C++ map、set 与关联式容器入门

C++ 关联式容器概述

序列式容器和关联式容器

STL 里的容器，大体可以分成两类。

1. 序列式容器：vector、list、deque、forward_list（C++11）等，元素按线性顺序存放，关注的是'把数据装起来'。
2. 关联式容器：围绕 <key, value> 或 key 本身组织数据，更偏向'按键查数据'。

如果你经常做查找、统计、去重，这类容器通常比序列式容器更顺手。

键值对 <key, value>

键值对就是通过 key 找到 value 的结构。英汉字典是最常见的例子：英文单词是 key，中文释义是 value。这个模型本身不复杂，难点在于容器怎么把它组织好、查起来又快又稳。

树形结构的关联式容器

STL 里常见的树形关联式容器有四种：map、set、multimap、multiset。它们的底层通常是平衡搜索树，常见实现是红黑树，所以元素天然有序，遍历时拿到的是中序序列。

set 容器：只管 value，不管 pair

基本特征

set 按一定顺序存储元素，元素本身就是它的身份，也就是'value 即 key'。这意味着每个值都必须唯一，不能重复。

它有几个很实用的特点：

• 元素不能在容器内部直接修改，只能插入或删除。
• 默认按小于号比较，也就是升序排列。
• 底层一般是红黑树，查找复杂度是 O(log n)。
• 头文件是 <set>。

和 map 的区别

map / multimap 存的是真正的 <key, value>；set 只保存 value，但内部可以理解成 <value, value>。这也是为什么 set 插入时只需要给一个值，不用先拼 pair。

常见用途

set 最常见的场景就是去重和排序。把一组数丢进去，重复项会被自动过滤，遍历出来又是有序的。这个特性很朴素，但线上处理数据时特别省事。

删除时的几个细节

erase 有三种常见写法，行为不太一样：

1. 按迭代器删除：删指定位置的元素；如果迭代器无效，程序就会出问题，所以通常先配合 find 判断。
2. 按值删除：返回被删掉的个数。
3. 按区间删除：区间是左闭右开，常配合 lower_bound 和 upper_bound 使用。

其中，lower_bound(k) 找的是第一个 >= k 的位置，upper_bound(k) 找的是第一个 > k 的位置。

multiset：允许重复的 set

multiset 和 set 很像，差别主要在是否允许重复值。

• 元素按特定顺序存储。
• 值可以重复。
• 元素同样不能在容器中直接修改。
• 底层通常也是红黑树。

它的接口和 set 基本一致，只是有几处行为会更贴近'多重集合'的语义：

• erase 返回删除元素的个数。
• count 返回某个值出现的次数。
• find 返回中序遍历里第一次出现的位置。

map 容器：最常用的键值表

基本特征

map 存的是键值对，按 key 排序。

• key 用来排序，也用来唯一标识元素。
• value 保存关联内容。
• 内部通常用 pair<const key, T> 表示一个元素。
• 可以按顺序直接遍历。
• 支持下标访问符 []。
• 头文件是 <map>。

pair 模板类

pair 定义在 <utility> 头文件中，用来把两个不同类型的值绑在一起。make_pair 可以直接构造它，写起来更省事。

模板参数

map 的模板参数通常包括：

1. key：键的类型。
2. T：值的类型。
3. Compare：比较器，默认按小于号比较；自定义类型时往往要自己传。
4. Alloc：空间配置器，一般不用手动管。

insert 的用法

insert 常接收 value_type，也就是一个 pair。遍历时，别把它当成普通单值处理，得用 first 和 second 访问键和值。

如果是范围 for，建议带上引用，少一次拷贝，代码也更干净。

去重

map 会按 key 去重，key 相同的元素不能同时存在。字符串 key 的排序，通常就是按字符的 ASCII 顺序一路比下去。

multimap：允许重复 key

multimap 可以看作 map 的'宽松版'，区别只有一个：key 可以重复。适合一对多的场景，比如一个分类下挂多个条目。

map 的 [] 操作符

[] 是 map 里最容易被顺手用坏的接口，但统计场景里它确实很方便。

计算水果出现次数

常见做法有三种：

1. 用迭代器和 find：先查，再决定要不要插入或更新。
2. 看 insert 的返回值：insert 会返回 pair<iterator, bool>，bool 表示是否插入成功，iterator 指向新插入或已经存在的结点。
3. 直接用 []：
   • 如果 key 不存在，[] 会先插入一个默认构造的 value。
   • int 默认是 0，指针默认是 nullptr。
   • 逻辑上可以理解成先查找，找不到就补一个默认值，再返回 second。

所以像 mapCount[e]++ 这种写法，本质上就是把 e 对应的计数加一。它很适合做频次统计，写法短，也够直接。