【C++】set和multiset的常用接口详解

 
          前⾯我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，本篇文章将先容一下set和multiset的利用。    1. 序列式容器和关联式容器

        在先容set之前我们先简朴先容一下什么是序列式容器和关联式容器。
   前⾯我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间⼀般没有紧密的关联关系，⽐如交换⼀下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。
      关联式容器也是⽤来存储数据的，与序列式容器差别的是，关联式容器逻辑结构通常是  ⾮线性结构，两个位置有紧密的关联关系，交换⼀下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列unordered_map/unordered_set系列。   set是key搜刮场景的结构。 
 
2. set系列的使⽤

2.1 set和multiset参考⽂档

参考文档：<set> - C++ Reference
先来总体看一下set的相关接口。

 总的来说还是之前我们在vector，string接触过的那些东西。固然看起来接口很多，但常用的以及会学习到的就那些。
 
2.2 set类的先容

set的声明如下。

   

• 参数1：T就是set底层关键字的类型。这个T就是key，名字差别。
  
• 参数2：set默认要求T⽀持⼩于⽐较，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现仿函数传给第⼆个模版参数。
  
• 参数3：set底层存储数据的内存是从空间配置器申请的（空间配置器），如果需要可以⾃⼰实现内存池，传给第三个参数。
  

  ⼀般情况下，我们都不需要传后两个模版参数。
  set底层是⽤红⿊树（以后会先容）实现，增删查服从是O（

） ，迭代器遍历是⾛的搜刮树的 中序，所以是有序的。       2.3 set的构造和迭代器

先看它的构造函数。
  

 再来看看他的迭代器。

• 从文档先容可以看出这是一个双向迭代器，⽀持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是⼆叉搜刮树，迭代器遍历⾛的中序。
  
• ⽀持迭代器就意味着⽀持范围for，set的iterator和const_iterator都不⽀持迭代器修改数据，修改关键字数据，破坏了底层搜刮树的结构。
  

 
2.4 set的增删查（不支持改）

2.4.1 insert

 
先看insert，增。

增这里起首支持增加一个value_type类型的东西，value_type什么？

 从这里可以看到，实在就是我们传的谁人关键字Key，而且上面谁人key_type也是key。所以就是插入一个key。这里的返回值类型后面会说，临时不关注。
 用set的时间要包含头文件#include <set>

1. #include <iostream>
2. #include <set>
3. using namespace std;
4. int main()
5. {
6.         set<int> s;
7.         s.insert(2);
8.         s.insert(1);
9.         s.insert(4); //重复
10.         s.insert(3);
11.         s.insert(4); //重复
12.         return 0;
13. }

复制代码

第二个参数不传的话，默认排升序。

用迭代器遍历一下。

1. int main()
2. {
3.         set<int> s;
4.         s.insert(2);
5.         s.insert(1);
6.         s.insert(4);
7.         s.insert(3);
8.         s.insert(4);
10.         auto it = s.begin();
11.         while (it != s.end())
12.         {
13.                 cout << *it << ' ';
14.                 it++;
15.         }
16.         cout << endl;
17.         return 0;
18. }

复制代码

  如果这里不用auto的话，就是  set<int>::iterator it = s.begin(); 

可以看到此时的s就是一个去重而且升序的状态。
 
如果想变成降序，set的参数列表就多传一个参数。

1. set<int, greater<int>> s;

复制代码

此时的s就是去重而且排降序。
 
还支持在某个位置插入，一般不用。

支持插入一段迭代器区间。

 
还支持插入initializer_list。

 就是用大括号括起来插入。

1. set<int> s;
2. s.insert(2);
3. s.insert(1);
4. s.insert(4);
5. s.insert(3);
6. s.insert(4);
7. s.insert({ 7, 5, 8, 6 }); //插入一段列表值
9. auto it = s.begin();
10. while (it != s.end())
11. {
12.         cout << *it << ' ';
13.         it++;
14. }
15. cout << endl;

复制代码

 而且如果这个列表里面有冗余的值，也会去掉。

 
set除了支持整形，也支持字符串，如下。

1. set<string> ss({ "hello", "eat", "bad", "cat" });
2. auto it = ss.begin();
3. while (it != ss.end())
4. {
5.         cout << *it << ' ';
6.         it++;
7. }
8. cout << endl;

复制代码

字符串的话比较顺序是按照ASCII码顺序比的。

 
 这里另有一种写法。

1. //set<string> ss({ "hello", "eat", "bad", "cat" });
3. set<string> ss = { "hello", "eat", "bad", "cat" }; //另一种写法

复制代码

