map 和 set

第 13 课，共 30 课 · 第 3 部分 · 容器 · 约 15 分钟

vector 用 0、1、2 这样的下标找元素。可很多时候我们想用名字去找：苹果多少钱、小林几分。std::map 就是一张两列的表：左边是键，右边是值，用键找值。要 #include <map>。

main.cpp

1#include <iostream>2#include <map>3#include <string>4 5int main() {6    std::map<std::string, double> prices;7    prices["苹果"] = 6.5;8    prices["香蕉"] = 3.2;9    std::cout << "香蕉：" << prices["香蕉"] << " 元\n";10    std::cout << "一共 " << prices.size() << " 种\n";11    return 0;12}

输出

香蕉：3.2 元
一共 2 种

std::map<std::string, double>：键是字符串，值是 double。prices["苹果"] = 6.5 存进去，prices["香蕉"] 取出来，和 vector 的方括号很像，只是方括号里放的是键。

存和改

map 也可以用花括号一开始就放好几对，每一对写成 {键, 值}。同一个键只有一个值：再给它赋值，就是改掉原来的。点单步，看 stock 显示成一对一对的：

main.cpp

1#include <iostream>2#include <map>3#include <string>4 5int main() {6    std::map<std::string, int> stock{{"苹果", 5}, {"梨", 3}};7    stock["苹果"] += 2;8    stock["橙子"] = 10;9    std::cout << "苹果：" << stock["苹果"] << '\n';10    std::cout << "一共 " << stock.size() << " 种\n";11    return 0;12}

输出

苹果：7
一共 3 种

stock["橙子"] = 10 时，表里还没有橙子，就新加一对；stock["苹果"] += 2 时已经有了，就在原来的值上改。

按键排好序

范围 for 能走遍一个 map。每一圈拿到的是一对：.first 是键，.second 是值。不管你按什么顺序放进去，map 总是按键从小到大排好。点单步，看新的一对插到哪里：

main.cpp

1#include <iostream>2#include <map>3#include <string>4 5int main() {6    std::map<int, std::string> rooms;7    rooms[305] = "小林";8    rooms[101] = "小王";9    rooms[210] = "小张";10    for (const auto& kv : rooms) {11        std::cout << kv.first << " 号房：" << kv.second << '\n';12    }13    return 0;14}

输出

101 号房：小王
210 号房：小张
305 号房：小林

这里每一对的类型很长，所以写 const auto&。C++17 起还可以写成 for (const auto& [room, name] : rooms)，这门课只用 C++14，写 .first 和 .second。

注意： 还有一种 std::unordered_map，查得更快，但走一遍的顺序不固定，每台电脑上都可能不一样。

m[key] 的坑

用方括号取一个不存在的键，会怎样？

先猜一猜

这段程序显示什么？

1#include <iostream>2#include <map>3#include <string>4 5int main() {6    std::map<std::string, int> stock{{"苹果", 5}};7    std::cout << stock["香蕉"] << '\n';8    std::cout << stock.size() << '\n';9    return 0;10}

stock["香蕉"] 找不到香蕉，就悄悄新建一对 {"香蕉", 0}，再把 0 给你。所以表里变成了两对。

输出

方括号找不到就新建：数数的时候很方便（下面数单词就靠它），只想看看有没有的时候却是个坑，表里会多出一堆 0。

查一查、删一个

只想知道有没有，不想新建，用这几个：

写法	做什么
`m.count(key)`	有这个键是 1，没有是 0
`m.find(key)`	找到的那一对；找不到时等于 `m.end()`
`m.at(key)`	取值；没有这个键就抛出 `std::out_of_range`
`m.erase(key)`	删掉这个键和它的值

main.cpp

1#include <iostream>2#include <map>3#include <string>4 5int main() {6    std::map<std::string, int> scores{{"小林", 92}, {"小王", 78}};7    if (scores.count("小张") == 0) {8        std::cout << "没有小张\n";9    }10    auto it = scores.find("小王");11    if (it != scores.end()) {12        std::cout << "小王：" << it->second << '\n';13    }14    scores.erase("小王");15    std::cout << "还剩 " << scores.size() << " 人\n";16    return 0;17}

