STL 应用 —— set / multiset

STL 应用 —— set / multiset

【简介】

STL提供了4种关联容器：set、multiset、map、multimap。

关联容器将值和键关联在一起，通过键来查找值。这4种容器都是可反转的经过排序的关联容器，不可以指定插入位置，因为需要保持有序性，可提供对元素的快速访问，内部采用红黑树实现。

set是有序集合，multiset是有序多重集合。set的键和值是统一的，值就是键，set的每个键都是唯一的，不允许重复；而multiset与set类似，只是允许多个值的键相同。使用set或multiset时，需要引入头文件#include。

set或multiset的迭代器为双向访问，不支持随机访问。执行一次“++”和“–”操作的时间复杂度均为O (logn)。
默认的元素顺序为升序，也可以通过第2个模板的参数设置为降序。

set<int>a; //升序

set<int , greater<int> >a; //降序，注意greater 后面有空格，避免两个 > 一起，有右移的歧义
1
2
3

【成员函数】

• size/empty/clear：元素个数、判空、清空。
• begin/end：开始位置和结束位置。
• insert(x)：将元素x 插入集合。
• erase(x)：删除所有等于x 的元素。
• erase(it)：删除it迭代器指向的元素。
• find(x)：查找元素x 在集合中的位置，若不存在，则返回end。
• count(x)：统计等于x 的元素个数。
• lower_bound/upper_bound：返回大于或等于x 的最小元素位置、大于x 的最小元素位置。

【举个栗子】

【HDU No. 1412 集合合并】

官方题目地址

题意

给定两个集合A 、B ，求A + B （在同一个集合中不会有两个相同的元素）。

【输入输出】

输入：

每组输入数据均分为三行。第1行包含两个整数n 和m（0int范围的整数），元素之间以一个空格隔开。

输出： 单行输出合并后的集合，要求从小到大输出，元素之间以一个空格隔开。

【样例】

【算法设计】

两个集合的合并问题，集合不允许元素重复，且输出时有序，set是有序集合，且每个键都是唯一的，不允许重复

→ 使用 set 解决。

【步骤】

• 定义一个 set ， 记录合并后的集合
• 将第 1 个集合中的元素插入 set
• 将第 2 个集合中的元素插入 set
• 按顺序输出集合中的元素

【算法实现】

#include
#include

using namespace std;

int n , m , x;

set<int> sum;

int main(){
	
	while(~scanf("%d%d",&n, &m)){
		
		sum.clear();
		
		for(int i = 0 ; i < n ; i ++){
			
			scanf("%d",&x);
			
			sum.insert(x);
			
		}
		
		for(int j = 0 ; j < m ; j++){
			
			scanf("%d", &x);
			sum.insert(x);
		}
		
		for(set<int>::iterator it = sum.begin() ; it != sum.end() ; it ++){
			
			if(it != sum.begin()) {
				
				printf(" ");
				
			}
			
			printf("%d",*it);
			
		}
		
		printf("\n");
		
	}
	
	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