【C++：map和set的使用】C++STL容器详解：set容器从使用到高频算法题实战

前面我们已经接触过STL中的部分容器比如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间一般没有紧密的关联关系，比如交换一下，依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。

关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系，交换一下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。

这部分艾莉丝要介绍的map和set底层是红黑树，红黑树是一颗平衡二叉搜索树。set是key搜索场景的结构，map是key / value搜索场景的结构。

2 ~> 了解set容器

2.1 set类介绍

1、set的声明如下，T就是set底层关键字的类型；

2、set对T要求比较大小，默认要求T支持小于比较的就可以了，如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模版参数；

3、set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参
数——这一点不需要管；

4、一般情况下，我们都不需要传后两个模版参数；

5、set底层是用红黑树实现的，红黑树我们已经知道是平衡二叉树，增删查效率是O(logN) ，迭代器遍历是走的搜索树的中序，左根右，所以是有序的；

6、前面部分我们已经介绍了vector / list等容器的使用，因为STL容器接口设计高度相似，所以这里我们就不再一个接口一个接口的介绍，而是直接带大家看文档，挑比较重要的接口进行介绍。

template < class T, // set::key_type/value_type class Compare = less<T>, // set::key_compare/value_compare class Alloc = allocator<T> // set::allocator_type > class set;

2.2 看set文档

set的支持正向和反向迭代遍历（至少是双向迭代器），遍历默认按升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，set的iterator和const_iterator都不支持迭代器修改数据，修改关键字数据，会破坏底层搜索树的结构。

2.2.1 set的构造和迭代器

// empty (1) 无参默认构造 explicit set(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); // range (2) 迭代器区间构造 template <class InputIterator> set(InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type & = allocator_type()); // copy (3) 拷贝构造 set(const set& x); // initializer list (5) initializer 列表构造 set(initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); // 迭代器是一个双向迭代器 iterator->a bidirectional iterator to const value_type // 正向迭代器 iterator begin(); iterator end(); // 反向迭代器 reverse_iterator rbegin(); reverse_iterator rend();

2.2.2 拷贝构造

set的拷贝构造都是深拷贝，代价极大。

3 ~> set的使用层详解

3.1 增删查

3.1.1 增：insert插入

3.1.2 删：erase删除

erase是直接把值删掉——

3.1.3 查

3.1.4 单纯判断在不在：count

判断在不在很方便，在就返回0，不在返回非0——

3.1.5 lower_bound和upper_bound

3.2 insert和迭代器遍历

3.2.1 代码实现

set遍历完自带去重和有序（中序遍历）——

3.2.2 运行演示

3.3 find和erase

3.3.1 代码实现

用范围for打印一下删除之后的数组，对比一下——

3.3.2 运行演示

这里我们删除一个6看看——

3.4 multiset

3.4.1 和set之间的差异

multiset和set的使用基本完全类似，主要区别点在于multiset支持值冗余。

3.4.2 代码实现

// multiset void Test_set3() { multiset<int> s; s.insert(3); s.insert(4); s.insert(6); s.insert(5); s.insert(3); s.insert(6); s.insert(7); s.insert(9); s.insert(3); // 遍历结果：去重 set<int>::iterator it = s.begin(); while (it != s.end()) { //*it = 1; // 报错不准确，不是常量的问题，而是不能修改*it，it可以修改 cout << *it << " "; ++it; } cout << endl; // 查找中序遍历中第一个3 auto pos = s.find(3); while (pos != s.end() && *pos == 3) { cout << *pos << endl; pos++; } cout << endl; // [) —— 左闭右开 //std::pair<multiset<int>::iterator, multiset<int> ::iterator> ret = s.equal_range(3); //// 返回左闭右开的区间 auto ret = s.equal_range(3); cout << s.count(3) << endl; cout << s.erase(3) << endl; // 删除所有3 for (auto e : s) { cout << e << " "; } cout << endl; }

3.4.3 查找多个key

比如查找3这个节点，如果有多个3节点，会查找中序遍历的第一个3节点——

3.4.4 equal_range

pair是库里面的类模板的结构，只是按struct公有定义——

左闭右开，pair(It1 , It2)，里面是迭代器，但是只有在类内部才能写迭代器。

3.4.5 count函数

count函数的功能：指定值在迭代器范围内的出现次数。

3.4.6 运行演示

我们以删除3为例，运行一下——

3.5 交集和差集的作用：数据同步和数据备份

3.5.1 图示：数据同步和数据备份

3.5.2 博主手记

3.6 博主手记

4 ~> set算法题练习

4.1 两个数组的交集

力扣链接：349. 两个数组的交集

力扣题解链接：使用哈希数组解决【两个数组的交集的问题】

题目描述：

4.1.1 C++实现

class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { // 去重 set<int> s1(nums1.begin(),nums1.end()); set<int> s2(nums2.begin(),nums2.end()); vector<int> v; auto it1 = s1.begin(); auto it2 = s2.begin(); while(it1 != s1.end() && it2 != s2.end()) { if(*it1 < *it2) { it1++; } else if(*it1 > *it2) { it2++; } else{ v.push_back(*it1); ++it1; ++it2; } } return v; } };

4.1.2 图示：交集 && 差集

4.1.3 博主手记

4.2 环形链表

力扣链接：LCR 022. 环形链表 II

力扣题解链接：