输出

没有小张
小王：78
还剩 1 人

find 给的是一个迭代器，指着找到的那一对；-> 拿的是它指着的那一对里的成员，所以 it->second 就是值。迭代器第 27 课再讲。大多数时候 count 就够了。

数单词

map 最常见的用处之一是数数。counts[w]++：第一次见到 w，方括号新建一个 0，再加 1；以后每见一次加 1。

main.cpp

1#include <iostream>2#include <map>3#include <string>4#include <vector>5 6int main() {7    std::vector<std::string> words{"猫", "狗", "猫", "鱼", "猫", "狗"};8    std::map<std::string, int> counts;9    for (const auto& w : words) {10        counts[w]++;11    }12    for (const auto& kv : counts) {13        std::cout << kv.first << "：" << kv.second << '\n';14    }15    return 0;16}

输出

狗：2
猫：3
鱼：1

点单步，看 counts 里的数怎么一个一个涨上去。「狗」排在「猫」前面，是因为按编码排。

set：不重复、排好序

std::set（在 <set> 里）只有键，没有值。同一个值放进去两次，只留一个；走一遍时总是从小到大：

main.cpp

1#include <iostream>2#include <set>3 4int main() {5    std::set<int> seen;6    seen.insert(42);7    seen.insert(7);8    seen.insert(42);9    seen.insert(19);10    std::cout << "有 " << seen.size() << " 个\n";11    for (int x : seen) {12        std::cout << x << " ";13    }14    std::cout << '\n';15    std::cout << "有 7 吗？" << seen.count(7) << '\n';16    return 0;17}

输出

有 3 个
7 19 42 
有 7 吗？1

insert 往里放，count 查有没有（1 或 0），erase 删掉。要「去掉重复的」「看看出现过没有」，就用 set。

练一练

写好代码，点检查。提示随便看，实在想不出来再看答案。

练习 1

仓库一共几件

写好 total_count：走一遍 stock，把所有的数量加起来交回去。main 已经写好了，会显示两个仓库各有几件。

要显示

厨房：18 件
办公室：35 件

exercise1.cpp

1#include <iostream>2#include <map>3#include <string>4 5int total_count(const std::map<std::string, int>& stock) {6    int total = 0;7 8    return total;9}10 11int main() {12    std::map<std::string, int> kitchen{{"杯子", 6}, {"盘子", 8}, {"碗", 4}};13    std::map<std::string, int> office{{"笔", 20}, {"本子", 15}};14    std::cout << "厨房：" << total_count(kitchen) << " 件\n";15    std::cout << "办公室：" << total_count(office) << " 件\n";16    return 0;17}

输出

点「运行」或按 Ctrl+Enter

练习 2

每个字母几次

数一数 word 里每个字母出现几次，按字母顺序显示。

要显示

a：3
b：1
n：2

exercise2.cpp

1#include <iostream>2#include <map>3#include <string>4 5int main() {6    std::string word = "banana";7 8    return 0;9}

输出

点「运行」或按 Ctrl+Enter

练习 3

修好它：set 不用 push_back

这段程序编译不过。改好它，让它显示一共打过几个不同的号码：不同的号码：3 个。

要显示

不同的号码：3 个

exercise3.cpp

1#include <iostream>2#include <set>3#include <vector>4 5int main() {6    std::vector<int> calls{110, 120, 110, 119, 120};7    std::set<int> seen;8    for (int c : calls) {9        seen.push_back(c);10    }11    std::cout << "不同的号码：" << seen.size() << " 个\n";12    return 0;13}

输出

点「运行」或按 Ctrl+Enter

这一课学会了

std::map<键类型, 值类型> 用键找值，要 #include <map>；m[key] = value 存或改。
走一遍 map 时按键从小到大，每一对用 .first（键）和 .second（值）。
m[key] 找不到会新建一个默认值（0、空字符串）：数数时正好，只想看看时是坑。
查有没有用 count（1 或 0）或 find（找不到等于 end()）；at 找不到会抛出异常；erase 删除。
counts[w]++ 是数单词的老办法。
std::set 只放不重复的值、自动排好序；insert、count、erase。