c++:刷题必备--容器set的使用.功能:查找,去重和排序.

容器set的使用

构造+插入数据

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

int main()
{
	//8, 3, 1, 10, 6, 4, 7, 14, 13
	
	//set<int> m = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };

	set<int> m;
	
	m.insert(8);
	m.insert(3);
	m.insert(1);
	m.insert(10);
	m.insert(6);
	m.insert(4);
	m.insert(14);
	m.insert(13);

	//用迭代器遍历
	//set<int>::iterator it = m.begin();
	//while (it != m.end())
	//{
	//	cout << (*it) << endl;
	//	it++;
	//}
	//范围for遍历
	for (auto e : m)
	{
		cout << e << " ";
	}

	return 0;
}

set的使用其实很简单.它的底层是一个自平衡二叉树,也就是AVL树和红黑树,
我们不断的插入值,它就会生成一个二叉树.

这个二叉树与其他普通二叉树不一样,
根的左子树永远比根的值小,根的右子树永远比根的值大
加上二叉树默认有去重功能,不能存储一样的数据

插入=>去重

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

int main()
{
	//8, 3, 1, 10, 6, 4, 7, 14, 13
	set<int> m;
	
	m.insert(8);
	m.insert(3);
	m.insert(1);
	m.insert(1);
	m.insert(1);
	m.insert(1);
	m.insert(1);
	m.insert(1);
	m.insert(1);
	m.insert(10);
	m.insert(6);
	m.insert(4);
	m.insert(14);
	m.insert(13);
	//范围for遍历
	for (auto e : m)
	{
		cout << e << " ";
	}

	return 0;
}

功利点来说,这个功能可以用在刷题上面

leetcode 349.两个数组的交集
比如这个题目,寻找交集,而给的两个数组中又有重复的内容,我们需要先去重,再寻找交集.

删除

int main()
{
	//8, 3, 1, 10, 6, 4, 7, 14, 13
	set<int> m;
	
	m.insert(8);
	m.insert(3);
	m.insert(1);
	m.insert(10);
	m.insert(6);
	m.insert(4);
	m.insert(14);
	m.insert(13);
	//范围for遍历
	for (auto e : m)
	{
		cout << e << " ";
	}
	cout << endl;

	m.erase(10);
	for (auto e : m)
	{
		cout << e << " ";
	}
	cout << endl;

	m.erase(13);
	for (auto e : m)
	{
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

排序

因为它的底层是一个自平衡二叉树,它本身就是有序的.

根的左子树永远比根的值小,根的右子树永远比根的值大.
我们只需要通过中序遍历(左子树 根 右子树)递归下去.
幸运的是,我们不需要自己写递归,因为底层的迭代器帮我们把活干了,我们只需要显示调用迭代器或者范围for调用就能做到排序的功能

	//显示调用迭代器
	set<int>::iterator it = m.begin();
	while (it != m.end())
	{
		cout << *it << " ";
		++it;
	}
	//范围for遍历
	for (auto e : m)
	{
		cout << e << " ";
	}
	cout << endl;

查找

void test_set2()
{
	set<int> m = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	for (auto e : m)
	{
		cout << e << " ";
	}
	cout << endl;
	
	//两种都可以
	//set<int>::iterator pos = m.find(1);
	auto pos = m.find(1);
	m.erase(pos);
	for (auto e : m)
	{
		cout << e << " ";
	}
	cout << endl;
}
int main()
{
	test_set2();
	return 0;
}

查找这个函数跟调用其他函数一样
找得到的话给你传那个位置的迭代器,用auto或者显示接收都行
找不到的话传给你m的终点m.end()

map的查找是logN,时间复杂度极低.10亿次的数据只需要查找30次.