在之前的学习中，我们已经接触过 string、vector、list 等序列式容器。今天我们来深入了解一下关联式容器中的 map 和 set。
序列式容器与关联式容器
STL 容器主要分为两大类。序列式容器如 vector、list、deque 等，其逻辑结构为线性序列，元素按存储位置顺序保存和访问。而关联式容器则不同，它们通常采用非线性结构（如树或哈希表），元素通过关键字来保存和访问。常见的关联式容器包括 map/set 系列以及 unordered_map/unordered_set 系列。
本章节重点讲解的 map 和 set，其底层实现基于红黑树（一种平衡二叉搜索树）。简单来说，set 是 key 搜索场景的结构，而 map 则是 key/value 搜索场景的结构。
键值对概念
键值对（Key-Value Pair）用来表示具有一一对应关系的结构，一般包含 key 和 value 两个成员变量。key 代表键值，value 表示与 key 对应的信息。比如字典中必然存在英文单词与其对应的中文含义。
树形结构的关联式容器
根据应用场景不同，STL 实现了两种结构的关联式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。它们的共同点是使用平衡搜索树（即红黑树）作为底层结构，采用中序遍历，因此容器中的元素是一个有序的序列。
Set 详解
Set 介绍
set 是按照一定次序存储元素的容器。在 set 中，元素的 value 也标识它（value 就是 key，类型为 T），并且每个 value 必须是唯一的。插入元素时，只需要插入 value 即可，不需要构造键值对。
内部，set 中的元素总是按照其内部比较对象所指示的特定严格弱排序准则进行排序。这意味着：
- set 中的元素不可以重复，因此可以使用 set 进行去重。
- set 中的元素默认按照小于号进行比较。
- set 中查找某个元素的时间复杂度为 O(log n)。
- set 中的元素不允许修改，以保证数据排序和搜索树结构不被破坏。
- 与 map/multimap 不同，map/multimap 中存储的是真正的键值对 <key, value>，set 中只放 value，但在底层实际存放的是由 <value, value> 构成的键值对。
Set 的构造和迭代器
set 支持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序。支持迭代器就意味着支持范围 for 循环。需要注意的是，set 的 iterator 和 const_iterator 都不支持通过迭代器修改数据，因为修改关键字会破坏底层搜索树的结构。
#include<set>
#include<iostream>
using namespace std;
int main() {
// 无参默认构造
set<int> s1;
// 拷贝构造
set<int> s2 = s1;
// 初始化列表构造
set<int> s3 = {1, 2, 3};
// 迭代器遍历
auto it = s();
(it != s()) {
cout << *it << ;
++it;
}
cout << endl;
( e : s3) {
cout << e << ;
}
;
}
