【C++】set & multiset

---

前言

知识铺垫：关联式容器和值键对概念
链接-【C++】关联式容器 & 键值对（概念介绍）

---

1.set介绍

set文档

翻译：

1. set是按照一定次序存储元素的容器（从小到大）

2. 在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。

3. 在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。

4. set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。

5. set在底层是用二叉搜索树(红黑树)实现的。

注意：

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

2. set中插入元素时，只需要插入value即可，不需要构造键值对。

3. set中的元素不可以重复(因此可以使用set进行去重)。

4. 使用set的迭代器遍历set中的元素，可以得到有序序列

5. set中的元素默认按照小于来比较

6. set中查找某个元素，时间复杂度为：$lo{g}_{2}n$

7. set中的元素不允许修改(为什么?)

8. set中的底层使用二叉搜索树(红黑树)来实现。

---

2.set的使用

（1）set的模板参数列表

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

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

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

（2）set的构造、set的迭代器、set的容量、set修改操作

• 略（可自行查看文档）

（3）set的使用举例

• 示例1

#include 
void TestSet()
{
	// 用数组array中的元素构造set
	int array[] = { 1, 3, 5, 7, 9, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9, 2, 4,
6, 8, 0 };
	set<int> s(array, array + sizeof(array) / sizeof(array[0]));
	cout << s.size() << endl;
	// 正向打印set中的元素，从打印结果中可以看出：set可去重
	for (auto& e : s)
		cout << e << " ";
	cout << endl;
	// 使用迭代器逆向打印set中的元素
	for (auto it = s.rbegin(); it != s.rend(); ++it)
		cout << *it << " ";
	cout << endl;
	// set中值为3的元素出现了几次
	cout << s.count(3) << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 示例2

#include
#include
using namespace std;

void test_set1()
{
	set<int> s;
	s.insert(3);
	s.insert(1);
	s.insert(4);
	s.insert(7);
	s.insert(2);
	s.insert(1);

	// 排序+去重（搜索二叉树-中序插入）
	//set::iterator it = s.begin();
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	//	auto pos = s.find(3);                    // O(logN)
	auto pos = find(s.begin(), s.end(), 3);  //  O(N)
	if (pos != s.end())
	{
		s.erase(pos);
	}
	cout << s.erase(1) << endl;
	cout << s.erase(3) << endl;	//删除失败返回0
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	if (s.count(3))	//3在的话返回1，不在返回0
	{
		//...
	}
}


int main()
{
	test_set1();

	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

---

3.multiset介绍

multiset文档

翻译：

1. multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。

2. 在multiset中，元素的value也会识别它(因为multiset中本身存储的就是组成的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)，但可以从容器中插入或删除。

3. 在内部，multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。

4. multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。

5. multiset底层结构为二叉搜索树(红黑树)。

注意：

1. multiset中再底层中存储的是的键值对
2. mtltiset的插入接口中只需要插入即可
3. 与set的区别是，multiset中的元素可以重复，set是中value是唯一的
4. 使用迭代器对multiset中的元素进行遍历，可以得到有序的序列
5. multiset中的元素不能修改
6. 在multiset中找某个元素，时间复杂度为$O(lo{g}_{2}N)$
7. multiset的作用：可以对元素进行排序

---

4.multiset的使用

此处只简单演示set与multiset的不同，其他接口接口与set相同，同学们可参考set。

• 示例1

#include 
void TestSet()
{
	int array[] = { 2, 1, 3, 9, 6, 0, 5, 8, 4, 7 };

	// 注意：multiset在底层实际存储的是的键值对
	multiset<int> s(array, array + sizeof(array) / sizeof(array[0]));
	for (auto& e : s)
		cout << e << " ";
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11

• 示例2

void test_set2()
{
	multiset<int> s;
	s.insert(3);
	s.insert(1);
	s.insert(4);
	s.insert(7);
	s.insert(2);
	s.insert(1);
	s.insert(1);
	s.insert(3);
	s.insert(1);
	s.insert(3);
	s.insert(2);
	s.insert(1);
	s.insert(1);


	// 排序
	//multiset::iterator it = s.begin();
	auto it = s.begin();
	while (it != s.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	auto pos = s.find(3);                    // O(logN)
	while (pos != s.end())	//find找到的3为中序第一个3，++之后仍指向树中同一元素
	{
		cout << *pos << " ";
		++pos;
	}
	cout << endl;

	/*if (pos != s.end())  //删除某一元素的测试代码
	{
		s.erase(pos);
	}
	cout << s.erase(1) << endl;
	cout << s.erase(3) << endl;
	for (auto e : s)
	{
		cout << e << " ";
	}
	cout << endl;

	cout << s.count(1) << endl;		//count用于确定容器中同一元素个数
	*/
}

int main()
{
	test_set2();

	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

---

🌹🌹 【C++】set & multiset 今天就讲到这里了，如果有兴趣的小伙伴可以点开博主的专栏，查阅更多以前的文章。同时，博主后续会继续更新更多C++的相关知识，干货满满，如果觉得博主写的还不错的话，希望各位小伙伴不要吝啬手中的三连哦！你们的支持是博主坚持创作的动力！💪💪