笔记C++复健笔记

C++复健笔记 Vol.4：map 和 set

3175 字 约 16 分钟
C++/STL/学习笔记
摘要

复习常用的关联容器：用 set 去重和维护有序集合，用 map 统计、映射和查找。

上一篇复习了 vector 和 string，它们更像是“按位置访问”的容器。这一篇补两个很常见的关联容器：set 和 map。

简单说：

  • set：存一堆不重复的元素，并且自动有序。
  • map：存键值对，也就是从 key 映射到 value，并且按 key 自动有序。

机考里遇到“去重”“统计次数”“名字对应分数”“查某个东西是否出现过”之类的需求，经常就会用到它们。

set：有序去重集合

set 需要头文件：

#include <set>

基本用法：

#include <iostream>
#include <set>
using namespace std;

int main() {
    set<int> s;

    s.insert(3);
    s.insert(1);
    s.insert(2);
    s.insert(3);

    for (int x : s) {
        cout << x << ' ';
    }
    cout << '\n';

    return 0;
}

输出是：

1 2 3

注意两个特点：

  • 重复插入的 3 只会保留一个。
  • 遍历时是升序。

常用操作：

  • s.insert(x)：插入元素。
  • s.erase(x)：删除值为 x 的元素。
  • s.count(x)：判断 x 是否存在，返回 0 或 1。
  • s.find(x)：查找 x，返回迭代器。
  • s.size()：元素个数。
  • s.empty()：是否为空。
  • s.clear()：清空。

判断一个数是否出现过：

if (s.count(x)) {
    cout << "yes" << '\n';
} else {
    cout << "no" << '\n';
}

也可以用 find：

auto it = s.find(x);
if (it != s.end()) {
    cout << "found" << '\n';
}

lower_bound 和 upper_bound

set 自己也有 lower_bound 和 upper_bound。

auto it = s.lower_bound(x);

lower_bound(x) 找第一个大于等于 x 的元素。

auto it = s.upper_bound(x);

upper_bound(x) 找第一个大于 x 的元素。

例子：

set<int> s = {1, 3, 5, 7};

auto it = s.lower_bound(4);
if (it != s.end()) {
    cout << *it << '\n'; // 5
}

如果要找小于等于 x 的最大值，可以这样写：

auto it = s.upper_bound(x);
if (it != s.begin()) {
    --it;
    cout << *it << '\n';
}

这里要先判断 it != s.begin()，否则 --it 会越界。迭代器这东西，平时看着很优雅，一越界就很有自己的想法。

set 的排序方式

默认是升序。

如果想降序：

set<int, greater<int>> s;

自定义结构体也可以放进 set，但要告诉它怎么比较。

struct Node {
    int x;
    int y;
};

struct Cmp {
    bool operator()(const Node& a, const Node& b) const {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    }
};

set<Node, Cmp> s;

对机考来说，更常见的写法其实是直接用 pair：

set<pair<int, int>> s;

pair 默认先比较 first，再比较 second，很多时候够用了。

multiset：允许重复的 set

set 不存重复元素。如果需要有序，并且允许重复，可以用 multiset。

multiset<int> s;

s.insert(1);
s.insert(1);
s.insert(2);

cout << s.count(1) << '\n'; // 2

但是删除时要注意：

s.erase(1);

这会把所有值为 1 的元素都删掉。

如果只想删一个，可以先 find：

auto it = s.find(1);
if (it != s.end()) {
    s.erase(it);
}

这个坑很常见，尤其是维护一个可以重复的有序集合时。

map：键值映射

map 需要头文件：

#include <map>

基本用法：

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    map<string, int> score;

    score["Alice"] = 90;
    score["Bob"] = 85;
    score["Alice"] = 95;

    cout << score["Alice"] << '\n';
    cout << score["Bob"] << '\n';

    return 0;
}

map<K, V> 表示从类型 K 映射到类型 V。

