Hellow! 铁子们，今天博主来介绍C++set的使用。赶紧来解锁set的使用吧，铁子们可以先去看看博主数据结构专栏里面的二叉搜索树，map/set底层就是基于二叉搜索树的变形--红黑树

1 set的使⽤

1. 1 序列式容器和关联式容器

前⾯我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这 些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间⼀般没有紧 密的关联关系，⽐如交换⼀下，他依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位 置来顺序保存和访问的。 关联式容器也是⽤来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是⾮线性结构， 两个位置有紧密的关联关系，交换⼀下，他的存储结构就被破坏了。顺序容器中的元素是按关键字来 保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。 map和set底层是红⿊树，红⿊树是⼀颗平衡⼆叉搜索树。set是key搜索场景的结构，map是key/value搜索场景的结构。平衡二叉树会在数据结构专栏介绍。

2 set系列的使⽤

1 set和multiset参考⽂档

https://legacy.cplusplus.com/reference/set/

2 set类的介绍

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

• set默认要求T⽀持⼩于⽐较，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现仿函数传给第⼆个模 版参数,传入比较仿函数实际上是改变二叉树的插入规则

• set底层存储数据的内存是从空间配置器申请的，如果需要可以⾃⼰实现内存池，传给第三个参数。

• ⼀般情况下，我们都不需要传后两个模版参数。

• set底层是⽤红⿊树实现，增删查效率是O(LogN)，迭代器遍历是⾛的搜索树的中序，所以是有序的。

3 传入仿函数的本质

传入比较仿函数实际上是改变二叉树的插入规则，如传入greate<int>仿函数实现二叉树底层的比较功能相当于把插入规则改成大于当前节点往左走，小于当前节点往右走，这样中序遍历出来的就是降序的。set默认就是升序的。

set<int> s;//set容器底层是搜索二叉树，中序遍历 默认升序 去重
				//重复的数据不插入，插入的set的数据就是关键字key不允许修改
vector<int> v = { 1,2,3,4,5,76,7,8 };
//支持花括号初始化插入,greater<int>仿函数控制二叉树的插入逻辑，使得中序遍历为降序
//less<int>升序
set<int,greater<int>> s1 = { 5,3,56,7,3,2,6,8,2,3,43,42,2,34,657,4 };

4 set的构造和迭代器

set的⽀持正向和反向迭代遍历，遍历默认按升序顺序，因为底层是⼆叉搜索树，迭代器遍历⾛的中 序；⽀持迭代器就意味着⽀持范围for，set的iterator和const_iterator都不⽀持迭代器修改数据，修改 关键字数据，破坏了底层搜索树的结构。不清楚什么是迭代器的铁子们可以去看看博主C++专栏里面的模拟实现string等容器，其实迭代器就是对指针的封装。

5 set使用样例

#include<iostream>
using namespace std;
#include<vector>
#include<set>

int main()
{
	set<int> s;//set容器底层是搜索二叉树，中序遍历 默认升序 去重
				//重复的数据不插入，插入的set的数据就是关键字key不允许修改
	vector<int> v = { 1,2,3,4,5,76,7,8 };
	//支持花括号初始化插入,greater<int>仿函数控制二叉树的插入逻辑，使得中序遍历为降序
	//less<int>升序
	set<int,greater<int>> s1 = { 5,3,56,7,3,2,6,8,2,3,43,42,2,34,657,4 };

	//支持迭代器初始化，给一个容器的迭代区间或者数组的一段区间的左右地址
	set<int> s4(v.begin(),v.end());
	s.insert(5);
	s.insert(2);
	s.insert(2);
	s.insert(2);//对于重复的key不插入
	s.insert(4);
	s.insert(8);
	s.insert(9);
	s.insert(0);
	s.insert(33);

	set<int>::iterator it = s.begin();//支持迭代器遍历，返回的是树中值最小的位置
	for (auto k : s4) {
		cout << k << " ";
	}
	cout << endl;

	for (auto k : s1) {
		cout << k << " ";
		}
	cout << endl;

	//基于算法库的查找，给起始位置的迭代器，暴力搜索
	auto i = find(s1.begin(), s1.end(), 3);
	//查找,找到了返回迭代器，没找到返回无效迭代器不能解引用
	//基于二分查找时间复杂度log(N)
	set<int>::iterator it1 = s1.find(2);
	cout << *it1 <<*i << endl;

	//删除:指定位置删，指定key删
	//没有就不删，指定key删返回删除的元素个数
	s.erase(s.begin());
	cout << s.erase(0) << endl;;
	for (auto k : s) {
		cout << k << " ";
	}
	cout << endl;

	//返回指定key的个数
	if (s.count(0)) {
		cout << "在" << endl;
	}
	else {
		cout << "不在" << endl;
	}

	//删除指定区间的值
	set<int> ss = { 10,20,30,40,50,65,67,70,80,90 };
	for (auto e : ss) {
		cout << e << " ";
	}
	cout << endl;
	//返回大于等于20的位置，没有指定值就找不该值大的第一个
	auto low_b = ss.lower_bound(20);
	//返回大于67的下一个位置，没有指定值就找不该值大的第一个
	set<int>::iterator up_b = ss.upper_bound(67);
	cout << *up_b << *low_b << endl;
	ss.erase(low_b,up_b);//删除区间左闭右开
	for (auto e : ss) {
		cout << e << " ";
	}
	cout << endl;

	//multiset允许插入重复值，中序遍历 默认升序 不去重

	multiset<int> ms = { 1,2,3,4,4,4,5,6,2,3,2 };
	for (auto m : ms) {
		cout << m << " ";
	}
	cout << endl;

	//返回中序遍历的第一个要寻找的值的位置，没有则返回无效迭代器
	multiset<int>::iterator ii = ms.find(2);
	//erase,删除所有指定元素
	ms.erase(4);

	for (auto m : ms) {
		cout << m << " ";
	}
}

6 multiset和set的差异

multiset和set的使⽤基本完全类似，主要区别点在于multiset⽀持值冗余，那么 insert/find/count/erase都围绕着⽀持值冗余有所差异，具体参看下⾯的样例代码理解。

#include<iostream>
#include<set>
using namespace std;
int main()
{
// 相⽐set不同的是，multiset是排序，但是不去重
multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 };
auto it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
// 相⽐set不同的是，x可能会存在多个，find查找中序的第⼀个
int x;
cin >> x;
auto pos = s.find(x);
while (pos != s.end() && *pos == x)
{
cout << *pos << " ";
++pos;
}
cout << endl;
// 相⽐set不同的是，count会返回x的实际个数
cout << s.count(x) << endl;
// 相⽐set不同的是，erase给值时会删除所有的x
s.erase(x);
for (auto e : s)
{
cout << e << " ";
}
cout << endl;
return 0;
}

本期收录于博主的专栏—-C++专栏，适用于编程初学者，感兴趣的朋友们可以订阅，查看博主其它对于C++学习的文章。

感谢每一个观看本篇文章的朋友，更多精彩敬请期待：小董 不懂  *(￣▽￣)°★*