C++数据结构篇『三』关联容器：映射与集合

工欲善其事，必先利其器，使用恰当的数据结构去解决问题能事半功倍。因本人没有任何C++的基础，但在刷题的过程中遇到了一些数据结构的经典应用，且能借助STL中的容器很好的实现并解决任务。因此总结常用容器的用法，以供下次使用。

关联容器包括: map 和 set，字面意思的理解就是，map是字典，有键有对应的值；set是数学上的那个集合，元素无序，且没有重复元素。

map

常用的调用如下：

// <>里的第一个参数表示 key 的类型, 第二个参数表示 value 的类型
// 模板的实例化
map<string, int> m1; 
m1["Kobe"] = 100;
m1["James"] = 99;
m1["Curry"] = 98;
string s("Jordan");
m1[s] = 90;
cout << m1["Kobe"] << endl;
cout << m1["Jordan"] << endl;
//不存在这个 key，就显示 0
// 所以若存在有值为 0 的时候就需要格外注意
cout << m1["Durant"] << endl; 
//通过关键字来删除
m1.erase("Curry");
// 输出 map 的键和值
cout << m1->first;
cout << m1->second;
// pair 的意思是将两个数据组合成一个数据
//也可以通过insert函数来实现增加元素
m1.insert(pair<string, int>("Harris", 89));
// 域分隔符 value_type 函数
m1.insert(map<int, string>::value_type(100, "zhangsan"));
// 全部元素的遍历
map<int, string>::iterator itr;
// 按 key 升序
for (itr = m1.begin(); itr != m1.end(); itr++){
    cout << itr->first << " : " << itr->second << endl;
}
//清空全部
m1.clear(); 

例题

“单身狗”是中文对于单身人士的一种爱称。本题请你从上万人的大型派对中找出落单的客人，以便给予特殊关爱。

输入格式：

输入第一行给出一个正整数 $N（≤ 50 000）$，是已知夫妻/伴侣的对数；随后 $N$ 行，每行给出一对夫妻/伴侣——为方便起见，每人对应一个 ID 号，为 5 位数字（从 00000 到 99999），ID 间以空格分隔；之后给出一个正整数 $M（≤ 10 000）$，为参加派对的总人数；随后一行给出这 $M$ 位客人的 ID，以空格分隔。题目保证无人重婚或脚踩两条船。

输出格式：

首先第一行输出落单客人的总人数；随后第二行按 ID 递增顺序列出落单的客人。ID 间用 1 个空格分隔，行的首尾不得有多余空格。

输入样例：

3
11111 22222
33333 44444
55555 66666
7
55555 44444 10000 88888 22222 11111 23333

输出样例：

5
10000 23333 44444 55555 88888

求解

使用 map 这种数据结构，将夫妻关系进行映射即可，单身狗即为在映射中查找不到的人。

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

map<int, int> couple;
int arr[100002] = {0};
vector<int> v, v1;

int main(int argc, char const *argv[])
{
    int n;
    cin >> n;
    int str1, str2;
    for (int i = 0; i < n; i++)
    {
        cin >> str1 >> str2;
        if (str1 == 0) str1 = 100001;
        if (str2 == 0) str2 = 100001;
        couple[str1] = str2;
        couple[str2] = str1;
    }
    int m;
    cin >> m;
    v.resize(m);
    v1.resize(0);
    int count = 0, temp = 0;
    // 有人可能是夫妻 但另一方不参加聚会 也是单身狗
    for (int i = 0; i < m; i++)
    {
        cin >> temp;
        if (temp == 0) temp = 100001;
        arr[temp] = 1;
        v[i] = temp;
    }
    // 如果 map 中存在，且 数组两端均为 1 表示不单身（两人都在）
    for (int i = 0; i < v.size(); i++)
    {
        if (couple[v[i]] != 0 && arr[v[i]] == 1 && arr[couple[v[i]]] == 1)
            continue;
        else
        {
            count++;
            v1.push_back(v[i]);
        }
    }
    cout << count << endl;
    sort(v1.begin(), v1.end());
    for (int i = 0; i < v1.size(); i++)
    {
        if (i == 0)
            printf("%05d", v1[i]);
        else
            printf(" %05d", v1[i]);
    }
    return 0;
}

set

声明与初始化

template <class T>
void showset(set<T> v)
{
    for (typename set<T>::iterator it = v.begin(); it != v.end(); it++)
    {
        cout << *it;
    }
    cout << endl;
}

// 自动排序，从小到大，剔除相同项
set<int> s1{9,8,1,2,3,4,5,5,5,6,7,7 }; 
showset(s1);
// 字典序 排序
set<string> s2{ "hello","sysy","school","hello" }; 
showset(s2);
// 有这个值了，do nothing
s1.insert(9);
showset(s1);
// 没有这个字符串，添加并且排序
s2.insert("aaa"); 
showset(s2);

同样，若在集合中插入结构体等数据，我们可以重载 <, > 等运算符，实现集合内元素的自动排序。

其他常见调用

在使用 multiset 时，也只需引用头文件 set 即可。

int values[] = {3, 5, 1, 7, 2, 2};
multiset<int> s(values, values + 6);

multiset<int>::iterator p;
for (p = s.begin(); p != s.end(); p++){
    cout << *p << " ";
} cout << endl;

s.insert(12);
s.insert(11);

// 默认降序
// multiset<int, greater<int> >

// 查找 2 第一次出现
p = s.lower_bound(2);
// 查找 2 最后一次出现
p = s.upper_bound(2);
cout << *p << endl;

// 查找
p = s.find(13);
if (p == s.end()){
    cout << "not found" << endl;
} else {
    cout << "found" << endl;
}

// 计数
cout << s.count(2) << endl;

// 删除所有的 2
s.erase(2);
for (p = s.begin(); p != s.end(); p++){
    cout << *p << " ";
} cout << endl;