比如：

  • map<string, int>：名字到分数。
  • map<int, string>：编号到名字。
  • map<char, int>：字符到出现次数。
  • map<string, vector<int>>：名字到一组成绩。

用 map 统计次数

统计每个数字出现几次：

int n;
cin >> n;

map<int, int> cnt;

for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    cnt[x]++;
}

for (const auto& p : cnt) {
    cout << p.first << ' ' << p.second << '\n';
}

这里 cnt[x]++ 很方便：如果 x 原来不存在，cnt[x] 会先被默认初始化成 0，然后再加一。

遍历 map 时，拿到的是 pair<const K, V>：

for (const auto& p : cnt) {
    cout << p.first << ' ' << p.second << '\n';
}

C++17 以后也可以写结构化绑定：

for (const auto& [key, value] : cnt) {
    cout << key << ' ' << value << '\n';
}

这个写法很舒服，但如果考场环境比较老，就还是用 p.first 和 p.second 稳一点。

map 的查找

判断某个 key 是否存在：

if (mp.count(key)) {
    cout << "exists" << '\n';
}

或者：

auto it = mp.find(key);
if (it != mp.end()) {
    cout << it->second << '\n';
}

这里 it->first 是 key，it->second 是 value。

需要特别注意 operator[]：

cout << mp[key] << '\n';

如果 key 不存在，这句会把它插入到 map 里，并把 value 默认初始化。

比如：

map<string, int> mp;

cout << mp["unknown"] << '\n';
cout << mp.size() << '\n'; // 1

所以如果只是想“查一下有没有”，不要随手写 mp[key]，用 count 或 find 更稳。

map 的遍历顺序

map 会按 key 从小到大遍历。

map<string, int> mp;
mp["banana"] = 2;
mp["apple"] = 3;
mp["cat"] = 1;

for (const auto& p : mp) {
    cout << p.first << ' ' << p.second << '\n';
}

输出顺序是：

apple 3
banana 2
cat 1

如果题目要求按字典序输出统计结果，map 就很顺手。

如果不需要有序，只关心查找和统计，可以考虑 unordered_map。

unordered_map 和 unordered_set

unordered_map 和 unordered_set 是哈希表，平均查找和插入更快，但不保证遍历顺序。

需要头文件：

#include <unordered_map>
#include <unordered_set>

常见用法：

unordered_map<string, int> cnt;
cnt["apple"]++;

unordered_set<int> appeared;
appeared.insert(x);

怎么选：

  • 需要有序输出、找前驱后继、用 lower_bound：用 map / set。
  • 只需要快速判断存在、统计次数：可以用 unordered_map / unordered_set。

不过机考里如果数据量不大，map 和 set 已经够用，而且行为更稳定、遍历有序，调试时也更直观。

小练习：统计单词出现次数

读入一整行，统计每个单词出现几次，并按字典序输出。

#include <iostream>
#include <map>
#include <sstream>
#include <string>
using namespace std;

int main() {
    string line;
    getline(cin, line);

    stringstream ss(line);
    string word;
    map<string, int> cnt;

    while (ss >> word) {
        cnt[word]++;
    }

    for (const auto& p : cnt) {
        cout << p.first << ": " << p.second << '\n';
    }

    return 0;
}

输入：

cpp is good and cpp is useful

输出：

and: 1
cpp: 2
good: 1
is: 2
useful: 1

小结

  • set：有序、不重复，适合去重、判断存在、维护有序集合。
  • multiset：有序、允许重复，删除一个元素时要用迭代器。
  • map：按 key 有序的键值映射，适合统计次数和建立对应关系。
  • mp[key] 会在 key 不存在时插入默认值，只查找时优先用 count 或 find。
  • 需要哈希表时可以用 unordered_map / unordered_set，但它们不保证遍历顺序。

下一篇可以继续补 stack、queue、deque 和 priority_queue，这些容器写 BFS、模拟和堆相关题目时特别常用。