C++ STL 关联式容器详解
在 C++ 标准模板库（STL）中，容器主要分为序列式和关联式两大类。序列式容器如 vector、list 等，元素按线性顺序存储；而关联式容器则通过关键字来保存和访问数据，逻辑结构通常是非线性的。
本章节重点讲解基于红黑树实现的关联式容器：set、multiset、map 和 multimap。它们共同的特点是底层使用平衡二叉搜索树，采用中序遍历时，容器中的元素是一个有序的序列。
提示：
set适用于 key 搜索场景，map适用于 key/value 搜索场景。
一、键值对基础
关联式容器常涉及键值对（Key-Value Pair）的概念。这是一种具有一一对应关系的结构，包含两个成员变量：
- key：代表键值，用于标识或排序。
- value：表示与 key 对应的信息。
例如字典中，英文单词是 key，中文含义是 value。
二、set 容器详解
1. 基本特性
set 是按照一定次序存储元素的容器。在 set 中，元素的 value 即标识它本身（类型为 T），且每个 value 必须是唯一的。插入时只需传入 value，无需构造显式的键值对。
- 唯一性：
set中的元素不可重复，常用于去重。 - 有序性：默认按照小于号
<比较，内部总是保持特定严格弱排序准则。 - 查找效率：时间复杂度为 O(log n)。
- 不可修改性：
set中的元素不允许直接修改，否则会破坏搜索树结构。 - 底层实现：二叉搜索树（红黑树）。
2. 构造与迭代器
set 支持正向和反向迭代遍历，默认按升序顺序（因为底层是中序遍历）。支持迭代器意味着也支持范围 for 循环。注意，iterator 和 const_iterator 都不支持通过迭代器修改数据。
// 无参默认构造
std::set<int> s1;
// 迭代器区间构造
std::set<int> s2(s1.begin(), s1.end());
// 拷贝构造
std::set<int> s3(s2);
// 初始化列表构造
std::set<int> s4 = {1, , };
it = s();
(it != s()) {
std::cout << *it << ;
++it;
}
