{ }codelper

学习 › C++

进阶 · 16

字典（映射）

按键查找和修改值：统计单词、判断键是否存在、按键的顺序遍历。

字典（映射）不是按位置，而是按键来查找值。
下面的示例统计每个单词出现的次数，查找被问到的单词，再按键的顺序全部输出。

#include <iostream>#include <map>#include <set>#include <sstream>#include <string>#include <vector> std::vector<std::string> readWords() {    std::string line, w;    std::getline(std::cin, line);    std::istringstream in(line);    std::vector<std::string> out;    while (in >> w) out.push_back(w);    return out;} int main() {    std::vector<std::string> words = readWords(), queries = readWords();    std::cout << std::set<std::string>(words.begin(), words.end()).size() << '\n';    std::map<std::string, int> counts;    for (const auto& w : words) counts[w]++;    for (const auto& q : queries) {        if (counts.contains(q)) std::cout << q << ' ' << counts.at(q) << '\n';        else std::cout << q << " none\n";    }    for (const auto& [w, c] : counts) std::cout << w << ' ' << c << '\n';}
stdin
apple banana apple cherry banana apple
banana grape
stdout
3
banana 2
grape none
apple 3
banana 2
cherry 1

要点

  • 把键和值配成对，比如 "apple" → 3。
    插入、查找、修改都比从头扫描列表快得多。
  • 最常见的用法是计数。
    第一次见到的单词从 0 开始，再加 1。
  • 读取不存在的键时，各语言差别最大：报错、得到空值，或者新建一个条目。
    所以要先检查。
  • 不要依赖遍历顺序。
    有的语言保持插入顺序，有的什么都不保证。
    示例先把键排序再输出，所以每种语言结果都一样。
  • 只有键没有值的就是集合。
    不同单词的个数就是集合的大小。

各语言的写法

Pythoncounts = {} — 计数 counts.get(w, 0) + 1，检查 w in counts。
用 [] 读不存在的键报 KeyError。
保持插入顺序。
集合用 set
JavaScriptnew Map() — 计数 (counts.get(w) ?? 0) + 1，检查 has。
不存在时 get 返回 undefined。
保持插入顺序。
集合用 Set
TypeScript和 JavaScript 一样。
像 new Map<string, number>() 这样写出类型
JavaHashMap（不保证顺序）、LinkedHashMap（插入顺序）、TreeMap（按键排序）。
计数 merge(w, 1, Integer::sum)，检查 containsKey，不存在时 get 返回 null。
集合用 HashSet
C#Dictionary<string, int> — 计数 GetValueOrDefault(w) + 1，检查 TryGetValue。
用索引器读不存在的键报 KeyNotFoundException。
顺序未定义（按键排序用 SortedDictionary）。
集合用 HashSet
C++std::map（按键排序）、std::unordered_map（不保证顺序）。
计数 counts[w]++，检查用 C++20 的 contains。
用 [] 读不存在的键会新建一个值为 0 的条目。
集合用 std::set
C没有内置字典。
示例把键数组和值数组并排放着，从头查找（输入不大时足够了）
Craykon字典() — 用 d["苹果"] = 3 写入和读取。
检查用 d.包含(键)，d.键列表 按插入顺序。
读取不存在的键会像 Python 一样因运行时错误而停止

常见错误

想检查一下，用 [] 读却多出了条目C++

std::map<std::string, int> counts;
if (counts["grape"] == 0) { }
std::cout << counts.size();

→ 1 — 只是读了一下，就新建了值为 0 的 "grape" 条目

检查请用 counts.contains(w)（C++20）或 counts.find(w)。

以为会按插入顺序输出Java · C# · C++

Map<String, Integer> m = new HashMap<>();
m.put("pear", 1); m.put("apple", 2); m.put("fig", 3);
System.out.println(m.keySet());

→ [apple, pear, fig] — 和插入顺序（pear, apple, fig）不同

先把键排序再输出，或者用保证顺序的 TreeMap、LinkedHashMap（C++ std::map、C# SortedDictionary）。

直接读取不存在的键Python · C# · Craykon

counts = {"apple": 3}
print(counts["grape"])

→ 报 KeyError: 'grape' 并停止（C# 报 KeyNotFoundException，Craykon 提示字典里没有 "grape" 这个键）

先检查，或者像 Python 的 get(w, 0) 那样给默认值。

各语言的差异
在 JavaScript 里用空对象 {} 计数，"constructor" 这样的单词会和 Object.prototype 上的属性冲突，而 "10" 这样像数字的键不管插入顺序如何都会按升序排在最前面。
计数请用 Map。

练习题

  1. 电话簿查找8P0063
  2. 单词频率排名8P0034
  3. 删除重复的数8P0035
  4. 按扫描顺序数商品8P0220
  5. 只算最后一票的投票8P0228
  6. 按零件编码范围查库存8P0229
  7. 找出互相选择的搭档8P0256
  8. 商店库存管理8P0064