Set和Multiset容器（C++）

3.8 set/multiset 容器

3.8.1 set 基本概念

简介：

• 所有元素都会在插入时自动被排序

本质：

• set/multiset 属于关联式容器，底层结构是用二叉树实现的

set 和multiset 区别：

• set 不允许容器中有重复的元素
• multiset 允许容器有重复的元素

3.8.2 set 构造和赋值

功能描述：

• 创建set 容器以及赋值

构造：

• set<T> st; //默认构造函数
• set(const set& st); //拷贝构造函数

赋值：

• set& operator=(const set& st); //重载等号操作符

示例：

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

//打印输出
void PriSet(const set<int> s) {
	for (set<int>::const_iterator it = s.begin(); it != s.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}


//set构造和赋值
void test01() {
	//默认构造
	set<int> s1;
	//set插入只有insert
	s1.insert(2);
	s1.insert(1);
	s1.insert(3);
	//不允许加入重复值
	s1.insert(2);
	//特点：插入元素自动排序
	PriSet(s1);
	//拷贝构造
	set<int> s2(s1);
	PriSet(s2);
	//赋值
	set<int> s3 = s2;
	PriSet(s3);
}


//主函数
int main() {
	test01();
	system("pause");
	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

3.8.3 set 大小和交换

功能描述：

• 统计set 容器大小以及交换set 容器

函数原型：

• size(); //返回容器中元素的数目
• empty(); //判断容器是否为空
• swap(st); //交换两个集合容器

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

//打印输出
void PriSet(const set<int>& s) {
	for (set<int>::const_iterator it = s.begin(); it != s.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

//set大小和交换
void test01() {
	set<int> s1;
	s1.insert(0);
	s1.insert(4);
	s1.insert(2);
	s1.insert(3);
	PriSet(s1);
	cout << "s1大小为：" << s1.size() << endl;
	if (s1.empty()) {
		cout << "s1容器为空" << endl;
	}
	else {
		cout << "s1容器不为空" << endl;
	}
	set<int> s2;
	s2.insert(0);
	PriSet(s2);
	s1.swap(s2);
	PriSet(s1);
}

//主函数
int main() {
	test01();
	system("pause");
	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

3.8.4 set 插入和删除

功能描述：

• set 容器进行插入数据和删除数据

函数原型：

• insert(elem); //在容器中插入元素
• clear(); //清除所有元素
• erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器
• erase(beg, end); //删除区间[beg, end]的所有元素，返回下一个元素的迭代器
• erase(elem); //删除容器中值为elem的元素；

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

//打印
void PriSet(const set<int>& s) {
	for (set<int>::const_iterator it = s.begin(); it != s.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}


//set插入和删除
void test01() {
	set<int> s1;
	s1.insert(0);
	s1.insert(4);
	s1.insert(2);
	s1.insert(3);
	PriSet(s1);
	//删除操作
	s1.erase(3);
	PriSet(s1);
	set<int>::iterator it = s1.begin();
	it++;
	s1.erase(s1.begin(),it);
	PriSet(s1);
}

//主函数
int main() {
	test01();
	system("pause");
	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

3.8.5 set 查找和统计

功能描述：

• 对set 容器进行查找数据以及统计数据

函数原型：

• find(key); //查找key是否存在，若存在，返回该键的元素迭代器；若不存在，返回set.end();
• count(key); //统计key元素的个数

示例：

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

//打印
void PriSet(const multiset<int>& s) {
	for (multiset<int>::const_iterator it = s.begin(); it != s.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

//set查找和统计
void test01() {
	multiset<int> s1;
	for (int i = 0; i < 10; i++) {
		s1.insert(i);
		s1.insert(i + 1);
	}
	PriSet(s1);
	//查找 find返回的是迭代器
	s1.erase(s1.find(9));
	PriSet(s1);
	//统计
	cout << "s1中6的个数为：" << s1.count(6) << endl;
}

//主函数
int main() {
	test01();
	system("pause");
	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

总结：

• 查找 — find（返回的是迭代器）
• 统计 — count（对于set，结果只有0 1两种）

3.8.6 set 和 multiset区别

区别：

• set 不可以插入重复数据，而multiset可以
• set 插入数据的同时会返回插入结果，表示插入成功
• multiset 不会检测数据，因此可以插入重复数据

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

//set 和 multiset 区别
void test01() {
	//对于set
	set<int> s;
	//第一次插入 10
	pair<set<int>::iterator, bool> ret = s.insert(10);
	if (ret.second) {
		cout << "第一次插入成功" << endl;
	}
	else {
		cout << "第一次插入失败" << endl;
	}
	//第二次插入 10
	ret = s.insert(10);
	if (ret.second) {
		cout << "第二次插入成功" << endl;
	}
	else {
		cout << "第二次插入失败" << endl;
	}

	//对于multiset
	multiset<int> ms;
	ms.insert(10);
	ms.insert(10);
	for (multiset<int>::iterator it = ms.begin(); it != ms.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;

}


//主函数
int main() {
	test01();
	system("pause");
	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

总结：

• 如果不允许插入重复数据可以利用set
• 如果需要插入重复数据利用multiset

3.8.7 pair 对组创建

功能描述：

• 成对出现的数据，利用队组可以返回两个数据

两种创建方式：

• pair<type, type> p (value1, value2);
• pair<type, type> p = make_pair(value1, value2);

示例：

#include<iostream>
#include<string>
using namespace std;

//对组创建
void test01() {
	//第一种方式
	pair<string, int> p1("tom", 20);
	cout << "姓名：" << p1.first << " 年龄：" << p1.second << endl;
	//第二种方式
	pair<string, int> p2 = make_pair("jerry", 10);
	cout << "姓名：" << p2.first << " 年龄：" << p2.second << endl;
}

//主函数
int main() {
	test01();
	system("pause");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3.8.8 set 容器排序

学习目标：

• set 容器默认排序规则为从小到大，掌握如何改变排序规则

主要技术点：

• 利用仿函数，可以改变排序规则

示例1：set存放内置数据类型

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

class MyCompare {
public:
	bool operator()(const int& v1,const int& v2)const {
		return v1 > v2;
	}
};

//打印
void PriSet(const set<int>& s) {
	for (set<int>::const_iterator it = s.begin(); it != s.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

//set容器排序
void test01() {
	set<int>s1;
	s1.insert(10);
	s1.insert(50);
	s1.insert(30);
	s1.insert(20);
	//默认顺序为从小到大
	PriSet(s1);
	//指定顺序从大到小
	set<int, MyCompare>s2;
	s2.insert(10);
	s2.insert(90);
	s2.insert(30);
	s2.insert(50);
	for (set<int, MyCompare>::iterator it = s2.begin(); it != s2.end(); it++) {
		cout << *it << " ";
	}
	cout << endl;
}

//主函数
int main() {
	test01();
	system("pause");
	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

示例2：set存放自定义数据类型

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

//set 排序 自定义数据类型

class Person {
public:
	string m_Name;
	int m_Age;
	Person(string name, int age) {
		this->m_Name = name;
		this->m_Age = age;
	}
};

class ComparePerson {
public:
	bool operator()(const Person& p1, const Person& p2)const {
		//按照年龄降序
		return p1.m_Age > p2.m_Age;
	}
};

void test01() {
	//自定义数据类型 都会指定排序规则
	set<Person,ComparePerson> s;

	//创建Person对象
	Person p1("张三", 10);
	Person p2("李四", 20);
	Person p3("王五", 30);
	Person p4("赵六", 40);
	s.insert(p1);
	s.insert(p2);
	s.insert(p3);
	s.insert(p4);

	//遍历
	for (set<Person,ComparePerson>::iterator it = s.begin(); it != s.end(); it++) {
		cout << "姓名：" << it->m_Name << " 年龄：" << it->m_Age << endl;
	}
}

//主函数
int main() {
	test01();
	system("pause");
	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