C++ 集合、映射与词频统计｜C++ 第 16 课

Easy explanation

集合像门禁名单，映射像带索引的字典。

门卫只需要快速判断名字是否在名单里，不关心这个名字排在第几个，这适合集合。字典则根据单词找到解释，通讯录根据姓名找到电话，这种“键对应值”的关系适合映射。选择结构时先看问题问的是存在性，还是需要从键取得附加信息。

有序容器 set 和 map 会自动按键排序，底层通常是平衡树；unordered 版本使用哈希，平均查询更快，但遍历顺序不固定。输出需要稳定排序时选 map，只关心快速查询时可考虑 unordered_map。

目标 1使用 set 自动去重并判断存在

目标 2使用 map 建立键值关系

目标 3理解有序容器与哈希容器差异

目标 4完成词频统计和按频率排序

C++ 集合、映射与词频统计通俗学习插图 — 集合保存唯一键，映射在唯一键旁再保存一个对应值。

Core concepts

先把四个核心知识点说清楚。

01

唯一集合

set<string> names;

同一个值只保存一次，insert 返回是否插入成功，count 或 contains 判断存在。

02

键值映射

map<string, int> scores;

每个键对应一个值。方括号访问不存在的键时会自动创建默认值。

03

哈希容器

unordered_map<string, int> frequency;

平均查询接近常数时间，但没有排序保证，自定义键还需要哈希规则。

04

安全查询

auto it = data.find(key);

只想查询时使用 find，避免 operator[] 意外创建一条不存在的记录。

unique.insert(value);

重复值不会增加集合大小。

++frequency[word];

不存在的单词先得到零，再加一，适合频率统计。

data.erase(key);

按键删除并返回删除数量，可判断目标原先是否存在。

for (const auto& [key, value] : data)

结构化绑定让遍历键和值更直观。

Complete examples

两个例子，把知识变成能运行的程序。

Example 1

例子一：通讯录增查改

姓名作为键，电话作为值。添加前检查键是否存在，可以阻止误覆盖；修改则要求记录已经存在。

find 返回迭代器，it->second 是电话号码。这里只读查询不会创建空联系人。

姓名映射到电话号码

map<string, string> contacts;
contacts.emplace("Mia", "0151-1234");
contacts.emplace("Tom", "0176-8888");

string name = "Mia";
auto it = contacts.find(name);
if (it != contacts.end())
    cout << name << "：" << it->second << '\n';
else
    cout << "没有这个联系人\n";

contacts["Tom"] = "0176-9999";
for (const auto& [person, phone] : contacts)
    cout << person << " -> " << phone << '\n';

Mia：0151-1234Mia -> 0151-1234Tom -> 0176-9999

Example 2

例子二：文章词频排行榜

先把单词转成小写并去掉标点，再用 unordered_map 计数。映射适合查询，但不按次数排序，所以最后复制成 vector。

排序比较器先比较次数，次数相同按单词字母顺序，输出会稳定且容易测试。

清理、计数、再排序

unordered_map<string, int> freq;
string word;
while (cin >> word)
{
    string clean;
    for (char ch : word)
        if (isalpha(static_cast<unsigned char>(ch)))
            clean += static_cast<char>(tolower(ch));
    if (!clean.empty()) ++freq[clean];
}

vector<pair<string, int>> ranking(freq.begin(), freq.end());
sort(ranking.begin(), ranking.end(), [](const auto& a, const auto& b)
{
    if (a.second != b.second) return a.second > b.second;
    return a.first < b.first;
});

输入：Code is fun. Code is useful.code -> 2is -> 2fun -> 1useful -> 1

Algorithm thinking

先确定键，再决定值和顺序。

映射设计最关键的是键必须稳定且能唯一识别记录。姓名可能重复，学生系统更适合用学号；商品名可能变化，库存系统应使用商品编号。值可以是一个数字，也可以是包含多个字段的对象。

去重、查询和排序是不同需求。set 自动按值有序且唯一；unordered_set 只保证唯一；map 按键有序；词频按次数排序则需要额外把键值对放进 vector。不要期待一个容器同时自动满足所有顺序。

1
选择唯一键
确认键稳定、可比较，并且不会让两条不同记录互相覆盖。
2
选择有序或哈希
需要按键输出选 map，只重视平均查询速度可选 unordered_map。
3
区分查询与创建
查询使用 find，明确要新增或计数时再使用方括号。
4
单独处理结果排序
按值排序时复制到 vector，并写清楚比较规则。

Common mistakes

这些错误很常见，学会自己排查。

1

查询时意外新增

data[key] 会插入默认值，判断存在应使用 find 或 contains。

2

依赖哈希遍历顺序

unordered 容器输出顺序可能变化，测试不能假定固定排列。

3

键选择不唯一

用姓名当学生键会覆盖同名者，应使用学号等稳定标识。

4

边遍历边随意修改

删除当前元素要使用正确迭代器写法，避免访问失效位置。

本课通用调试法

先准备一个最小输入，只保留能够重现问题的几行数据；再在关键步骤输出变量值，确认程序究竟在哪一步偏离预期。编译错误从第一条开始处理，运行错误则比较“实际结果”和“期望结果”。修复后别只重跑原来的例子，还要增加空输入、边界值和错误输入，防止问题换一个形式再次出现。

Homework

第 16 课课后作业：从模仿到独立完成。

建议按顺序完成。前四题帮助巩固语法和基本操作，第五到第七题要求把多个知识点组合起来，第八题是小项目。每道题都要先写输入、处理、输出三行计划，再开始敲代码；程序运行后至少测试正常情况、边界情况和错误情况。

1

名单去重

输入一组姓名，输出不重复名单、重复次数和按字母排序结果。

2

集合运算

计算两个 set 的交集、并集和差集，并用课程报名名单解释含义。

3

成绩映射

学号映射到 Student，支持添加、查询、修改和删除，拒绝重复学号。

4

字符频率

统计一行中每个字母出现次数，忽略大小写和非字母字符。

5

购物清单

商品名映射到数量，重复添加时累加，数量降到零时删除。

6

投票系统

set 保存已投票用户，map 统计候选人票数，阻止重复投票。

7

两数之和

使用 unordered_set 在线性时间内判断是否存在两个数之和等于目标。

8

词频项目

读取多行文章，清理文本，输出总词数、不同单词数和前十排行榜。

本课验收标准：能说明键和值各代表什么；查询不会意外插入；知道 map 与 unordered_map 的顺序差异；完成至少一次去重、频率计数和按值排序。

提交内容应包括源代码、三组测试输入与输出、一个曾经出现的错误及修复方法。最后请用自己的话解释本课最重要的概念；如果只能照着代码念，还需要再独立重写一次核心例子。

Lesson 16 summary

集合回答“有没有”，映射回答“这个键对应什么”。

setmapunordered_mapfindfrequency

下一课回到指针，观察链表节点如何一个接一个连接，并比较链表与连续容器的取舍。

进入第 17 课返回第 15 课查看课程大纲