先来总体看一下set的相关接口。总的来说还是之前我们在vectorstring接触过的那些东西。虽然看起来接口很多但常用的以及会学习到的就那些。2.2 set类的介绍set的声明如下。参数1T就是set底层关键字的类型。这个T就是key名字不同。参数2set默认要求T⽀持⼩于⽐较如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现仿函数传给第⼆个模版参数。参数3set底层存储数据的内存是从空间配置器申请的空间配置器如果需要可以⾃⼰实现内存池传给第三个参数。⼀般情况下我们都不需要传后两个模版参数。set底层是⽤红⿊树以后会介绍实现增删查效率是O 迭代器遍历是⾛的搜索树的中序所以是有序的。2.3 set的构造和迭代器先看它的构造函数。再来看看他的迭代器。从文档介绍可以看出这是一个双向迭代器⽀持正向和反向迭代遍历遍历默认按升序顺序因为底层是⼆叉搜索树迭代器遍历⾛的中序。⽀持迭代器就意味着⽀持范围forset的iterator和const_iterator都不⽀持迭代器修改数据修改关键字数据破坏了底层搜索树的结构。2.4 set的增删查不支持改2.4.1 insert先看insert增。增这里首先支持增加一个value_type类型的东西value_type什么从这里可以看到其实就是我们传的那个关键字Key并且上面那个key_type也是key。所以就是插入一个key。这里的返回值类型后面会说暂时不关注。用set的时候要包含头文件#include set代码语言javascriptAI代码解释#include iostream #include set using namespace std; int main() { setint s; s.insert(2); s.insert(1); s.insert(4); //重复 s.insert(3); s.insert(4); //重复 return 0; }第二个参数不传的话默认排升序。用迭代器遍历一下。代码语言javascriptAI代码解释int main() { setint s; s.insert(2); s.insert(1); s.insert(4); s.insert(3); s.insert(4); auto it s.begin(); while (it ! s.end()) { cout *it ; it; } cout endl; return 0; }如果这里不用auto的话就是setint::iterator it s.begin();可以看到此时的s就是一个去重并且升序的状态。如果想变成降序set的参数列表就多传一个参数。代码语言javascriptAI代码解释setint, greaterint s;此时的s就是去重并且排降序。还支持在某个位置插入一般不用。支持插入一段迭代器区间。还支持插入initializer_list。就是用大括号括起来插入。代码语言javascriptAI代码解释setint s; s.insert(2); s.insert(1); s.insert(4); s.insert(3); s.insert(4); s.insert({ 7, 5, 8, 6 }); //插入一段列表值 auto it s.begin(); while (it ! s.end()) { cout *it ; it; } cout endl;而且如果这个列表里面有冗余的值也会去掉。set除了支持整形也支持字符串如下。代码语言javascriptAI代码解释setstring ss({ hello, eat, bad, cat }); auto it ss.begin(); while (it ! ss.end()) { cout *it ; it; } cout endl;字符串的话比较顺序是按照ASCII码顺序比的。这里还有一种写法。代码语言javascriptAI代码解释//setstring ss({ hello, eat, bad, cat }); setstring ss { hello, eat, bad, cat }; //另一种写法第一种写法就是直接调用构造函数第二种写法就是构造的隐式类型转换构造拷贝构造 优化成 构造。2.4.2 find和erasefind支持value_type的查找value_type就是T就是key。找到了就返回这个迭代器没找到就返回endend就是最后一个位置的后一个位置。删除有三个接口。传迭代器过去删除某个位置的值。传一个值过去传的这个值可能在容器里也可能不在如果在就直接删除然后返回删除了几个数如果删除一个就返回1如果这个值不在容器里就会返回0因为删除了0个数。set每个数只有一个但是multiset有多个传迭代器区间过去删除一个区间的值。我们先给这个容器一些值并且打印出来。代码语言javascriptAI代码解释setint s { 3,1,5,6,4,9,2 }; for (auto e : s) { cout e ; } cout endl;比如说我们现在要删除最小值。直接传begin过去就可以。代码语言javascriptAI代码解释s.erase(s.begin()); //删除最小值因为s默认排升序第一个值就是最小值迭代器是左闭右开的就是begin。这里用到的就是第1个接口。这个接口的返回值是删除位置的后一个位置的迭代器。我们也可以输入一个值让他删除。代码语言javascriptAI代码解释int x; cin x; //输入一个值 int ret s.erase(x); //ret接收erase的返回值 if (ret 0) cout 此值不存在 endl; for (auto e : s) { cout e ; } cout endl;先输入一个存在的值。再输入一个不存在的值试试。不存在的话什么都不删。这里用到的就是第2个接口。第二个接口其实可以理解为是用find第一个接口来实现的如下。代码语言javascriptAI代码解释int x; cin x; //输入一个值 auto pos s.find(x);//先找值 if (pos ! s.end()) //找到了就删 { s.erase(pos); cout 删除成功 endl; } else cout 此值不存在 endl;迭代器区间删除在2.4.4里会说。删除后迭代器失效问题这里删除数据绝对会导致迭代器失效。失效有两种情况一是导致野指针问题二是删除后迭代器意义改变。具体分析需要结合底层。比如说我们删除一个数之后再访问这个迭代器vs平台下是一定会报错的。2.4.3 countcount就是传一个value_type然后返回这个值在容器里的个数。虽然set里的值有就是1没有就是0是要和multiset保持一致因为multiset里不仅是有没有这个值他还可能有多个。count确定某个值在不在会比find更方便。代码语言javascriptAI代码解释setint s { 3,1,5,6,4,9,2 }; for (auto e : s) { cout e ; } cout endl; int x; cin x; //输入一个值 if (s.count(x)) //非0就存在 { cout x 存在 endl; } else { cout x 不存在 endl; }2.4.4 lower_bound 和 upper_boundlower_bound 是 返回⼤于等于val位置的迭代器upper_bound 是 返回⼤于val位置的迭代器。这样设计是为了方便我们找一段迭代器区间因为只要是迭代器区间就必须是左闭右开的。比如说现在有一堆值如下。代码语言javascriptAI代码解释setint s { 10, 20, 30, 40, 50, 60, 70, 80, 90 };现在要求 : 1. 删除[30, 50]区间的值 2. 删除[25, 65]之间的值 。先看第一个。删30到50之间的值但是迭代器区间只能是左闭右开左闭能删除右开怎么办代码语言javascriptAI代码解释setint s { 10, 20, 30, 40, 50, 60, 70, 80, 90 }; //删除[30,50] auto left s.lower_bound(30); //左闭给upper_bound传50过去upper_bound返回比50大的第一个迭代器。代码语言javascriptAI代码解释setint s { 10, 20, 30, 40, 50, 60, 70, 80, 90 }; //删除[30,50] auto left s.lower_bound(30); //左闭 返回 30 auto right s.upper_bound(50);//右开 返回 50这里正好有30就返回30返回比50大的第一个迭代器6060是开区间。然后我们删掉这个区间。这里就用到了前面没说的删除的第三个接口传迭代器区间。代码语言javascriptAI代码解释s.erase(left, right); //删除 for (auto e : s) { cout e ; } cout endl;再看第二个删除25到65之间的值。25和65都不在这个容器里怎么办还是一样的lower_bound传25过去没有25就返回比25大的第一个迭代器给upper_bound传65过去upper_bound返回比65大的第一个迭代器。代码语言javascriptAI代码解释setint s { 10, 20, 30, 40, 50, 60, 70, 80, 90 }; //删除[25,65] auto left s.lower_bound(25); //左闭 返回 25 auto right s.upper_bound(65);//右开 返回 65 s.erase(left, right); //删除 for (auto e : s) { cout e ; } cout endl;3.set和multiset的差别multiset的使用不需要再包含别的头文件就是#include set。multiset和set的使⽤基本完全类似主要区别点在于multiset⽀持值冗余。那么insert / find / count / erase都围绕着⽀持值冗余有所差异。insert相⽐set的不同的是multiset的支持插入已经存在的值。count相⽐set的不同的是multiset的会返回x的实际个数。代码语言javascriptAI代码解释multisetint ms { 2,5,4,7,6,8,2,1,5,2 }; for (auto e : ms) { cout e ; } cout endl; cout ms.count(2) endl; cout ms.count(9) endl;2在容器里有3个count就返回39不在容器里就返回0。find不同的是multiset里的x可能会存在多个如果有多个find查找的是中序的第⼀个。比如说下面这颗树我们找3但是有两个3。这棵树不平衡只是举例说明什么叫中序第一个可以自己可以走一遍中序遍历会发现框起来的3是中序遍历的第一个3就返回它。返回中序的第一个我们就可以把所有相同的值全打印出来。代码语言javascriptAI代码解释auto tar ms.find(2); while (tar ! ms.end() *tar 2) { cout *tar ; tar; } cout endl;erase不同的是multiset的erase给值时会删除所有的x。代码语言javascriptAI代码解释ms.erase(2); for (auto e : ms) { cout e ; } cout endl;4.相关练习4.1 两个数组的交集349. 两个数组的交集 - 力扣LeetCode这个题的思路先用set去重排序然后用两个指针比较两个数组的值相同的就放到一起。代码语言javascriptAI代码解释vectorint intersection(vectorint nums1, vectorint nums2) { setint s1, s2; vectorint ret; for (auto e : nums1) s1.insert(e); for (auto e : nums2) s2.insert(e); }代码语言javascriptAI代码解释vectorint intersection(vectorint nums1, vectorint nums2) { setint s1, s2; vectorint ret; for (auto e : nums1) s1.insert(e); for (auto e : nums2) s2.insert(e); auto it1 s1.begin(); auto it2 s2.begin(); }相同就放到ret里然后同时往后移动不同的话谁小谁就后移。代码语言javascriptAI代码解释vectorint intersection(vectorint nums1, vectorint nums2) { setint s1, s2; vectorint ret; for (auto e : nums1) s1.insert(e); for (auto e : nums2) s2.insert(e); auto it1 s1.begin(); auto it2 s2.begin(); while (it1 ! s1.end() it2 ! s2.end()) { if (*it1 *it2) { ret.push_back(*it1); //相同就放到ret it1; it2; } else if (*it1 *it2) it2; else it1; } return ret; }最后返回ret就行。4.2 环形链表142. 环形链表 II - 力扣LeetCode这道题用set写就会特别简单思路遍历这个链表把节点的地址存到set里如果出现相同的结点地址就是带环否则不带环。存的是地址不是值因为不同的节点可能存在值相同当我们遍历到-4时前面这4个节点地址都没出现重复继续遍历。-4节点的下一个是2。因为2的地址出现了两次所以直接就可以判断为带环。代码实现如下。代码语言javascriptAI代码解释class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode *cur head; setListNode* s; while(cur) { if(s.count(cur)) return cur; else s.insert(cur); cur cur-next; } return nullptr; } };