一、set容器

• set和multiset是一个集合容器，其中set所包含的元素是唯一的，集合中的元素按一定的顺序自动排列。set采用红黑树变体的数据结构实现，红黑树属于平衡二叉树。在插入操作和删除操作上比vector快，在n个数中查找目标数的效率是 log 2 n
• set容器中不允许重复元素（中文名集合的意思，只能有一个），multiset允许重复元素。
• 只提供Insert方法初始化
• set/multiset的特性是所有元素会根据元素的值自动进行排序
• set不能修改某个值，如果想修改只能删除再添加

1、set构造函数

set<int> s1;//自动进行排序，默认从小到大。
s1.insert(7);
s1.insert(2);
s1.insert(3);//这时候打印时会输出 2 3 7，已经自动排序了
1
2
3
4

2、set赋值操作

	set<int> s2;
	s2 = s1;
	s2.swap(s1);//swap交换集合容器
1
2
3

3、set大小操作

size();//获得容器元素的数目
empty();//判断内容器是否为空
1
2

4、set插入和删除操作

insert(elem);//在容器中插入元素
clear();//清除所有元素
erase(pos);//删除迭代器指的元素，下面这两个都是迭代器
erase(beg,end);//删除区间的元素
erase(elem);//删除容器中值为elem的元素，是删除一个，虽然只有一个
1
2
3
4
5

5、set的查找（重要）

s1.find(4)找4位置的迭代器
lower_bound(2) 找第一个大于等于2的(元素)迭代器值
s1.upper_bound(2); 找第一个大于K的值

	set<int> s1;
	//插入几个元素
	s1.insert(7);
	s1.insert(2);
	s1.insert(4);
	s1.insert(5);
	s1.insert(1);
	s1.insert(9);
    
    //使用迭代器从头开始查找元素
    //find函数查找元素，返回元素位置的迭代器，如果没有找到返回end()的迭代器
	set<int>::iterator ret = s1.find(4);
	
	//下面判断元素是否找到
	if (ret == s1.end())
	{
		cout << "没有找到" << endl;
	}
	else
	{
		cout << "ret:" << *ret << endl;
	}
//---------------------------------------------------------------
	//lower_bound(2)找第一个大于等于k的(元素)迭代器值
	ret = s1.lower_bound(2);
	if (ret == s1.end())
	{
		cout << "没有找到" << endl;
	}
	else
	{
		cout << "ret:" << *ret << endl;
	}

//---------------------------------------------------------------
	//找第一个大于K的值
	ret = s1.upper_bound(2);
	if (ret == s1.end())
	{
		cout << "没有找到" << endl;
	}
	else
	{
		cout << "ret:" << *ret << endl;
	}

	//equal_range 返回Lower_bound 和 upper_bound值
	pair<set<int>::iterator, set<int>::iterator> myret = s1.equal_range(2);
	//这里用到了pair我们在下面补充对组的相关内容。
	/*myret.first;
	myret.second;*/
	if (myret.first == s1.end())
	{
		cout << "can't find" << endl;
	}
	else
	{
		cout << "myret:" << *myret.first << endl;//返回Lower_bound
	}
	if (myret.second == s1.end())
	{
		cout << "can't find" << endl;
	}
	else
	{
		cout << "myret:" << *myret.second << endl; //返回upper_bound
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

6、修改set的排序次序

看下面的仿函数

set<int, mycompare> s3;//这里使用仿函数后，在插入时会修改默认的插入顺序
	s3.insert(7);
	s3.insert(2);
	s3.insert(4);
	s3.insert(5);
	s3.insert(1);
	s3.insert(9);
1
2
3
4
5
6
7

7、set里添加对象

set添加元素需要排序，但如果直接排序，set不知道怎么排会报错，因此也需要一个仿函数

//定义一个类
class Person
{
public:
	Person(int age, int id):id(id),age(age){}
public:
	int id;
	int age;
};
//定义一个仿函数，根据对象的年龄大小排序
class mycompare2
{
public: 
	bool operator()(Person p1, Person p2)const
	{
		return p1.age > p2.age;
	}
};
void test(){
	//使用仿函数进行自定义排序
	set<Person,mycompare2> sp;
	Person p1(10, 20), p2(30, 40), p3(50, 60);
	sp.insert(p1);
	sp.insert(p2);
	sp.insert(p3);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

需要注意的是，如果使用find，这时候应该查找比较的那个元素，比如上面用age进行比较的，那么查找的时候也是用这个age去查找，这个age就相当于键了。比如下面代码，虽然没有加入p4，但是p4里的40是已经加入的，因此可以找到

	Person p4(10, 40);
	auto ret = sp.find(p4);//set<Person,mycompare2>::iterator
	if (ret == sp.end())
	{
		cout << "can't find" << endl;
	}
	else
	{
		cout << "find:" << (*ret).id << " " << (*ret).age << endl;
	}
1
2
3
4
5
6
7
8
9
10

二、pair

pair是将2个数据组合成一组数据，当需要这样的需求时就可以使用pair，如stl中的map就是将key和value放在一起来保存。另一个应用是，当一个函数需要返回2个数据的时候，可以选择pair。

//法一
	pair<string, int> pair1(string("number"), 20);
	cout << pair1.first << " " << pair1.second << endl;
	
	//或者pair<string,int> pair2=make_pair("name",30)
	pair<string, int> pair2 = make_pair("name", 30);
	cout << pair2.first << " " << pair2.second << endl;

	//pair赋值
	pair<string, int> pair3 = pair2;
	cout << pair2.first << " " << pair2.second << endl;
1
2
3
4
5
6
7
8
9
10
11

三、仿函数

//仿函数
class mycompare
{
public:
	bool operator()(int v1,int v2)const
	{
		return v1 > v2;
	}
};
1
2
3
4
5
6
7
8
9