cpp的set

一、关联式容器和键值对

1.关联式容器

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的
键值对，在数据检索时比序列式容器效率更高

2.键值对

用来表示具有一一对应关系的一种结构，key表示键，value表示值，key与value有对应的关系，比如字典，key表示英文单词，value表示中文翻译。

二、pair

pair是一种简单的数据结构，用于存储两个相关联的对象，内部包含两个元素一个是key一个是value两个元素都可以自定义类型，key可以用pair.first表示，value可以用pair.second表示

#include<iostream>
#include<utility>
#include<string>
using namespace std;
int main()
{
	pair<string, string> Pass;
	Pass.first = "apple";
	Pass.second = "苹果";
	cout <<"Pass.first :" << Pass.first << endl;
	cout << "Pass.second :" << Pass.second << endl;
	return 0;
}

三、树形结构的关联式容器

树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树(即红黑树)作为其底层结果，容器中的元素是一个有序的序列。下面一依次介绍每一个容器。

1.set

特点：

1、set是按照一定次序存储的容器。

2、set中的元素不能修改它总是被const修饰的，单可以插入和删除。

3、set中value和key是相同的，且每个value的值是唯一的，不存在两个相同的value值。

4、set的底层是通过红黑树实现的。

注意：

1、set与map/multimap不同，map/multimap中存储的是真正的键值对<key, value>，set中只放
value，但在底层实际存放的是由<value, value>构成的键值对。

2、在set插入一个元素时只需要传一个value值，不需要构造键值对。

3、set中的元素默认按照小于来比较。

4、set中的元素不能改变。

5、set中的元素不能重复（可用于去重）。

6、set的迭代器遍历set中的元素是中序，可以得到有序序列。

7、set中查找某个元素的时间复杂度是O（log n）。

使用：

1、set的模板参数

T: set中存放元素的类型，实际在底层存储<value, value>的键值对。

Compare：set中元素默认按照小于来比较

Alloc：set中元素空间的管理方式，使用STL提供的空间配置器管理

2、set的构造

（1）空容器构造函数（默认构造函数）
          构造一个没有元素的空容器。
（2） Range 构造函数
          构造一个容器，其中包含与范围 [first，last] 一样多的元素，每个元素都由该区域中的相应元素构造。
（3）复制构造函数
           使用 x 中每个元素的副本构造一个容器。

	set<int> Sei1;// 构造一个没有元素的空容器。
	set<int> s;
	s.insert(3);
	s.insert(1);
	s.insert(7);
	s.insert(9);
	s.insert(5);
	set<int> Sei2(s.begin(), s.end());//构造一个容器，其中包含与范围 [first，last] 一样多的元素，每个元素都由该区域中的相应元素构造。
	set<int> Sei3(s);
	cout << "s: ";
	for (const auto& i : s)
	{
		cout << i << ' ';
	}
	cout << endl;
	cout << "Sei2: ";
	for (const auto& i : Sei2)
	{
		cout << i << ' ';
	}
	cout << endl;
	cout << "Sei3: ";
	for (const auto& i : Sei3)
	{
		cout << i << ' ';
	}
	cout << endl;

3、set的插入 insert

通过插入新元素来扩展容器，从而有效地增加容器大小（按插入的元素数）。由于集中的元素是唯一的，因此插入操作会检查每个插入的元素是否等效于容器中已有的元素，如果是，则不会插入该元素，而是返回此现有元素的迭代器（如果函数返回值）。

set<int> si;
si.insert(5);//插入5
si.insert(7);//插入7

cout << "si: ";
for (const auto& i : si)
{
	cout << i << ' ';
}

4、set的删除erase

从集合容器中删除单个元素或一系列元素（[first，last）]。这实际上通过删除的元素数（被销毁）来减小容器大小。

	set<int> s;
	s.insert(3);
	s.insert(1);
	s.insert(7);
	s.insert(9);
	s.insert(5);
	cout << "s: ";
	for (const auto& i : s)
	{
		cout << i << ' ';
	}
	cout << endl;
	s.erase(4);//删除一个不存在的元素
	s.erase(1);
	s.erase(5);
	cout << "s: ";
	for (const auto& i : s)
	{
		cout << i << ' ';
	}
	cout << endl;

5、set的清除clear

从设置的容器中删除所有元素（已销毁），使容器的大小为 0。

	set<int> s;
	s.insert(3);
	s.insert(1);
	s.insert(7);
	s.insert(9);
	s.insert(5);
	cout << "s: ";
	for (const auto& i : s)
	{
		cout << i << ' ';
	}
	cout << endl;
	cout << "s: ";
	s.clear();//清除所有元素
	for (const auto& i : s)
	{
		cout << i << ' ';
	}
	cout << endl;

6、set的查找find

在容器中搜索等效于 val 的元素，如果找到，则返回一个迭代器，否则返回一个迭代器 set：：end。如果容器的比较对象反射性地返回 false（即，无论元素作为参数传递的顺序如何），则认为集合的两个元素是等效的。

	set<int> s;
	s.insert(3);
	s.insert(1);
	s.insert(7);
	s.insert(9);
	s.insert(5);
	cout << "s: ";
	for (const auto& i : s)
	{
		cout << i << ' ';
	}
	cout << endl;
	auto it= s.find(1);//查找1并返回1的迭代器
	s.erase(it);//删除迭代器的值
	//it = s.find(2);//
	//s.erase(it);//删除迭代器的值
	cout << "s: ";
	for (const auto& i : s)
	{
		cout << i << ' ';
	}
	cout << endl;

7、set的计数count

在容器中搜索相当于 val 的元素，并返回匹配项的数量。由于集容器中的所有元素都是唯一的，因此该函数只能返回 1（如果找到元素）或 0（否则）。如果容器的比较对象反射性地返回 false（即，无论元素作为参数传递的顺序如何），则认为集合的两个元素是等效的。


    set<int> s;
	s.insert(3);
	s.insert(1);
	s.insert(7);
	s.insert(9);
	s.insert(5);
	cout << "s: ";
	for (const auto& i : s)
	{
		cout << i << ' ';
	}
	cout << endl;
	cout << s.count(1) << endl;//计算有几个1
	cout << s.count(2)<<endl;//计算有几个2