【C++】set 容器最全解析（什么是 set? set容器的常用接口有那些？）
目录
一、前言
二、预备知识
💢关联式容器💢
💢键值对💢
💢树型结构的关联式容器💢
三、set 详解
🔥 什么是 set ?
🔥set 模板参数列表
🔥set 的构造
🔥set 的使用
🍋insert
🍓find
🍇erase
🥝swap
🍐 empty
🍒size
🍈count
🍌 lower_bound
🍍upper_bound
🍉set 的降序使用
🔥set 的特点
🔥set 和 vector 的对比
四、常考面试题
五、共勉
一、前言
set是STL中的容器之一，不同于普通容器，它的查找速度极快，常用来存储各种经常被检索的数据，因为容器的底层是平衡二叉搜索树中的红黑树。除此之外，还可以借助其特殊的性质，解决部分难题
二、预备知识
在正式学习
set之前，首先要有一些预备知识，否则后面可能看不懂相关操作
💢关联式容器💢
在以往的 【
STL容器】学习中，我们接触到的都是 序列式容器，比如string、vector、list、deque等，序列式容器的特点就是 底层为线性序列的数据结构，就比如list，其中的节点是 线性存储 的，一个节点存储一个元素，其中存储的元素都可序，但未必有序
- 【关联式容器】 则比较特殊，其中存储的是
<key, value>的 键值对，这就意味着可以按照 键值大小key以某种特定的规则放置于适当的位置，关联式容器 没有首尾的概念，因此没有头插尾插等相关操作，本文中学习的set就属于 关联式容器
注意： stack、queue 等适配器也属于序列式容器，因为他们的底层是 deque 等容器
💢键值对💢
【键值对】是 一种用来表示具有一一对应关系的结构，该结构中一般只包含两个成员变量：
key和value，前者表示 键值，后者表示 实值 关联式容器的实现离不开【键值对】
因此在标准库中，专门提供了这种结构 pair 定义如下 ：
//SGI 版 STL 中的实现
template <class T1, class T2>
struct pair {typedef T1 first_type;typedef T2 second_type;T1 first; T2 second; pair() : first(T1()), second(T2()) {}pair(const T1& a, const T2& b) : first(a), second(b) {}#ifdef __STL_MEMBER_TEMPLATEStemplate <class U1, class U2>pair(const pair<U1, U2>& p) : first(p.first), second(p.second) {}
#endif
};
pair中的first表示 键值，second则表示 实值，在给 【关联式容器】 中插入数据时，可以构建pair对象
比如下面就构建了一个 键值
key为string，实值value为int的匿名 键值对pair对象
pair<string, int>("hehe", 123);
- 可以将此匿名对象传入 关联式容器 中，当然这样写未免过于麻烦了，于是库中设计了一个函数模板
make_pair，可以根据传入的参数，去调用pair构建对象并返回
make_pair("hehe", 123); //构建出的匿名对象与上面的一致
make_pair的定义如下所示：
template <class T1,class T2>
pair<T1,T2> make_pair (T1 x, T2 y)
{return ( pair<T1,T2>(x,y) );
}
- 该函数实际会被编译器优化为 内联函数，因此不会造成过多消耗，可以放心使用
💢树型结构的关联式容器💢
所以在
C++标准中，共提供了四种 树型结构的关联式容器
setmultisetmapmultimap
关于 哈希结构的关联式容器 将在 哈希表 中学习
树型结构与哈希结构的关联式容器功能都是一模一样的，不过 哈希结构查找比树型结构快得多 -> O(1)
注：
STL中选择的树型结构为 红黑树RB-Tree- 树型结构中的元素 中序遍历 后有序，而哈希结构中的元素无序
三、set 详解
🔥 什么是 set ?
【set】 是按照一定顺序存储的容器
- 在 set 中，元素的 value 也标识它（value就是key，类型为T），并且每个value必须是唯一的。set中的元素不能在容器中修改（元素总是 const 类型），但是可以从容器中插入或者删除它们。
- 在内部，set 中的元素总是按照其内部比较对象（类型为Compare）所指示的特定严格弱排序准则进行排序。
- set 容器通过 key 访问单个元素的速度比 unordered_set 容器慢，但 set 容器允许根据顺序对子集进行直接迭代
- set 在底层是用二叉搜索树（红黑树）实现的。
注意点：
- set 中 插入元素时，只需要插入 value 即可，不需要构造键值对
- set 中的元素不可以重复（因此可以使用 set 去重）
- 使用 set 的迭代器遍历 set 中的元素，可以得到有序序列
- set 中的元素默认按照 升序 来排序
- set 中的查找某个元素，时间复杂度为 ：log N
- 与 map/multimap不同 ，map/multimap 中存储的时真正的键值对 <key，value>，set 中只放 value，但是底层实际存放的是由 <key，value> 构成的键值对
- set 中的元素不允许修改，因为 set 在底层是用二叉搜索树来实现的，若是二叉搜索树当中的某个元素值进行了修改，那么这棵树将不再是二叉查找树。
🔥set 模板参数列表
如下图所示：
- T ： set中存放元素的类型，实际在底层存储 <value, value> 的键值对。
- Compare ：set中元素默认按照小于来比较。
- Alloc ：set中元素空间的管理方式，使用STL提供的空间配置器管理。
🔥set 的构造
这里主要有三种方式：
（1）无参构造空容器
set<int> s1; // 构造一个int类型的空容器
（2）拷贝构造某类型容器
set<int> s2(s1); // 拷贝构造int类型s1容器的复制品
（3）使用迭代器区间进行初始化构造
vector<int> v1 = { 1,2,3,4,5 };
set<int> s3(v1.begin(), v1.end()); // 构造vector对象某段区间的复制品
🔥set 的使用
set的成员函数主要分为：迭代器，容量操作，修改操作。
- 需要注意的是，对于 set 而言，它的普通迭代器和const迭代器都不支持修改。
我这里只举几个常用的，其它可以看文档学习。
🍋insert
在 set 中插入元素 val ，实际插入的是 <val，val> 构成的键值对
- 如果插入成功，返回 <val在set中的位置， true>
- 如果插入失败，说明 val 在set中已经存在,返回 <val在set中的位置， false>
代码示例：
void testset()
{set<int> s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(2);s.insert(1);s.insert(3);s.insert(3);// 遍历for (auto e : s){cout << e << " ";}
}
- 可以看到当插入元素重复元素时，set 会自动过滤掉，并对已有的元素进行排序
🍓find
在容器中搜索查找 val 元素，如果找到，则返回一个迭代器，否则返回 set::end 的迭代器
代码示例：
void testset()
{set<int> s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(2);s.insert(1);s.insert(3);s.insert(3);set<int>::iterator pos = s.find(5);if (pos != s.end()){cout << "找到了" << endl;}
}
🍇erase
删除 set 中的元素，这里有3种删除方式
（1）从 set 容器中删除单个元素（搭配 find 使用）
void testset()
{set<int> s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(6);s.insert(3);s.insert(8);s.insert(7);auto pos = s.find(5);if (pos != s.end()){s.erase(pos); // 删除元素5cout << "删除成功" << endl;}else{cout << "删除失败" << endl;}// 遍历for (auto e : s){cout << e << " ";}
}
（2）从set 容器中删除单个元素（直接传入要删除的元素）
void testset()
{set<int> s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(6);s.insert(3);s.insert(8);s.insert(7);s.erase(5);// 遍历for (auto e : s){cout << e << " ";}
}
那么它和 第1种 的区别是什么呢?
- erase(x) ：如果x存在就删除；如果不存在，不做任何改变
- erase(pos) ：如果x存在就删除;如果不存在，此时pos位置指向set::end的迭代器，那么程序运行就会报错。
实这种方式本质上可以理解为 erase 去调用了迭代器和 find 。
(3) 从 set 容器中删除一组元素（传的是迭代器区间【first，last)）
void testset()
{set<int> s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(6);s.insert(3);s.insert(8);s.insert(7);auto pos = s.find(5);if (pos != s.end()){s.erase(pos, s.end()); // 从5开始所有的元素全部删除cout << "删除成功" << endl;}else{cout << "删除失败" << endl;}// 遍历for (auto e : s){cout << e << " ";}
}
- 可以看到从 5 开始所有的元素都已经被删除了
🥝swap
交换 set 容器中的元素
void testset()
{set<int> s1;s1.insert(4);s1.insert(5);s1.insert(2);s1.insert(1);set<int> s2;s2.insert(6);s2.insert(3);s2.insert(8);s2.insert(7);s1.swap(s2);cout << "s1:";// 遍历for (auto e1 : s1){cout << e1 << " ";}cout << "s2:";// 遍历for (auto e2 : s2){cout << e2 << " ";}
}
- 可以看到 s1 和 s2 的元素已经被交换了
🍐 empty
判断 set 容器是否为空，空返回 ture，非空飞回 false
void testset()
{set<int> s1;s1.insert(4);s1.insert(5);s1.insert(2);s1.insert(1);set<int> s2;cout << s1.empty() << endl; // s1容器不为空,输出0cout << s2.empty() << endl; // s2容器为空,输出1
}
🍒size
返回 set 中的有效元素个数
void testset()
{set<int> s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(6);s.insert(3);s.insert(8);s.insert(7);// 打印元素个数cout << s.size() << endl;
}
🍈count
返回 set 中值为 x 的元素的个数
void testset()
{set<int> s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(6);s.insert(3);s.insert(8);s.insert(7);// 元素3的个数cout << s.count(3) << endl;// 元素7的个数cout << s.count(10) << endl;
}
- 这个接口对于 set 容器其实没有太大用处，因为 set 当中每个value 都是唯一的
🍌 lower_bound
返回一个指向容器中第一个元素的迭代器，该迭代器不被认为在val之前(它是等于或在val之后)
- 其实就是，返回大于等于val位置的迭代器。
void testset()
{set<int> s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(3);s.insert(8);s.insert(7);// 如果3存在就返回3位置的迭代器auto lowIt = s.lower_bound(3);cout << *lowIt << endl;// 如果6不存在就返回比6大的位置的迭代器lowIt = s.lower_bound(6);cout << *lowIt << endl;
}
代码示例二：
void testset()
{set<int> s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(3);s.insert(8);s.insert(7);// 删除大于等于4的所有值auto lowIt = s.lower_bound(4);s.erase(lowIt, s.end());// 遍历for (auto e : s){cout << e << " ";}
}
- 可以看到所有 大于等于 4 的都被删除了
🍍upper_bound
返回指向容器中第一个元素的迭代器， 该元素被认为是val之后的元素。
- 也就是说，不管val存在还是不存在，都返回比val大的那个值。
void testset()
{set<int> s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(1);s.insert(3);s.insert(8);s.insert(7);// 如果3存在就返回大于3位置的迭代器auto lowIt = s.upper_bound(3);cout << *lowIt << endl;// 如果6不存在就返回比6大的位置的迭代器lowIt = s.upper_bound(6);cout << *lowIt << endl;
}
- 其实，lower_bound 和 upper_bound 可以搭配使用，删除元素中间的一段区间
void testset()
{set<int> s;// 插入元素s.insert(4);s.insert(5);s.insert(2);s.insert(6);s.insert(1);s.insert(3);s.insert(8);s.insert(7);// 删除 [3, 7] 这段区间中的所有数auto leftIt = s.lower_bound(3); // 返回3位置的迭代器auto rightIt = s.upper_bound(7); // 返回8位置的迭代器s.erase(leftIt, rightIt);// 遍历for (auto e : s){cout << e << " ";}
}
- 注意：erase 删除的迭代器区间是左闭右开，也就是说 right 是 8 位置的迭代器，但是 erase 只会删除到 7。
🍉set 的降序使用
可以通过改变
set模板参数2的方式，改变其中的顺序为 降序
#include <iostream>
#include <vector>
#include <set>
using namespace std;int main()
{vector<int> arr = { 7,3,6,9,3,1,6,2 };set<int, greater<int>> s1(arr.begin(), arr.end());for (auto e : s1)cout << e << " ";return 0;
}
🔥set 的特点
set具有以下特点：
🔥set 和 vector 的对比
vector是一个动态数组，它允许存储重复的元素，且元素存储的顺序是按插入顺序排列的
- 插入操作：在
vector的末尾插入元素的时间复杂度为O(1)，但如果你想在vector的中间插入元素，则需要O(n)的时间来移动元素。 - 查找操作：在
vector中查找元素通常需要O(n)的时间（除非你自己进行排序并使用二分查找）。
set是一个集合，它自动去重并保持元素的有序性
- 插入操作：在
set中插入元素的时间复杂度为O(log n)，并且插入后元素自动排序。 - 查找操作：在
set中查找元素的时间复杂度为O(log n)，比vector中的线性查找要高效得多。
使用场景
vector适用于需要频繁访问元素并且不关心元素顺序的场景，比如用来存储一组数据，然后你可以遍历、访问这些数据。set适用于需要存储唯一元素且需要快速查找或顺序访问的场景，比如你需要维护一个不重复的、有序的数据集合
四、常考面试题
题目 ：两个数组的交集
链接：349. 两个数组的交集 - 力扣（LeetCode）
解题思路：
- 对于求交集、并集、差集，其实有一种特定的方法，如下图所示：
class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {// 去掉num1当中重复的元素并排序set<int> s1;for (auto e1 : nums1){s1.insert(e1);}// 去掉num2当中重复的元素并排序set<int> s2;for (auto e2 : nums2){s2.insert(e2);}vector<int> ret; // 存放交集auto it1 = s1.begin(); // 指向s1的起始位置auto it2 = s2.begin(); // 指向s2的起始位置while (it1 != s1.end() && it2 != s2.end()) // 当s1和s2都没有遍历完时{if (*it1 < *it2) {it1++;}else if (*it2 < *it1){it2++;}else // 当it1和it2指向的元素相等时,就是交集{ret.push_back(*it1); // 把元素尾插到ret中,然后同时向后挪动it1++;it2++;}}return ret; // 返回交集}
};
五、共勉
以下就是我对 【C++】set 容器 的理解，如果有不懂和发现问题的小伙伴，请在评论区说出来哦，同时我还会继续更新【C++】，请持续关注我哦！！！