第一种写法就是直接调用构造函数，第二种写法就是构造的隐式类型转换，构造+拷贝构造 优化成 构造。
 
2.4.2 find和erase

 find支持value_type的查找，value_type就是T就是key。

找到了就返回这个迭代器，没找到就返回end，end就是最后一个位置的后一个位置。 
删除有三个接口。

   

• 传迭代器过去，删除某个位置的值。
  
• 传一个值过去，传的这个值可能在容器里，也可能不在，如果在，就直接删除，然后返回删除了几个数，如果删除一个就返回1；如果这个值不在容器里，就会返回0，因为删除了0个数。（set每个数只有一个，但是multiset有多个）
  
• 传迭代器区间过去，删除一个区间的值。
  

   我们先给这个容器一些值，而且打印出来。

1. set<int> s = { 3,1,5,6,4,9,2 };
2. for (auto e : s)
3. {
4.         cout << e << " ";
5. }
6. cout << endl;

复制代码

比如说我们如今要删除最小值。直接传begin过去就可以。

1. s.erase(s.begin()); //删除最小值

复制代码

因为s默认排升序，第一个值就是最小值，迭代器是左闭右开的，就是begin。

这里用到的就是第1个接口。这个接口的返回值是删除位置的后一个位置的迭代器。
 
我们也可以输入一个值让他删除。

1. int x;
2. cin >> x; //输入一个值
3. int ret = s.erase(x); //ret接收erase的返回值
4. if (ret == 0)
5.         cout << "此值不存在" << endl;
6. for (auto e : s)
7. {
8.         cout << e << " ";
9. }
10. cout << endl;

复制代码

先输入一个存在的值。 

 再输入一个不存在的值试试。

不存在的话什么都不删。这里用到的就是第2个接口。
第二个接口实在可以明白为是用find+第一个接口来实现的，如下。

1. int x;
2. cin >> x; //输入一个值
3. auto pos = s.find(x);//先找值
4. if (pos != s.end()) //找到了就删
5. {
6.         s.erase(pos);
7.         cout << "删除成功" << endl;
8. }
9. else
10.         cout << "此值不存在" << endl;

复制代码

迭代器区间删除在2.4.4里会说。
 
 删除后迭代器失效问题
这里删除数据绝对会导致迭代器失效。失效有两种情况，一是导致野指针问题，二是删除后迭代器意义改变。具体分析需要联合底层。比如说我们删除一个数之后再访问这个迭代器，vs平台下是一定会报错的。

 

 2.4.3 count

 count就是传一个value_type，然后返回这个值在容器里的个数。固然set里的值有就是1，没有就是0，是要和multiset保持一致，因为multiset里不仅是有没有这个值，他还可能有多个。
count确定某个值在不在会比find更方便。

1. set<int> s = { 3,1,5,6,4,9,2 };
2. for (auto e : s)
3. {
4.         cout << e << " ";
5. }
6. cout << endl;int x;cin >> x; //输入一个值if (s.count(x)) //非0就存在{        cout << x << "存在" << endl;}else{        cout << x << "不存在" << endl;}

复制代码

 

2.4.4 lower_bound 和 upper_bound

   

• lower_bound 是 返回⼤于等于val位置的迭代器；upper_bound 是 返回⼤于val位置的迭代器。
  
• 这样计划是为了方便我们找一段迭代器区间，因为只要是迭代器区间，就必须是左闭右开的。
  

  比如说如今有一堆值，如下。

1. set<int> s = { 10, 20, 30, 40, 50, 60, 70, 80, 90 };

复制代码

如今要求 : 1. 删除[30, 50]区间的值   2. 删除[25, 65]之间的值 。
 
先看第一个。删30到50之间的值，但是迭代器区间只能是左闭右开，左闭能删除，右开怎么办？

1. set<int> s = { 10, 20, 30, 40, 50, 60, 70, 80, 90 };//删除[30,50]auto left = s.lower_bound(30); //左闭

复制代码

给upper_bound传50过去，upper_bound返回比50大的第一个迭代器。

1. set<int> s = { 10, 20, 30, 40, 50, 60, 70, 80, 90 };//删除[30,50]auto left = s.lower_bound(30); //左闭 返回 >=30auto right = s.upper_bound(50);//右开 返回 >50

复制代码

这里恰好有30，就返回30；返回比50大的第一个迭代器，60，60是开区间。
然后我们删掉这个区间。这里就用到了前面没说的删除的第三个接口，传迭代器区间。

1. s.erase(left, right); //删除
2. for (auto e : s)
3. {
4.         cout << e << " ";
5. }
6. cout << endl;

