C++_关联容器

关联容器

关联容器的特点是：

按关键字（key）而不是按位置存取元素

它们支持：

• 高效查找
• 按关键字访问
• 自动按关键字组织元素（有序容器）或按哈希组织元素（无序容器）

关联容器类型

关联容器分两大类：

1. 有序关联容器
2. 无序关联容器

有序关联容器

元素按关键字有序保存（默认按 < 排序）。

容器	作用
map	保存 关键字-值 对，每个关键字唯一
set	只保存关键字，每个关键字唯一
multimap	保存 关键字-值 对，关键字可重复
multiset	只保存关键字，关键字可重复

无序关联容器

按哈希函数组织元素，不保证有序。

容器	作用
unordered_map	哈希版 map，关键字唯一
unordered_set	哈希版 set，关键字唯一
unordered_multimap	哈希版 multimap，关键字可重复
unordered_multiset	哈希版 multiset，关键字可重复

关联容器与顺序容器的区别

顺序容器按“位置”组织元素，如：

• vector
• deque
• list

关联容器按“关键字”组织元素，因此：

• 不支持位置相关操作
• 没有 push_back、push_front
• 没有“第几个元素”这种核心概念

例如：

set<int> s;
s.insert(3);
s.insert(1);
s.insert(2);

容器中的顺序不是插入顺序，而是关键字顺序：

1 2 3

关联容器的迭代器

关联容器的迭代器一般是双向迭代器：

• 可以 ++it
• 可以 --it

但不能像 vector 那样做：

it + 1   // 不行

注意：

• set 中元素就是关键字，因此不能通过迭代器修改元素
• map 中关键字部分也不能修改

使用 map

map 保存的是：

key -> value

所以它常被称为关联数组。

和普通数组的区别：

• 普通数组下标通常是整数
• map 的“下标”可以是任意可比较类型

例如：

map<string, int> word_count;
word_count["hello"] = 3;

这里：

• 关键字：string
• 值：int

map 中的元素类型

map 的每个元素其实是一个 pair：

pair<const Key, T>

例如：

map<string, int> m;

则元素类型是：

pair<const string, int>

其中：

• first：关键字
• second：对应的值

例如：

for (auto &p : m) {
    cout << p.first << " " << p.second << endl;
}

使用 set

set 只保存关键字，不保存额外值。

例如：

set<int> s = {3, 1, 2};

最终按关键字有序保存为：

1 2 3

特点：

• 元素唯一
• 自动排序
• 适合“判重”“查某元素是否存在”

定义关联容器

定义 map

定义 map 时必须给出：

• 关键字类型
• 值类型

map<string, int> m;

定义 set

定义 set 时只需给出关键字类型：

set<string> s;

列表初始化

set

set<int> s{1, 2, 3};

map

map<string, int> m{
    {"Tom", 90},
    {"Alice", 95}
};

map 初始化时，每个元素都是：

{key, value}

关键字是否唯一

关键字唯一：

• map
• set
• unordered_map
• unordered_set

关键字可重复：

• multimap
• multiset
• unordered_multimap
• unordered_multiset

pair 类型

pair 定义在头文件：

#include <utility>

作用：

• 把两个值当作一个整体保存

基本定义

pair<string, int> p("Tom", 18);

或：

pair<string, int> p = {"Tom", 18};

成员访问

p.first
p.second

例如：

cout << p.first << " " << p.second;

make_pair

auto p = make_pair("Tom", 18);

编译器会自动推断类型。

pair 的常用操作

操作	含义
pair<T1, T2> p;	默认构造
pair<T1, T2> p(v1, v2);	用两个值构造
pair<T1, T2> p = {v1, v2};	列表初始化
make_pair(v1, v2)	生成 pair
p.first	第一个成员
p.second	第二个成员

关联容器的类型成员

类型成员	含义
key_type	关键字类型
mapped_type	值类型，仅 map 有
value_type	元素类型

其中：

• 对 set：value_type == key_type
• 对 map：value_type == pair<const key_type, mapped_type>

为什么 map 的 key 不能修改

因为 map 中元素是按 key 排序保存的。
如果能随意改 key，会破坏容器内部顺序。

所以：

• first 是 const
• second 可以修改

例如：

it->first = "new";   // 错
it->second = 100;    // 对

添加元素

关联容器常用：

• insert
• emplace

单个插入

c.insert(v);
c.emplace(args);

map / set

• 若关键字不存在，插入成功
• 若关键字已存在，插入失败

返回值：

pair<iterator, bool>

其中：

• first：指向关键字对应元素
• second：是否插入成功

例如：

set<int> s;
auto ret = s.insert(10);

multimap / multiset

对于允许重复关键字的容器：

• 总能插入成功
• 返回值通常是指向新元素的迭代器

范围插入 / 列表插入

c.insert(b, e);
c.insert(il);

• b, e：迭代器范围
• il：初始化列表

带提示位置的插入

c.insert(p, v);
c.emplace(p, args);

p 是提示位置，告诉容器“从这里附近开始找插入点”。

注意：

• 只是提示
• 不保证一定用上
• 不像顺序容器那样表示“插到 p 前面”

删除元素

按关键字删除

c.erase(k);

作用：

• 删除所有关键字为 k 的元素

返回值：

• 删除元素个数

对于唯一关键字容器，返回值只能是 0 或 1

按迭代器删除

c.erase(p);

删除 p 指向的元素。

返回值：

• 指向被删元素之后位置的迭代器

按范围删除

c.erase(b, e);

删除 [b, e) 范围元素。

map 的下标操作

