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 快很多。

常用操作

  1. insert(x) 插入元素:

当容器中没有等价元素的时候,将元素 x 插入到 set 中。

2. erase() 删除元素:

  1. 删除单个元素:
    1. earse(x): 删除值为 x 的元素,时间复杂度 O(logn)。
    2. erase(it): 删除迭代器为 it 的元素,要求迭代器必须合法,时间复杂度 O(1)。
  2. 删除区间元素:

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 快不少。

常用操作

  1. 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 中元素的访问

  1. 通过下标(类似于普通数组的下标访问)
    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() 删除元素:

  1. 删除单个元素:
    • earse(x): 删除键为 x 的元素,时间复杂度 O(logn)。
    • erase(it): 删除迭代器为 it 的元素,要求迭代器必须合法,时间复杂度 O(1)。
  2. 删除区间元素:
    • 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>。

常用操作

  1. 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;
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注