【C++】set

目录1. 引入从序列式到关联式容器2. set 的设计3. 核心接口3.1 构造函数 (Constructor)3.2 迭代器操作 (Iterator)3.3 容量操作 (Capacity)3.4 修改与查询操作 (Modifiers Operations)4. 核心操作4.1 插入与遍历自动去重排序4.2 查找与区间操作4.3 multiset不去重的变体5. 深度剖析底层引擎为什么是红黑树5.1 放弃 AVL 树的原因5.2 红黑树的妥协与优势5.3 迭代器底层的精妙设计附录基于红黑树封装自定义 set1. 引入从序列式到关联式容器在 C STL 中vector、list、deque等被称为序列式容器其底层是线性的数据结构存储的是元素本身。而为了解决海量数据下的高效率检索问题STL 引入了关联式容器。关联式容器的核心在于存储的是key, value结构的键值对。在底层键值对通过std::pair结构体实现包含代表键值的key(即first) 和对应信息的value(即second)。// STL 中键值对的底层定义templateclassT1,classT2structpair{typedefT1 first_type;typedefT2 second_type;T1 first;T2 second;pair():first(T1()),second(T2()){}pair(constT1a,constT2b):first(a),second(b){}};2. set 的设计根据底层结构的不同关联式容器分为树型结构如set、map和哈希结构。set作为树形关联容器的代表其设计具有以下核心特征真正的存储结构表面上set只对外暴露value但其底层实际存放的是由value, value构成的键值对。元素天然有序且唯一set内部根据特定的严格弱排序准则默认按小于升序对元素进行排序且每个value必须唯一。元素绝对禁止修改constset中的元素在容器中总是const的。深度思考为什么不允许修改因为set的底层是二叉搜索树如果允许修改结点的key会直接破坏树的有序性与严格弱排序准则导致整棵树失效。时间复杂度依靠平衡树支撑查找、插入和删除的时间复杂度均严格稳定在O ( log ⁡ 2 N ) O(\log_2 N)O(log2​N)。3. 核心接口3.1 构造函数 (Constructor)函数声明功能介绍set (const Compare comp Compare(), const Allocator Allocator() );构造空的 setset (InputIterator first, InputIterator last, ...);用[first, last)区间中的元素构造 setset (const setKey,Compare,Allocator x);set 的拷贝构造3.2 迭代器操作 (Iterator)函数声明功能介绍iterator begin()/iterator end()返回正向迭代器begin指向首元素end指向尾元素下一个位置const_iterator cbegin()/cend()返回const版本的正向迭代器reverse_iterator rbegin()/rend()返回反向迭代器rbegin即endrend即beginconst_reverse_iterator crbegin()/crend()返回const版本的反向迭代器3.3 容量操作 (Capacity)函数声明功能介绍bool empty() const检测 set 是否为空空返回true否则返回falsesize_type size() const返回 set 中有效元素的个数3.4 修改与查询操作 (Modifiers Operations)函数声明功能介绍pairiterator,bool insert(const value_type x)在 set 中插入元素 x返回该元素位置, 是否插入成功若已存在则返回 falseiterator erase (const_iterator position)删除 position 位置上的元素size_type erase (const key_type x)删除 set 中值为 x 的元素返回删除的元素个数iterator erase (const_iterator first, const_iterator last)删除 set 中[first, last)区间中的元素void swap (setKey, Allocator Compare, st)交换两个 set 中的元素void clear ()将 set 中的元素清空iterator find (const key_type x) const返回 set 中值为 x 的元素的位置迭代器找不到则返回end()size_type count (const key_type x) const返回 set 中值为 x 的元素的个数对于 set 只能是 0 或 14. 核心操作4.1 插入与遍历自动去重排序在set中插入元素时无需显式构造键值对直接传入value即可。#includeiostream#includesetusingnamespacestd;intmain(){// 去重 排序setints;s.insert(5);s.insert(2);s.insert(7);s.insert(4);s.insert(9);s.insert(9);// 重复插入无效s.insert(9);s.insert(1);autoits.begin();while(it!s.end()){cout*it ;it;}coutendl;// 范围 for 遍历for(autoe:s){coute ;}coutendl;return0;}4.2 查找与区间操作必须认清算法库中的std::find与set::find的本质区别// 1. 算法库的 find底层暴力遍历时间复杂度 O(N)autopos1find(s.begin(),s.end(),x);// 2. set 成员函数 find利用红黑树查找时间复杂度 O(log_2 N)autopos2s.find(x);对于区间操作set提供了lower_bound返回≥ \ge≥目标的迭代器和upper_bound返回 目标的迭代器极大地简化了左闭右开[first, last)区间的删除操作。intmain(){setintmyset;setint::iterator itlow,itup;for(inti1;i10;i)myset.insert(i*10);// 10 20 30 40 50 60 70 80 90itlowmyset.lower_bound(30);// 30itupmyset.upper_bound(60);// 60// 删除 [30, 60]myset.erase(itlow,itup);// 剩余: 10 20 70 80 90for(setint::iterator itmyset.begin();it!myset.end();it)cout *it;coutendl;return0;}4.3 multiset不去重的变体intmain(){multisetints;s.insert(1);s.insert(10);s.insert(15);s.insert(14);s.insert(14);s.insert(14);for(autow:s){coutw ;}coutendls.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。#includefunctional// 为了引入 std::lessnamespacebit{// 增加 Compare 模板参数默认使用 lessKtemplateclassK,classComparestd::lessKclassset{typedefK ValueType;structKeyOfValue{constKoperator()(constValueTypekey)const// 注意加 const{returnkey;}};// 将 Compare 也传给底层的红黑树typedefRBTreeK,ValueType,KeyOfValue,CompareRBTree_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 如果返回 pairRBTree_t::Iterator, bool// 这里可能需要做一个隐式或显式的转换转成 pairiterator, boolpairiterator,boolinsert(constValueTypedata){return_t.Insert(data);}voidclear(){_t.Clear();}iteratorfind(constKkey)const// 提供 const 版本的 find{return_t.Find(key);}private:RBTree_t _t;};}