【C++ STL篇(八)】set容器——零基础入门与核心用法精讲

C STL篇(八) —— set 讲解本篇文章将带你从零开始一步步掌握set的核心用法 。全程干货坐稳发车~ ദ്ദി˶̀֊́ )✧文章目录C STL篇(八) —— set 讲解1.序列式容器与关联式容器1.1 序列式容器1.2 关联式容器2. set 系列的初步认识2.1 参考资料2.2 set 类的声明拆解2.3 构造与迭代器2.4 增删查核心操作2.4.1 插入 insert2.4.2 查找 find 和 count2.4.3 删除 erase2.4.4 边界查找 lower_bound 与 upper_bound3. 跟着代码彻底弄懂每个细节3.1 insert 与迭代器遍历3.2 find 和 erase 的正确使用3.3 lower_bound 与 upper_bound 实现区间操作4. multiset5. 实战演练5.1 两个数组的交集5.2 环形链表6. 常见误区6.1 绝不能修改元素6.2 迭代器失效6.3 优先使用成员函数6.4 为什么 set 没有下标操作结语1.序列式容器与关联式容器在深入set之前我们先搞清楚 STL 容器大家族里的两大派系。1.1 序列式容器我们已经学过的string、vector、list、deque、array、forward_list等都属于序列式容器。你可以把它们想象成一排储物柜每个元素按照插入的顺序占据一个位置。比如你依次存入 A、B、C那它们在内存或逻辑上就按照 A-B-C 的顺序排列。即使你把 A 和 B 交换一下位置容器本身并不会因此“坏掉”依然是一个合法的序列。所以序列式容器中元素之间的关联很松散主要靠存储位置来组织和访问。1.2 关联式容器而关联式容器则完全不一样。它的逻辑结构通常是非线性的比如树形结构元素之间存在着某种“紧密的关联关系”——这种关系由关键字(key)来维持。如果你胡乱交换两个元素的位置这个容器的结构就会被破坏因为它不是靠位置来记忆元素的而是靠关键字和它们之间的排序规则。常见的关联式容器分为两大类有序关联容器map/set系列底层基于红黑树一种平衡二叉搜索树元素按照键值自动排序。无序关联容器unordered_map/unordered_set系列底层基于哈希表元素位置由哈希值决定不保证顺序。本文的主角是set和它的兄弟multiset它们都基于红黑树实现专门用于“关键字就是值本身”的场景即 key 搜索模型。而map则是“关键字-值”对key/value 模型的场景。今天我们先彻底拿下set。2. set 系列的初步认识2.1 参考资料关于set的官方参考可以查阅cplusplus.comcppreference.com2.2 set 类的声明拆解我们先来看一下set的类模板声明templateclassT,// 关键字类型classComparestd::lessT,// 比较函数对象classAllocstd::allocatorT// 空间配置器内存管理classset;这三个模板参数分别代表了T你打算存储的元素的类型。在set里元素的值就是它的键因此也叫key_type和value_type它们俩是同一回事。Compare如何比较两个元素的大小。默认是std::lessT也就是用运算符(升序)。set默认要求你的类型支持比较。如果你想自定义排序规则可以自己写一个仿函数函数对象传进来。Alloc控制内存分配的方式默认使用标准分配器。绝大多数情况下我们不需要动它。关键点set的底层是红黑树我们之后的文章中会对红黑树进行深入讲解它具备以下核心特性自动排序元素始终按Compare规则保持有序默认是升序。唯一性不允许有重复的关键字同一个值只能出现一次。高效操作插入、删除、查找的平均时间复杂度都是O(log N)。迭代器中序遍历当你用迭代器遍历时会得到一个有序序列。通常情况下我们只需要传第一个参数后两个保持默认就够用了。2.3 构造与迭代器set提供了多种构造方法我们可以重点关注以下几个最常用的// 1. 默认构造创建一个空 setexplicitset(constComparecompCompare(),constAllocallocAlloc());// 2. 迭代器区间构造用一段 [first, last) 区间内的元素初始化 settemplateclassInputIteratorset(InputIterator first,InputIterator last,constComparecompCompare(),constAllocAlloc());// 3. 拷贝构造set(constsetx);// 4. 初始化列表构造C11set(std::initializer_listvalue_typeil,constComparecompCompare(),constAllocallocAlloc());例如setints1;// 空集合setints2{3,1,4,1,5};// 初始化列表注意重复的 1 只会保留一个setints3(s2.begin(),s2.end());// 迭代器区间构造迭代器是访问set元素的核心工具。set提供了双向迭代器支持正向和反向遍历。一个极为重要的特性set的迭代器不允许修改元素的值。也就是说无论是iterator还是const_iterator你都不能通过*it ...来赋值。尝试这样做会导致编译错误。为什么因为set中的元素是自动排序的如果你偷偷改了某个键的值整个红黑树的结构就会被破坏导致未定义行为。所以标准库直接将迭代器指向的元素视为常量从根本上禁止修改。由于支持迭代器set自然也支持范围 for 循环遍历起来非常方便。2.4 增删查核心操作下面我们来看看set最常用的增删查接口。这些接口和vector、list很像但由于set的关联特性参数和返回值会有一些不同。2.4.1 插入 insert// 1. 插入单个值返回一个 pairfirst 是指向插入元素或已存在元素的迭代器// second 是 bool表示是否真的插入了新元素pairiterator,boolinsert(constvalue_typeval);// 2. 插入初始化列表中的值已存在的不会重复插入也没有返回值告诉你哪些没插入voidinsert(std::initializer_listvalue_typeil);// 3. 插入一段迭代器区间templateclassInputIteratorvoidinsert(InputIterator first,InputIterator last);单个插入的返回值非常有用pair的第一个成员是一个迭代器指向刚插入的那个新元素如果元素已经存在就指向那个已存在的元素。第二个成员是bool表示是否插入成功。你可以用它来判断某个值是不是之前就已经存在。2.4.2 查找 find 和 count// 在 set 中查找 val返回指向该元素的迭代器若没找到则返回 end()iteratorfind(constvalue_typeval);const_iteratorfind(constvalue_typeval)const;// 返回 val 的元素个数由于 set 不允许重复结果只能是 0 或 1size_typecount(constvalue_typeval)const;find的复杂度是O(log N)远比算法库里的通用std::find复杂度 O(N)高效。永远优先使用 set 自己的find。count对于set来说通常用于检查某个元素是否存在返回 1 表示存在返回 0 表示不存在。2.4.3 删除 erase// 删除一个迭代器指向的元素返回被删除元素的下一个迭代器C11起iteratorerase(const_iterator position);// 删除值为 val 的元素返回实际删除的元素个数0 或 1size_typeerase(constvalue_typeval);// 删除 [first, last) 区间的元素返回 lastiteratorerase(const_iterator first,const_iterator last);使用迭代器删除时要确保迭代器有效而且删除后该迭代器会失效不能再使用。按值删除会返回删掉了几个对于set来说就是 0 或 1set 中的值不重复。2.4.4 边界查找 lower_bound 与 upper_bound这两个函数在处理区间问题时特别有用// 返回第一个 val 的位置的迭代器iteratorlower_bound(constvalue_typeval);const_iteratorlower_bound(constvalue_typeval)const;// 返回第一个 val 的位置的迭代器iteratorupper_bound(constvalue_typeval);const_iteratorupper_bound(constvalue_typeval)const;lower_bound和upper_bound加起来可以精确划定一个范围[lower_bound(a), upper_bound(b))包含所有满足a ≤ x ≤ b的元素。你可以利用这个区间进行批量删除或遍历。3. 跟着代码彻底弄懂每个细节下面我们结合具体的代码一块一块地分析。3.1 insert 与迭代器遍历#includeiostream#includesetusingnamespacestd;intmain(){// setint s; // 默认升序从小到大setint,greaterints;// 传入 greaterint改为降序从大到小s.insert(4);s.insert(8);s.insert(4);// 重复的 4不会插入成功s.insert(2);s.insert(9);autoits.begin();while(it!s.end()){// 编译报错不能给常量赋值// *it 1;cout*it ;it;}coutendl;// 插入初始化列表中的值已经存在的值如 8插入失败s.insert({6,8,7,1,5});for(autoe:s){coute ;}coutendl;// 存放字符串的 set默认按照字符串的字典序ASCII码排序setstringstrset({sort,insert,add});for(autoe:strset){coute ;}coutendl;return0;}解析降序排列setint, greaterint s;通过第二个模板参数把比较器换成了greaterint。原本用lessint,比较规则是“小于”换成greater后比较规则变成了“大于”所以中序遍历结果是降序。输出时你会看到从大到小排列。重复插入s.insert(4);执行两次第二次插入时4已经存在操作会失败。set里仍然只有一个4。不能修改元素如果写*it 1;编译器会直接报错因为set的迭代器指向的是常量。这保护了底层的结构不被破坏。初始化列表插入s.insert({6,8,7,1,5});会把列表中的每个元素尝试插入。对于已经存在的元素比如之前就有的8会直接跳过。最终容器里是所有出现过的唯一值并按降序排列。字符串 setsetstring默认按照字典序比较所以输出顺序是add,insert,sort因为 ‘a’ ‘i’ ‘s’。3.2 find 和 erase 的正确使用intmain(){setints{3,9,2,6,8,1,4,7};for(autoe:s){coute ;// 输出1 2 3 4 6 7 8 9 自动升序}coutendl;// 删除最小的元素s.begin() 指向最小s.erase(s.begin());for(autoe:s){coute ;// 2 3 4 6 7 8 9}coutendl;// 方法1直接按值删除 xintx;cinx;intnums.erase(x);if(num0)coutx不存在endl;elsecoutx删除成功endl;// 方法2先用 find 找到迭代器再删除cinx;autoposs.find(x);if(pos!s.end()){s.erase(pos);// 删除后 pos 失效coutx删除成功endl;// cout *pos; // 不能使用失效的迭代器}else{coutx不存在endl;}// 算法库的 find不推荐用于 setautopos1std::find(s.begin(),s.end(),x);// O(N)autopos2s.find(x);// O(logN)// 利用 count 快速判断元素是否存在cinx;if(s.count(x))coutx存在endl;elsecoutx不存在endl;return0;}核心要点删除 begin()s.erase(s.begin())会移除当前最小的元素。注意删除后原来的s.begin()迭代器失效了但s本身依然有效下一次调用begin()会指向新的最小元素。按值删除erase(x)返回 0 或 1可以直接用来判断该值是否存在于集合中。这是一种既判断又删除的简洁写法。先 find 后 erasepos s.find(x)如果成功pos就是一个有效的迭代器。传给erase(pos)后pos 立即失效不能再解引用或递增。代码中注释掉的那行cout *pos;一旦执行行为是未定义的可能导致崩溃或读取垃圾数据。效率差异std::find(s.begin(), s.end(), x)在set上执行时是暴力遍历复杂度 O(N)而s.find(x)利用红黑树复杂度 O(log N)。在数据量大时两者差距惊人一定要用成员函数find。count判段是否存在s.count(x)要么是 0 要么是 1非常适合做条件判断比find略简洁一些但如果你还需要拿到迭代器做进一步操作find更好。3.3 lower_bound 与 upper_bound 实现区间操作intmain(){setintmyset;for(inti1;i10;i){myset.insert(i*10);// 10 20 30 40 50 60 70 80 90}for(autoe:myset){coute ;// 10 20 30 40 50 60 70 80 90}coutendl;// 想要获取在 [30, 50] 范围内的所有元素autoitlowmyset.lower_bound(30);// 返回第一个 30 的位置即 30autoitupmyset.upper_bound(50);// 返回第一个 50 的位置即 60// 演示更宽泛的范围 [25, 55]itlowmyset.lower_bound(25);// 25实际指向 30itupmyset.upper_bound(55);// 55实际指向 60// 删除 [itlow, itup) 区间内的所有元素myset.erase(itlow,itup);for(autoe:myset){coute ;// 输出 10 20 60 70 80 90}coutendl;return0;}这段代码展示了如何删除一个闭区间内的所有元素。初始集合包含 10 的倍数10, 20, 30, 40, 50, 60, 70, 80, 90。lower_bound(25)找到第一个≥ 25的元素。由于 20 25下一个是 30所以返回指向 30 的迭代器。upper_bound(55)找到第一个 55的元素。55 之后第一个是 60所以返回指向 60 的迭代器。区间[itlow, itup)包含了 30, 40, 50。erase(itlow, itup)会删除这三个元素剩下 10, 20, 60, 70, 80, 90。小技巧如果你想获取包含边界[a, b]的所有元素就用lower_bound(a)和upper_bound(b)然后作用于erase或遍历。4. multisetmultiset与set的用法几乎一模一样唯一的本质区别就是multiset允许存在多个相同的关键字也就是允许值冗余。这一差异导致了insert、find、count和erase的行为有所不同。intmain(){// multiset 只排序不去重multisetints{3,9,2,6,8,1,4,7,2,6,4,4};autoits.begin();while(it!s.end()){cout*it ;// 输出1 2 2 3 4 4 4 6 6 7 8 9it;}coutendl;// find 查找 x如果有多个返回中序遍历的第一个 xintx;cinx;autoposs.find(x);while(pos!s.end()*posx){cout*pos ;pos;}coutendl;// count 返回 x 的实际个数couts.count(x)endl;// erase 按值删除会把所有的 x 都删掉// 如果你只想删一个需要用迭代器删除poss.find(x);while(pos!s.end()*posx){poss.erase(pos);// erase 返回下一个迭代器所以可以安全地继续}coutendl;for(autoe:s){coute ;}coutendl;return0;}对比 set 逐一理解构造和插入multisetint可以接收重复值构造后它会自动排序但不会去重。输出中4出现了 3 次2和6各出现 2 次。find 的行为s.find(x)在有多个匹配时返回的是中序遍历遇到的第一个x。然后我们可以在循环里依次向后遍历直到遇到的值不再是x这样就访问了所有等于x的元素。count 的含义不同了在multiset里count(x)返回的是实际存在多少个x可能大于 1。erase 按值删除十分危险s.erase(x)会删除所有等于 x 的元素如果你只想删除其中一个必须通过迭代器s.erase(pos)来精确删除某个位置。代码中使用了一个循环每次erase(pos)返回被删除元素的下一个位置将其赋给pos可以安全地继续向后清理所有x。简单总结特性setmultiset是否允许重复元素否是insert返回值pairiterator, bool仅iterator总成功find返回唯一元素或 end()返回中序第一个count0 或 1实际个数erase(val)删除该值0 或 1 个删除所有该值5. 实战演练5.1 两个数组的交集传送门两个数组的交集思路拆解利用set完成去重排序迭代器遍历两个有序集合找交集两个迭代器都从头开始遍历两个有序集合如果迭代器指向的值不相等指向的值比较小的那个迭代器向后移动有序序列越往右数越大更小的数永远不可能匹配对面后方更大的数直接舍弃、迭代器后移即可。如果相等说明这是交集元素加入结果集然后两个迭代器都向后移动因为集合里没有重复元素这个数不会再出现了。代码示列classSolution{public:vectorintintersection(vectorintnums1,vectorintnums2){setints1(nums1.begin(),nums1.end());setints2(nums2.begin(),nums2.end());vectorintv;autoit1s1.begin();autoit2s2.begin();while(it1!s1.end()it2!s2.end()){if(*it1*it2){it1;}elseif(*it1*it2){it2;}else{v.push_back(*it1);it1;it2;}}returnv;}};这里再补充一个小问题如果要找差集怎么办迭代器指向的值更小的就是差集加入结果集然后让值更小的迭代器向后移动。如果两个迭代器相等 说明这个元素在两个集合里都存在不属于差集两个迭代器同时往后走。其中一个走到尾部了另一个没走完的值也是属于差集5.2 环形链表传送门环形链表思路拆解利用 set 存储已经访问过的节点指针遍历链表时第一次遇到重复访问的节点就是环的入口。创建一个集合用来存储已经访问过的节点指针遍历链表直到节点为空无环或找到重复节点有环。遍历结束没找到重复节点说明链表无环返回 nullptr代码示例classSolution{public:ListNode*detectCycle(ListNode*head){setListNode*s;//用来存储已经访问过的节点ListNode*curhead;while(cur){//count 可以判断节点是否存在if(!s.count(cur)){s.insert(cur);curcur-next;}else//找到了重复的节点returncur;}returnnullptr;}};6. 常见误区6.1 绝不能修改元素*it new_value在set中是行不通的。如果你需要修改一个元素只能先erase旧值再insert新值。6.2 迭代器失效set的插入操作不会使任何已有的迭代器失效删除操作只会使指向被删除元素的迭代器失效其它迭代器依然有效。这与vector有很大不同。代码中删除后继续使用pos是个常见的坑务必重新赋值或提前备份。6.3 优先使用成员函数set的成员函数find、lower_bound等是专为树结构优化的复杂度 O(log N)。不要图方便去用algorithm里全局的std::find那会变成线性遍历。6.4 为什么 set 没有下标操作set不是序列容器元素的位置由排序规则决定而不是线性索引。如果你需要“第 k 个元素”只能通过迭代器 循环但那样做效率较低通常说明set可能不是最适合你的结构。可以考虑在特定场景下使用vector并保持排序或结合其它数据结构。结语今天的内容到这里就结束了希望你能有所收获~干货整理到手抖觉得有用的话赏个三连回回血__(:ᗤ」ㄥ)_ _