只适用于：

• map
• unordered_map

operator[]

c[k]

作用：

• 若 k 存在：返回对应值
• 若 k 不存在：插入一个新元素

新元素的值会进行值初始化

例如：

map<string, int> m;
cout << m["Tom"];

如果 "Tom" 原来不存在，则会插入：

{"Tom", 0}

at

c.at(k)

作用：

• 若关键字存在：返回对应值
• 若不存在：抛出 out_of_range

[] 的重要特点

[] 可能导致插入元素，所以：

如果只是想查某 key 是否存在，不要轻易用 []

应优先用：

• find
• count

访问元素

find

c.find(k)

返回：

• 找到：指向该元素的迭代器
• 找不到：c.end()

count

c.count(k)

返回关键字为 k 的元素个数。

对于不允许重复关键字的容器：

• 返回值只能是 0 或 1

对于 multiset / multimap：

• 可能大于 1

lower_bound

c.lower_bound(k)

返回第一个不小于 k 的元素迭代器。

即：

>= k

upper_bound

c.upper_bound(k)

返回第一个大于 k 的元素迭代器。

即：

> k

equal_range

c.equal_range(k)

返回一个 pair，表示关键字等于 k 的元素范围：

{lower_bound(k), upper_bound(k)}

特别适合：

• multiset
• multimap

哪些不适用于无序容器

下面这些只适用于有序关联容器：

• lower_bound
• upper_bound
• equal_range

因为无序容器没有“大小顺序”的概念。

map 与 set 的典型用途

map

适合：

• 统计次数
• 建立映射关系
• 通过 key 查值

例如单词计数：

map<string, int> word_count;
string word;
while (cin >> word)
    ++word_count[word];

set

适合：

• 判重
• 保留不重复元素
• 判断某元素是否存在

例如：

set<int> s;
s.insert(10);
if (s.find(10) != s.end()) {
    // 存在
}

无序容器

无序容器使用：

• 哈希函数
• == 运算符

而不是 < 排序。

特点：

• 不按关键字顺序存放
• 平均情况下查找更快
• 适合只关心“是否存在 / 对应值”，不关心顺序的场景

什么时候用无序容器

适合：

• 不需要有序遍历
• 更看重平均查找效率
• 关键字适合做哈希

不适合：

• 需要有序输出
• 需要范围查找（lower_bound 等）

无序容器的底层：桶

无序容器底层通常由很多**桶（bucket）**组成。

过程大致是：

1. 对关键字做哈希
2. 算出它应落入哪个桶
3. 在该桶中查找元素

桶中的冲突

不同关键字可能哈希到同一个桶，这叫：

• 哈希冲突

此时需要在桶中继续比较。

所以无序容器性能与这些因素有关：

• 哈希函数好不好
• 桶够不够多
• 各桶是否分布均匀

无序容器的要求

要把某类型作为无序容器的关键字，通常需要：

1. 可以计算哈希值
2. 可以用 == 判断相等

标准库已经为很多内置类型和标准类型提供了哈希支持，如：

• int
• string

无序容器的桶接口

操作	含义
c.bucket_count()	当前桶数
c.max_bucket_count()	最大可能桶数
c.bucket_size(n)	第 n 个桶中的元素个数
c.bucket(k)	关键字 k 在哪个桶中

桶迭代

无序容器不仅能遍历整个容器，也能遍历某个桶。

操作	含义
local_iterator	桶迭代器类型
const_local_iterator	const 桶迭代器
c.begin(n), c.end(n)	第 n 个桶的迭代器范围
c.cbegin(n), c.cend(n)	const 桶迭代器范围

哈希策略

操作	含义
c.load_factor()	平均每个桶装多少元素
c.max_load_factor()	容器希望维持的最大平均桶大小
c.rehash(n)	重新组织桶，使桶数至少为 n
c.reserve(n)	预留空间，使其容纳 n 个元素而尽量不 rehash

load_factor

load_factor = size() / bucket_count()

值越大，说明每个桶平均元素越多，冲突可能越多。

rehash 和 reserve

• rehash(n)：直接调整桶数量
• reserve(n)：按将来要装 n 个元素来准备空间

有序容器 vs 无序容器

对比项	有序容器	无序容器
组织方式	按关键字顺序	按哈希
遍历结果	有序	无序
查找依据	<	hash + ==
支持范围查找	支持	不支持
平均查找效率	较快	通常更快

易错点总结

关联容器不支持 push_back / push_front

因为元素位置不是由插入位置决定，而是由关键字决定。

map 的元素是 pair<const key, value>

所以：

• key 不能改
• value 可以改

set 的元素不能改

因为元素本身就是 key，改了会破坏有序性。

map[key] 可能插入新元素

如果只是检查是否存在，优先用：

find
count

lower_bound / upper_bound 只适用于有序关联容器

无序容器不支持这些操作。

multiset / multimap 允许重复关键字

而 set / map 不允许。

无序容器不保证遍历顺序

所以不能依赖输出顺序。

insert 在 map / set 中不一定成功

因为 key 可能已存在。

小结

关联容器的主线：

1. 按关键字存取，而不是按位置
2. 分为：

• 有序：map / set / multimap / multiset
• 无序：unordered_*

3. map 保存键值对，set 只保存键
4. map[key] 可能插入新元素
5. 无序容器依赖哈希和桶
6. 有序容器支持范围查找，无序容器不支持

优先掌握：

• map
• set
• insert
• erase
• find
• count
• []
• at
• lower_bound
• upper_bound
• equal_range
• unordered_map 的基本思想