STL 关联式容器
关联式容器
- 集合(set) 用以有序地存储 互异 元素的容器。其实现是由节点组成的红黑树,每个节点都包含着一个元素,节点之间以某种比较元素大小的谓词进行排列。
- 多重集合(multiset)用以有序地存储元素的容器。允许存在相等的元素。
- 映射(map)由 {键,值} 对组成的集合,以某种比较键大小关系的谓词进行排列。
- 多重映射(multimap)由 {键,值} 对组成的多重集合,亦即允许键有相等情况的映射。
无序(关联式)容器(C++11)
- 无序(多重)集合(unordered_set/unordered_multiset),与 set/multiset 的区别在于元素无序,只关心「元素是否存在」,使用哈希实现。
- 无序(多重)映射(unordered_map/unordered_multimap)与 map/multimap 的区别在于键 (key) 无序,只关心 “键与值的对应关系”,使用哈希实现。
set 集合
定义
set 是关联容器,翻译为集合,是一个内部自动有序且不含重复元素的容器。其最主要的作用就是自动去重并升序排序,使用set 需要导入 <set>头文件。
set 的搜索、移除和插入复杂度都是O(logn)复杂度,因此非常适合处理需要同时兼顾查找、插入与删除的情况。
和数学中的集合相似,set 中不会出现值相同的元素。如果需要有相同元素的集合,需要使用 multiset。 另外 C++11种还引入了 unordered_set 来处理只去重但不排序的需求,速度比 set 快很多。
常用操作
- insert(x) 插入元素:
当容器中没有等价元素的时候,将元素 x 插入到 set 中。
2. erase() 删除元素:
- 删除单个元素:
- earse(x): 删除值为 x 的元素,时间复杂度 O(logn)。
- erase(it): 删除迭代器为 it 的元素,要求迭代器必须合法,时间复杂度 O(1)。
- 删除区间元素:
3. clear() 清空容器:
清空 set,复杂度为 O(n)。
4. find(x) 查找元素:
查找值为 x 的元素,返回其迭代器,时间复杂度 O(logn)。
5. set 内元素访问:只能通过迭代器 iterator 进行。
for(set<int>::iterator it = s.begin(); it != s.end(); it++) cout << *it << " ";
注:STL 容器中只有 vector 和 string 支持 *(it + i) 或 *(v.begin() + i) 的访问方式。
示例代码
#include <bits/stdc++.h> using namespace std; int main(){ int a[10] = {2, 3, 2, 4, 5, 6, 9, 9, 2, 3}; set<int> s; for(int i = 0; i < 10; i++){ s.insert(a[i]); } cout << s.size() << "\n"; for(set<int>::iterator it = s.begin(); it != s.end(); it++){ cout << *it << " "; } return 0; }
map 映射
定义
map 是有序键值对容器,它的元素的键是唯一的,会以键从小到大的顺序自动排序。搜索、移除和插入操作复杂度都为 O(logn)。
例如现在想要存储学生姓名对应的分数:Tom 0,Bob 100…由于数组下标只能为非负整数,所以无法用姓名作为下标来存储,这个时候最简单的办法就是使用 STL 中的 map。因为 map 可以将任何基本类型(包括 STL 容器)映射到任何基本类型(包括 STL 容器),也就可以建立 string 到 int 的映射。
map 中不会存在键相同的元素,即一键只能对应一个值,如果想要一个键对应多个值,可以使用 multimap,其使用方法与 map 的使用方法基本相同。如果没有按键排序的需求,可以使用 C++11 引入的 unordered_map,速度比 map 快不少。
常用操作
- map 的定义
map<Keytype, Valuetype> mp; // Key 是键,Value 是值 <键,值> map<string, int> mp; // 字符串的映射要用 string 不能用 char 数组 map<int, int> mp; // 相当于普通的 int 数组 map<set<int>, string> mp; // 将 set 容器映射到字符串
2. map 中元素的访问
- 通过下标(类似于普通数组的下标访问)
map<char, int> mp; mp['c'] = 10; mp['c'] = 20; // 原来 'c' 对应的值 10 将被覆盖 cout << mp['c'] << "\n"; // 输出 20
2. 通过迭代器:it->first 为键,it->second 为值
map<char, int> mp; mp['c'] = 10; mp['c'] = 20; // 原来 'c' 对应的值 10 将被覆盖 mp['a'] = 86; mp['e'] = 2; mp['z'] = 9; for(map<char, int>:: iterator it = mp.begin(); it != mp.end(); it++){ cout << it->first << " " << it->second << "\n"; // 或者: cout << (*it).first << " " << (it).second << "\n"; } * /* 输出按键从小到大自动排序: a 86 c 20 e 2 z 9 */
3. find(x) 查找元素:
查找键为 x 的映射,返回其迭代器,时间复杂度 O(logn), n 为映射的个数。
4. erase() 删除元素:
- 删除单个元素:
- earse(x): 删除键为 x 的元素,时间复杂度 O(logn)。
- erase(it): 删除迭代器为 it 的元素,要求迭代器必须合法,时间复杂度 O(1)。
- 删除区间元素:
- erase(first, last): 删除迭代器在 [first, last) 范围内的所有元素。
5. size() 获取长度:
获取 map 中键值对的个数,复杂度为 O(1)。
6. clear() 清空容器:
清空 map 种所有元素,复杂度为 O(n)。
示例代码
#include <bits/stdc++.h> using namespace std; int main(){ map<char, int> mp; mp['c'] = 10; mp['c'] = 20; // 原来 'c' 对应的值 10 将被覆盖 cout << mp['c'] << "\n"; // 输出 20 mp['a'] = 86; mp['e'] = 2; mp['z'] = 9; map<char, int>:: iterator it = mp.find('e'); cout << (*it).first << " " << (*it).second << "\n"; // e 2 for(it = mp.begin(); it != mp.end(); it++){ cout << it->first << " " << it->second << "\n"; } return 0; }
pair 容器
定义
pair 用来将一对值组合成一个值,比如当想要将两个元素合成一个操作数据,又不想用结构体时,就可用 pair,因此可将其视为内部有两个元素的结构体,且元素类型可指定。
pair 容器在<utility>头文件中定义,由于 map 的内部实现中用到了 pair,因此导入<map> 会自动添加 <utility>。
常用操作
- pair定义及元素访问:在创建pair对象时,必须提供两个类型名,它的两个参数分别对应 first 和 second,可以是任意数据类型或者容器。
// pair<类型1, 类型2> name; pair<char, int> p1; p1 = make_pair('x', 7); // 使用自带的 make_pair 赋值 cout << p1.first << " " << p1.second << "\n"; // x 7 pair<string, double> p2("PI", 3.14); // 定义时用 (值1, 值2) 初始化 cout << p2.first << " " << p2.second << "\n"; // PI 3.14
2. 大小比较:两个 pair 类型数据可以直接用 ==,>= 等比较运算符进行大小比较,规则是先以 first 值做标准,再以 second 值做标准。
pair<int, int> a(9, 0); pair<int, int> b(2, 5); cout << (a < b ? "a < b" : "a >= b") << "\n"; // a >= b pair<int, int> c(8, 7); pair<int, int> d(8, 1); cout << (c < d ? "c < d" : "c >= d") << "\n"; // c >= d
3. 使用 pair 作为 map 键值对进行插入
map<char, int> mp; mp.insert(make_pair('x', 5)); mp.insert(pair<char, int>('y', 3)); for(map<char, int>:: iterator it = mp.begin(); it != mp.end(); it++){ cout << it->first << " " << it->second << "\n"; }
经典例题
[NOIP2006 普及组] 明明的随机数
思路
使用 set 会自动去重排序。
代码
#include <bits/stdc++.h> using namespace std; int main(){ set<int> s; int n, t; cin >> n; for(int i = 1; i <= n; i++){ cin >> t; s.insert(t); // 默认由小到大顺序插入,不会重复 } cout << s.size() << "\n"; set<int>::iterator i; // 正向 set 迭代器 i for(i = s.begin(); i != s.end(); i++) // i 取到 s 中每个元素的地址 cout << *i << " "; // *i : 取地址 i 中存的元素值 // for(auto i : s) cout << i << " "; // auto: 自动遍历,获取容器 s 中的元素 // for(int i : s) cout << i << " "; // 指定元素类型为 int 遍历 return 0; }
[NOIP2007 提高组] 统计数字
思路
由于本题数据范围很大,开不出 10 的 9 次方大小的数组,因此可以用 map<int, int> 灵活建立出现过的数字及其次数的映射,最后直接遍历 map 输出每个键和其对应的值即可。
代码
#include <bits/stdc++.h> using namespace std; int main(){ int n, t; map<int, int> cnt; scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%d", &t); cnt[t]++; // (键, 值) : (键, cnt[键]) } map<int, int>::iterator it; for(it = cnt.begin(); it != cnt.end(); it++){ printf("%d %d\n", (*it).first, (*it).second); // printf("%d %d\n", it->first, it->second); } return 0; }
Set Similarity
思路
本题要求两个集合的相似性,其实就是要找出两个集合的并集与交集,用交集元素个数除以并集元素个数算其百分比。注:输出 “%” 用 “%%”。
对于题目需要读入的 n 个集合,可以定义一个 set 数组,使用 insert() 将输入元素插入到给定集合内。
对于每次要查询的两个集合求其相似性,需要枚举第一个集合中的值,在另个集合中进行查找,若另个集合中存在,算入交集计数,若不存在,算入并集计数。
代码
#include <bits/stdc++.h> using namespace std; int main(){ int n, m, t; set<int> s[55]; scanf("%d", &n); for(int i = 1; i <= n; i++){ scanf("%d", &m); while(m--){ scanf("%d", &t); s[i].insert(t); } } int k, x, y; scanf("%d", &k); while(k--){ scanf("%d %d", &x, &y); // 计算 s[x] 与 s[y] 的 nc 和 nt int nc = 0, nt = s[x].size(); // 初始化 nt 为 s[x] 不同数字个数 // 遍历 s[y], 查找每个数是否在 s[x] 中出现过 for(set<int>::iterator it = s[y].begin(); it != s[y].end(); it++){ if(s[x].find(*it) != s[x].end()){ // 共有元素 nc++; } else{ nt++; // 非共有元素,两集合不同数字总数加 1 } } printf("%.1lf%%\n", nc * 100.0 / nt); } return 0; }
火星数字
思路
本题如果直接模拟,要讨论的情况会很多比较复杂。鉴于题目中数据范围不大,输入数字不会超过十进制的 169,因此可以暴力打表,然后直接查询。
代码
#include <bits/stdc++.h> using namespace std; int main(){ string gw[15] = {"tret", "jan", "feb", "mar", "apr", "may", "jun", "jly", "aug", "sep", "oct", "nov", "dec"}; string sw[15] = {"tret", "tam", "hel", "maa", "huh", "tou", "kes", "hei", "elo", "syy", "lok", "mer", "jou"}; string ns[170]; // ns[x] 数字 x 对应的火星文 map<string, int> sn; // sn[s] 火星文 s 对应的数字 // 打表生成 [0, 169) 中的映射 // 初始化单个个位和十位数字映射 for(int i = 0; i < 13; i++){ ns[i] = gw[i]; // 初始化个位数字对字符串 sn[gw[i]] = i; // 初始化个位字符串对数字 ns[i * 13] = sw[i]; // 初始化十位数字对字符串 sn[sw[i]] = i * 13; // 初始化十位字符串对数字 } // 初始化其余两位数的情况 for(int i = 1; i < 13; i++){ // i: 十位 1 ~ 12 for(int j = 1; j < 13; j++){ // j: 个位 1 ~ 12 ns[i * 13 + j] = sw[i] + " " + gw[j]; sn[sw[i] + " " + gw[j]] = i * 13 + j; } } int n; string s; cin >> n; getchar(); while(n--){ getline(cin, s); if(s[0] >= '0' && s[0] <= '9'){ // 地球 -> 火星 int x = 0; for(int i = 0; i < s.size(); i++){ x = x * 10 + s[i] - '0'; } cout << ns[x] << "\n"; } else{ // 火星 -> 地球 cout << sn[s] << "\n"; } } return 0; }
The Dominant Color
思路
题目描述中的“A strictly dominant color takes more than half of the total area. ”意思是说一个严格意义上的主色彩会占据超过一半的区域,题目中的色彩都是用整型数字进行编码的,所以本题其实就是要求一个给定的 N 行 M 列的矩阵中,出现次数超过总数字个数一半的那个最多出现次的数,本质上还是一个计数问题。
由于颜色的编码在 2^24 以内,数据范围很大,可能导致内存超限,因此可用 map<int, int> cnt 来计数,计数完成后遍历 cnt 每对键值对,找到值最大的那对元素,记录其键输出即可。
代码
#include <bits/stdc++.h> using namespace std; int main(){ int m, n, t; cin >> m >> n; map<int, int> cnt; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ cin >> t; cnt[t]++; // (键, 值) : (键, cnt[键]) } } map<int, int>::iterator it; int maxv = 0, k; for(it = cnt.begin(); it != cnt.end(); it++){ if(it->second > maxv){ k = it->first; // 记录最大值的键 maxv = it->second; // 记录最大值 } } cout << k; return 0; }