C++ 关联式容器概述
序列式与关联式容器
- 序列式容器：vector、list、deque、forward_list(C++11) 等，底层为线性序列数据结构，存储元素本身。
- 关联式容器：存储<key, value>结构的键值对，数据检索效率通常比序列式容器更高。
键值对<key, value>
通过 key 找 value，表示具有一一对应关系的结构。一般包含 key 和 value 两个成员变量。例如英汉字典，英文单词（key）对应中文含义（value）。
树形结构的关联式容器
STL 实现了两种管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。共同点是使用平衡搜索树（红黑树）作为底层结构，元素是有序序列（中序遍历）。
set 容器（key 模型）
功能介绍
- set 是按照一定次序存储元素的容器。
- 在 set 中，元素的 value 也标识它（value 就是 key），每个 value 必须唯一。
- 元素不能在容器中修改，但可以插入或删除。
- 内部按照特定严格弱排序准则进行排序。
- 底层用二叉搜索树（红黑树）实现。
注意事项
- map/multimap 存储真正的键值对<key, value>，set 只放 value，但底层实际存放<value, value>。
- 插入元素时只需插入 value，无需构造键值对。
- 元素不可重复（可用于去重）。
- 迭代器遍历可得有序序列。
- 默认按小于号比较。
- 查找时间复杂度为 O(log n)。
- 头文件：。
基本使用
插入与遍历
需先查看文档学习接口。迭代器使用方法与其他容器相同。
排序和去重
set 根据搜索二叉树的中序遍历插入，可对一组数排序并自动去重。
erase（删除）的区别
- 删除迭代器位置：若存在则删除，不存在报错。需配合 find 函数判断是否存在。
- 删除 val 值：返回删除的个数。
- 删除区间：左闭右开。利用 lower_bound（大于等于 k）和 upper_bound（大于 k）得到区间。
multiset 容器（允许插入重复值）
介绍
- 按特定顺序存储元素，元素可重复。
- value 识别自身（<value, value>），类型 T。
- 元素不可修改，可插入或删除。
- 底层结构为二叉搜索树（红黑树）。
基本使用
与 set 类似，最大区别是支持存储重复数据。
接口区别
- 删除返回值：返回删除元素的个数。
- count 函数：返回 val 在容器中的个数。
- find 函数：查找中序遍历中出现的第一个 val 值并返回位置。
map 容器（<key, value>模型）
介绍
- 按特定次序（key 比较）存储键值组合元素。
- key 用于排序和唯一标识，value 存储关联内容。
- 内部 key 与 value 通过 pair 绑定，typedef pair<const key, T> value_type。
