[C++]STL-set/multiset容器_std::multiset自动排序

set/multisite容器

set/multisite容器的特性是所有元素会根据元素的值自动进行排序。set/multisite容器是关联容器

set底层机制为RB-tree（红黑树，平衡二叉树的一种）。其查找效率非常高，set不允许有重复元素，multisite允许有重复元素

set容器会自动进行排序，所以只提供了insert方法添加数据

不可以通过set的迭代器改变元素的值

#include<iostream>
#include<set>   //set/multiset都是一个头文件，只需要引入set即可
using namespace std;
//set容器

void PrintSet(set<int> s) {
	for (set<int>::iterator it = s.begin(); it != s.end(); it++) {
		cout << (*it) << "  ";
	}
	cout << endl;
}

//set容器初始化
void SetTest1() {
	set<int> s1;
	s1.insert(56);  //自动进行排序，默认从小到大
	s1.insert(89);
	s1.insert(12);
	s1.insert(2);
	PrintSet(s1);


	
	
	//set容器赋值操作
	set<int> s2 = s1;
	set<int> s3 = { 10,56,44,23 };
	s3.swap(s2);  //交换容器内所有元素
	//size，empty，clear函数效果与其他容器一致

	//删除操作
	s1.erase(s1.begin());  //删除指定迭代器位置的元素
	s1.erase(89);  //删除指定值的元素
	PrintSet(s1);
	PrintSet(s2);
	PrintSet(s3);

	//改变默认排序


}

//set查找操作
void SetTest2() {
	//通过实值查找
	set<int> s1 = { 10,56,44,23 };
	set<int>::iterator it = s1.find(23);  
	/*
	find()函数若找到指定值的元素，
	则返回该元素的迭代器，
	若没有找到指定值元素
	则返回容器的end值
	*/
	if (it != s1.end()) {
		cout << "容器中存在:" << (*it) << endl;
	}
	else {
		cout << "不存在！" << endl;
	}
	//lower_bound(keyElem)，返回第一个大于等于keyElem的key的迭代器
	//upper_bound(keyElem),返回第一个大于keyElem的key的迭代器
	it = s1.lower_bound(25);
	if (it != s1.end()) {
		cout << "容器中第一个大于等于25的数为：" << (*it) << endl;
	}
	else {
		cout << "容器中所有数都小于25" << endl;
	}
	//equal_range(),返回两个值，分别是lower_bound和upper_bound的返回值
	//返回的类型是对组pair
	pair<set<int>::iterator,set<int>::iterator> myret = s1.equal_range(23);
	//判断是否得到相应值
	if (myret.first != s1.end()) {
		cout << "容器中第一个大于等于25的数为：" << *(myret.first) << endl;
	}
	else {
		cout << "容器中所有数都大于25" << endl;
	}
	if (myret.second != s1.end()) {
		cout << "容器中第一个大于25的数为：" << *(myret.second) << endl;
	}
	else {
		cout << "容器中所有数都小于等于25" << endl;
	}

}



int main() {
	SetTest2();

	return 0;
}
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

对组

对组(pair)将一对值组合成一个值，这一对值可以具有不同的数据类型，两个值可以分别用pair的共有函数first和second访问

类模板

template<class T1 , class T2> struct pair
1

//pair对组练习
void PairTest() {
	//对组构造方法
	pair<string, int> pair1("Leslie",45);
	cout << pair1.first << "'s age is " << pair1.second << endl;
	
	pair<string, int> pair2 = make_pair("Bob", 26);
	cout << pair2.first << "'s age is " << pair2.second << endl;
	
	pair<string, int> pair3 = pair2;
}
1
2
3
4
5
6
7
8
9
10
11

//仿函数
class MyCompare {
public:
	bool operator()(int v1, int v2)const
	{
		return v1 > v2;
	}
};

//更改默认排序方式
void SetTest3() {
	set<int, MyCompare> s1;   //重新定义排序规则，使其从大到小排序
	s1.insert(56);
	s1.insert(89);
	s1.insert(12);
	s1.insert(2);
	for (set<int>::iterator it=s1.begin(); it != s1.end(); it++) {
		cout << *it << "  ";
	}
	cout << endl;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

自定义类与set容器

#include<iostream>
#include<set>   //set/multiset都是一个头文件，只需要引入set即可
using namespace std;

class Person {
public:
	int mId;
	int mAge;
	Person(int id, int age) : mId(id), mAge(age) {}
	Person(){}
};

class PersonRank {
public:
	bool operator()(Person p1, Person p2) const  //注意，在VS中默认这里需要加const
	{
		return p1.mAge > p2.mAge;  //按照年龄从大到小
	}

};


void SetTest5() {  //对于自定义类的排序，由于系统不知道如何进行，所以需要我们自行制定排序方式
	set<Person, PersonRank> sp;
	Person p1(10, 15), p2(11, 19), p3(45, 88);
	sp.insert(p1);
	sp.insert(p2);
	sp.insert(p3);
	for (set<Person>::iterator it = sp.begin(); it != sp.end(); it++) {
		cout << "年龄：" << (*it).mAge << " ID：" << (*it).mId << endl;
	}

	//查找
	Person p4(20, 15);
	/*
	可以看到，set容器中并没有p4(20,15)
	但还是找到了与之“相同”的元素
	事实上，由于我们定义了排序的方法PersonRank
	所以find函数在寻找时，默认采用判断mAge值的方法决定两个元素是否相等
	所以，只要传入的年龄相同，find函数都找到与之相同的元素
	*/
	set<Person>::iterator ret=sp.find(p4);
	if (ret == sp.end()) {
		cout << "没有找到" << endl;
	}
	else {
		cout << "年龄：" << (*ret).mAge << " ID：" << (*ret).mId << endl;
	}
}


int main() {
	SetTest5();
	return 0;
}
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