1. 引入：从序列式到关联式容器

在 C++ STL 中，vector、list、deque等被称为序列式容器，其底层是线性的数据结构，存储的是元素本身。而为了解决海量数据下的高效率检索问题，STL 引入了关联式容器。

关联式容器的核心在于存储的是<key, value>结构的键值对。在底层，键值对通过std::pair结构体实现，包含代表键值的key(即first) 和对应信息的value(即second)。

// STL 中键值对的底层定义template<classT1,classT2>structpair{typedefT1 first_type;typedefT2 second_type;T1 first;T2 second;pair():first(T1()),second(T2()){}pair(constT1&a,constT2&b):first(a),second(b){}};

2. set 的设计

根据底层结构的不同，关联式容器分为树型结构（如set、map）和哈希结构。set作为树形关联容器的代表，其设计具有以下核心特征：

• 真正的存储结构：表面上set只对外暴露value，但其底层实际存放的是由<value, value>构成的键值对。

• 元素天然有序且唯一：set内部根据特定的严格弱排序准则（默认按小于升序）对元素进行排序，且每个value必须唯一。

• 元素绝对禁止修改（const）：set中的元素在容器中总是const的。深度思考：为什么不允许修改？因为set的底层是二叉搜索树，如果允许修改结点的key，会直接破坏树的有序性与严格弱排序准则，导致整棵树失效。

• 时间复杂度：依靠平衡树支撑，查找、插入和删除的时间复杂度均严格稳定在O ( log ⁡ 2 N ) O(\log_2 N)O(log2​N)。

3. 核心接口

3.1 构造函数 (Constructor)

3.2 迭代器操作 (Iterator)

3.3 容量操作 (Capacity)

3.4 修改与查询操作 (Modifiers & Operations)

4. 核心操作

4.1 插入与遍历（自动去重排序）

在set中插入元素时，无需显式构造键值对，直接传入value即可。

#include<iostream>#include<set>usingnamespacestd;intmain(){// 去重 + 排序set<int>s;s.insert(5);s.insert(2);s.insert(7);s.insert(4);s.insert(9);s.insert(9);// 重复插入无效s.insert(9);s.insert(1);autoit=s.begin();while(it!=s.end()){cout<<*it<<" ";++it;}cout<<endl;// 范围 for 遍历for(autoe:s){cout<<e<<" ";}cout<<endl;return0;}

4.2 查找与区间操作

必须认清算法库中的std::find与set::find的本质区别：

// 1. 算法库的 find，底层暴力遍历，时间复杂度 O(N)autopos1=find(s.begin(),s.end(),x);// 2. set 成员函数 find，利用红黑树查找，时间复杂度 O(log_2 N)autopos2=s.find(x);

对于区间操作，set提供了lower_bound（返回≥ \ge≥目标的迭代器）和upper_bound（返回> >>目标的迭代器），极大地简化了左闭右开[first, last)区间的删除操作。

intmain(){set<int>myset;set<int>::iterator itlow,itup;for(inti=1;i<10;i++)myset.insert(i*10);// 10 20 30 40 50 60 70 80 90itlow=myset.lower_bound(30);// >= 30itup=myset.upper_bound(60);// > 60// 删除 [30, 60]myset.erase(itlow,itup);// 剩余: 10 20 70 80 90for(set<int>::iterator it=myset.begin();it!=myset.end();++it)cout<<' '<<*it;cout<<endl;return0;}

4.3 multiset：不去重的变体

intmain(){multiset<int>s;s.insert(1);s.insert(10);s.insert(15);s.insert(14);s.insert(14);s.insert(14);for(autow:s){cout<<w<<" ";}cout<<endl<<s.count(14);return0;}

如果业务场景仅需排序而不需要去重，可以使用multiset。其接口与set基本一致，底层同样存放<value, value>，但允许元素重复。此时调用count(x)能够返回元素出现的实际次数，而不再局限于 0 或 1。

5. 深度剖析：底层引擎为什么是红黑树？

set和map的底层均为红黑树 (Red-Black Tree)，而不是 AVL 树。

5.1 放弃 AVL 树的原因

AVL 树是绝对平衡的二叉搜索树，要求每个结点的左右子树高度差绝对值不超过 1。这保证了极高的查询效率O ( log ⁡ 2 N ) O(\log_2 N)O(log2​N)。但是，在频繁增删结点的场景下，AVL 树为了维持这种绝对平衡，需要进行大量的旋转操作，甚至在删除时旋转可能持续到根结点，性能开销极大。

5.2 红黑树的妥协与优势

红黑树通过颜色约束牺牲了部分平衡性，来换取更少旋转次数：

• 每个结点不是红色就是黑色。

• 根结点必须是黑色。

• 不能有连在一起的红色结点。

• 每条路径上的黑色结点数目必须相同。

这些性质确保了红黑树的最长路径不会超过最短路径的两倍，达成了一种“近似平衡”。它的增删改查时间复杂度依然是O ( log ⁡ 2 N ) O(\log_2 N)O(log2​N)，但由于旋转次数远少于 AVL 树，在实际应用（如 C++ STL、Linux 内核）中具有更高的综合性能。

5.3 迭代器底层的精妙设计

STL 规定begin()和end()构成前闭后开的区间。在中序遍历红黑树时，begin()应当是最小结点（最左侧结点），那end()（最大结点的下一个位置）应该指向哪里？不能简单设为nullptr，因为还要支持对end()迭代器进行--操作找回最后一个元素。

STL 的红黑树实现中，巧妙地增加了一个黑色的头结点 (header)：

• header->_pParent指向红黑树真实的root。

• header->_pLeft指向树中最小的结点（即begin()）。

• header->_pRight指向树中最大的结点。

• end()迭代器直接指向这个header结点。

这种设计完美闭环了整棵树的迭代逻辑。

附录：基于红黑树封装自定义 set

为了证明底层结构与表层 API 的关系，我们可以通过复用泛型红黑树（RBTree）来模拟实现一个完整的set。

#include<functional>// 为了引入 std::lessnamespacebit{// 增加 Compare 模板参数，默认使用 less<K>template<classK,classCompare=std::less<K>>classset{typedefK ValueType;structKeyOfValue{constK&operator()(constValueType&key)const// 注意加 const{returnkey;}};// 将 Compare 也传给底层的红黑树typedefRBTree<K,ValueType,KeyOfValue,Compare>RBTree_t;public:// 关键：set 的迭代器统一使用红黑树的 const 迭代器typedeftypenameRBTree_t::ConstIterator iterator;typedeftypenameRBTree_t::ConstIterator const_iterator;public:set(){}// 提供 const 版本的迭代器接口iteratorbegin()const{return_t.Begin();}iteratorend()const{return_t.End();}size_tsize()const{return_t.Size();}boolempty()const{return_t.Empty();}// 注意：底层 Insert 如果返回 pair<RBTree_t::Iterator, bool>// 这里可能需要做一个隐式或显式的转换，转成 pair<iterator, bool>pair<iterator,bool>insert(constValueType&data){return_t.Insert(data);}voidclear(){_t.Clear();}iteratorfind(constK&key)const// 提供 const 版本的 find{return_t.Find(key);}private:RBTree_t _t;};}