C++ 关联式容器概述
序列式容器和关联式容器
STL 里的容器，大体可以分成两类。
- 序列式容器：
vector、list、deque、forward_list（C++11）等，元素按线性顺序存放，关注的是'把数据装起来'。 - 关联式容器：围绕
<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 有三种常见写法，行为不太一样：
- 按迭代器删除：删指定位置的元素；如果迭代器无效，程序就会出问题，所以通常先配合
find判断。 - 按值删除：返回被删掉的个数。
- 按区间删除：区间是左闭右开，常配合
lower_bound和upper_bound使用。
其中，lower_bound(k) 找的是第一个 >= k 的位置，upper_bound(k) 找的是第一个 > k 的位置。
multiset：允许重复的 set
multiset 和 set 很像，差别主要在是否允许重复值。
- 元素按特定顺序存储。
- 值可以重复。