复制代码

 
再看第二个，删除25到65之间的值。25和65都不在这个容器里，怎么办？还是一样的，lower_bound传25过去，没有25就返回比25大的第一个迭代器，给upper_bound传65过去，upper_bound返回比65大的第一个迭代器。

1. set<int> s = { 10, 20, 30, 40, 50, 60, 70, 80, 90 };//删除[25,65]auto left = s.lower_bound(25); //左闭 返回 >=25auto right = s.upper_bound(65);//右开 返回 >65s.erase(left, right); //删除
2. for (auto e : s)
3. {
4.         cout << e << " ";
5. }
6. cout << endl;

复制代码

 

3.set和multiset的差别

multiset的利用不需要再包含别的头文件，就是#include <set>。
  multiset和set的使⽤根本完全类似，主要区别点在于 multiset⽀持值冗余。  

 那么insert / find / count / erase都围绕着⽀持值冗余有所差异。
 
insert相⽐set的差别的是，multiset的支持插入已经存在的值。

 
count相⽐set的差别的是，multiset的会返回x的实际个数。

1. multiset<int> ms = { 2,5,4,7,6,8,2,1,5,2 };
2. for (auto e : ms)
3. {
4.         cout << e << ' ';
5. }
6. cout << endl;
7. cout << ms.count(2) << endl;
8. cout << ms.count(9) << endl;

复制代码

2在容器里有3个，count就返回3，9不在容器里，就返回0。
 
  find差别的是，multiset里的x可能会存在多个，如果有多个，find查找的是 中序的第⼀个。     比如说下面这颗树，我们找3，但是有两个3。（这棵树不平衡，只是举例阐明什么叫中序第一个）  

可以自己可以走一遍中序遍历，会发现框起来的3是中序遍历的第一个3，就返回它。
返回中序的第一个，我们就可以把所有相同的值全打印出来。

1. auto tar = ms.find(2);
2. while (tar != ms.end() && *tar == 2)
3. {
4.         cout << *tar << " ";
5.         tar++;
6. }
7. cout << endl;

复制代码

 
 erase差别的是，multiset的erase给值时会删除所有的x。

1. ms.erase(2);
2. for (auto e : ms)
3. {
4.         cout << e << ' ';
5. }
6. cout << endl;

复制代码

 
4.相关训练

4.1 两个数组的交集

349. 两个数组的交集 - 力扣（LeetCode）
这个题的思绪：先用set去重+排序，然后用两个指针比较两个数组的值，相同的就放到一起。

1. vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
2. {
3.         set<int> s1, s2;
4.         vector<int> ret;
5.         for (auto e : nums1) s1.insert(e);
6.         for (auto e : nums2) s2.insert(e);
7. }

复制代码

1. vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
2. {
3.         set<int> s1, s2;
4.         vector<int> ret;
5.         for (auto e : nums1) s1.insert(e);
6.         for (auto e : nums2) s2.insert(e);
8.         auto it1 = s1.begin();
9.         auto it2 = s2.begin();
10. }

复制代码

相同就放到ret里，然后同时往后移动，差别的话，谁小谁就后移。

1. vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
2. {
3.         set<int> s1, s2;
4.         vector<int> ret;
5.         for (auto e : nums1) s1.insert(e);
6.         for (auto e : nums2) s2.insert(e);
8.         auto it1 = s1.begin();
9.         auto it2 = s2.begin();
11.         while (it1 != s1.end() && it2 != s2.end())
12.         {
13.                 if (*it1 == *it2)
14.                 {
15.                         ret.push_back(*it1); //相同就放到ret
16.                         it1++; it2++;
17.                 }
18.                 else if (*it1 > *it2) it2++;
19.                 else it1++;
20.         }
21.         return ret;
22. }

复制代码

 最后返回ret就行。
 
4.2 环形链表

142. 环形链表 II - 力扣（LeetCode）
 这道题用set写就会特殊简朴，思绪：遍历这个链表，把节点的地址存到set里，如果出现相同的结点地址，就是带环，否则不带环。（存的是地址不是值！因为差别的节点可能存在值相同）

当我们遍历到-4时，前面这4个节点地址都没出现重复，继续遍历。

-4节点的下一个是2。 

因为2的地址出现了两次，所以直接就可以判定为带环。代码实现如下。

1. class Solution {
2. public:
3.     ListNode *detectCycle(ListNode *head)
4.     {
5.         ListNode *cur = head;
6.         set<ListNode*> s;
7.         while(cur)
8.         {
9.             if(s.count(cur)) return cur;
10.             else s.insert(cur);
11.             cur = cur->next;
12.         }
13.         return nullptr;
14.     }
15. };

复制代码

 
本次分享就到这里了，我们下篇见~