Ch 15: std::unordered_map

本章目标

• 深入理解 unordered_map 和 map 的本质区别
• 熟练使用 unordered_map 的各种操作 API
• 学会安全访问（避免插入默认值陷阱）
• 掌握自定义哈希函数和 key 类型
• 理解哈希表的性能特点和调优方法

15.1 Python dict vs C++ unordered_map

Python dict 回顾

# Python - 字典（哈希表实现）
d = {"apple": 1, "banana": 2, "cherry": 3}

# 添加/修改
d["date"] = 4
d["apple"] = 10

# 安全访问
x = d.get("elderberry", 0)  # 默认值 0
y = d.get("apple")          # 10

# 检查存在
if "banana" in d:
    del d["banana"]

# 遍历
for key in d:
    print(key, d[key])

for key, value in d.items():
    print(f"{key}: {value}")

# 字典推导
squares = {k: k**2 for k in range(5)}
filtered = {k: v for k, v in d.items() if v > 1}

C++ unordered_map 基础

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    // 构造
    std::unordered_map<std::string, int> scores;

    // 添加元素
    scores["apple"] = 1;
    scores["banana"] = 2;
    scores["cherry"] = 3;

    // 初始化列表 (C++11)
    std::unordered_map<std::string, int> scores2 = {
        {"apple", 1},
        {"banana", 2},
        {"cherry", 3}
    };

    // 访问
    int x = scores["apple"];          // 获取，不存在会插入默认值 0
    // int y = scores["grape"];      // scores["grape"] = 0 自动插入！

    // at() - 安全访问
    int a = scores.at("apple");      // 存在则返回
    // scores.at("grape")             // 抛出 std::out_of_range

    // find() - 查找
    auto it = scores.find("banana");
    if (it != scores.end()) {
        std::cout << "Found: " << it->second << std::endl;
    }

    // C++20 contains
    if (scores.contains("apple")) {  // C++20
        scores["apple"] = 100;
    }

    // 删除
    scores.erase("cherry");

    // 大小
    std::size_t sz = scores.size();
    bool empty = scores.empty();

    // 遍历
    for (const auto& [key, value] : scores) {  // C++17 结构化绑定
        std::cout << key << ": " << value << std::endl;
    }

    return 0;
}

关键区别总结

特性	Python dict	C++ unordered_map
底层实现	哈希表	哈希表
有序遍历	Python 3.7+ 保证插入顺序	无序
默认值	get(k, default)	[] 插入默认值
类型安全	运行时检查	编译时检查
空字典	{}	std::unordered_map<K,V>()

15.2 unordered_map vs map（选择正确的数据结构）

底层数据结构对比

#include <map>
#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    // std::map - 红黑树实现，自动排序
    std::map<std::string, int> ordered = {
        {"banana", 2},
        {"apple", 1},
        {"cherry", 3}
    };
    std::cout << "map order: ";
    for (const auto& [k, v] : ordered) {
        std::cout << k << " ";  // apple banana cherry（按字母排序）
    }
    std::cout << std::endl;

    // std::unordered_map - 哈希表实现
    std::unordered_map<std::string, int> hash = {
        {"banana", 2},
        {"apple", 1},
        {"cherry", 3}
    };
    std::cout << "unordered_map order: ";
    for (const auto& [k, v] : hash) {
        std::cout << k << " ";  // 顺序不确定
    }
    std::cout << std::endl;

    return 0;
}

选择决策树

需要有序遍历 key？
├── 是 → std::map（O(log n) 查找）
└── 否 → 需要最高性能查找？
         ├── 是 → std::unordered_map（O(1) 平均）
         └── 否 → std::unordered_map

性能对比

#include <map>
#include <unordered_map>
#include <chrono>
#include <iostream>

int main() {
    const int N = 100000;

    std::map<int, int> ordered_map;
    std::unordered_map<int, int> hash_map;

    // 插入
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) {
        ordered_map[i] = i;
    }
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << "map insert: "
              << std::chrono::duration<double>(end - start).count() << "s\n";

    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) {
        hash_map[i] = i;
    }
    end = std::chrono::high_resolution_clock::now();
    std::cout << "unordered_map insert: "
              << std::chrono::duration<double>(end - start).count() << "s\n";

    // 查找
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) {
        volatile int x = ordered_map[i];
    }
    end = std::chrono::high_resolution_clock::now();
    std::cout << "map find: "
              << std::chrono::duration<double>(end - start).count() << "s\n";

    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < N; ++i) {
        volatile int x = hash_map[i];
    }
    end = std::chrono::high_resolution_clock::now();
    std::cout << "unordered_map find: "
              << std::chrono::duration<double>(end - start).count() << "s\n";

    return 0;
}

何时用 map（有序）

#include <map>
#include <string>
#include <iostream>

int main() {
    // 场景 1：需要按 key 排序遍历
    std::map<std::string, int> word_count = {
        {"zebra", 1},
        {"apple", 2},
        {"mango", 3}
    };

    std::cout << "Alphabetical order:\n";
    for (const auto& [word, count] : word_count) {
        std::cout << word << ": " << count << "\n";
    }
    // apple, mango, zebra（字母序）

    // 场景 2：需要范围查询
    // 找所有 "a" 到 "m" 开头的词
    auto lower = word_count.lower_bound("a");
    auto upper = word_count.upper_bound("n");
    for (auto it = lower; it != upper; ++it) {
        std::cout << it->first << "\n";
    }

    // 场景 3：需要知道前驱/后继
    auto it = word_count.find("mango");
    if (it != word_count.end()) {
        auto prev = std::prev(it);
        auto next = std::next(it);
        if (prev != word_count.end()) {
            std::cout << "Prev: " << prev->first << "\n";
        }
        if (next != word_count.end()) {
            std::cout << "Next: " << next->first << "\n";
        }
    }

    return 0;
}

15.3 基本操作详解

构造和初始化

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    // 1. 默认构造
    std::unordered_map<std::string, int> empty_map;

    // 2. 初始化列表
    std::unordered_map<std::string, int> scores = {
        {"Alice", 95},
        {"Bob", 87},
        {"Charlie", 92}
    };

    // 3. 拷贝构造
    std::unordered_map<std::string, int> copy(scores);

    // 4. 移动构造
    std::unordered_map<std::string, int> moved(std::move(copy));
    // copy 现在是空容器

    // 5. 从迭代器范围构造
    std::vector<std::pair<std::string, int>> data = {
        {"David", 88},
        {"Eve", 91}
    };
    std::unordered_map<std::string, int> from_vector(data.begin(), data.end());

    // 6. 指定 bucket 数量（性能优化）
    std::unordered_map<std::string, int> reserved;
    reserved.reserve(1000);  // 预分配 bucket
    reserved.max_load_factor(0.7);  // 调整负载因子

    std::cout << "Size: " << moved.size() << std::endl;

    return 0;
}

添加和修改元素

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> ages;

    // operator[] - 添加或修改
    ages["Alice"] = 25;         // 添加
    ages["Bob"] = 30;
    ages["Alice"] = 26;          // 修改现有

    // insert - 显式插入
    ages.insert({"Charlie", 28});    // C++11
    ages.insert(std::make_pair("David", 35));

    // insert_or_assign - 插入或覆盖（C++17）
    ages.insert_or_assign("Eve", 40);
    ages.insert_or_assign("Alice", 27);  // 覆盖现有

    // emplace - 原位构造（C++11，更高效）
    ages.emplace("Frank", 32);
    ages.emplace(std::piecewise_construct,
                 std::forward_as_tuple("Grace"),
                 std::forward_as_tuple(29));

    // 尝试插入（不覆盖现有）
    auto [it, inserted] = ages.emplace("Alice", 99);  // 不会覆盖
    if (!inserted) {
        std::cout << "Alice already exists with age " << it->second << "\n";
    }

    // 遍历
    for (const auto& [name, age] : ages) {
        std::cout << name << ": " << age << "\n";
    }

    return 0;
}

查找和访问

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> scores = {
        {"Alice", 95},
        {"Bob", 87}
    };

    // ❌ 危险：operator[] 会在不存在时插入
    int x = scores["Charlie"];  // scores["Charlie"] = 0 自动插入！
    std::cout << "Size after []: " << scores.size() << std::endl;  // 3

    // ✅ 安全访问方式 1：at()
    try {
        int y = scores.at("Alice");        // 95
        // int z = scores.at("David");     // 抛出 std::out_of_range
    } catch (const std::out_of_range& e) {
        std::cout << "Key not found: " << e.what() << "\n";
    }

    // ✅ 安全访问方式 2：find()
    auto it = scores.find("Bob");
    if (it != scores.end()) {
        std::cout << "Found Bob: " << it->second << "\n";
    } else {
        std::cout << "Bob not found\n";
    }

    auto it2 = scores.find("David");
    if (it2 == scores.end()) {
        std::cout << "David not found\n";
    }

    // ✅ C++20 安全访问方式 3：contains()
    if (scores.contains("Alice")) {
        std::cout << "Alice is in the map\n";
    }

    // ✅ C++20 value_or（类似 Python dict.get）
    int default_age = 0;
    int eve_age = scores.value_or("Eve", default_age);  // 如果不存在，返回 0

    // 统计查找
    std::cout << "Bucket count: " << scores.bucket_count() << "\n";
    std::cout << "Load factor: " << scores.load_factor() << "\n";

    return 0;
}

删除操作

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> ages = {
        {"Alice", 25},
        {"Bob", 30},
        {"Charlie", 28},
        {"David", 35}
    };

    // 1. 按 key 删除
    std::size_t removed = ages.erase("Charlie");  // 返回删除数量（0 或 1）
    std::cout << "Removed " << removed << " element(s)\n";

    // 2. 迭代器删除
    auto it = ages.find("Bob");
    if (it != ages.end()) {
        ages.erase(it);  // 删除 Bob
    }

    // 3. 范围删除
    ages.erase(ages.begin(), ages.begin() + 1);  // 删除第一个

    // 4. 清空
    ages.clear();  // 所有元素删除，size 变为 0

    // 5. 条件删除（Lambda）
    ages = {{"Alice", 25}, {"Bob", 30}, {"Charlie", 35}};
    for (auto it = ages.begin(); it != ages.end(); ) {
        if (it->second > 30) {
            it = ages.erase(it);  // erase 返回下一个迭代器
        } else {
            ++it;
        }
    }
    // 删除年龄 > 30 的

    std::cout << "Remaining: ";
    for (const auto& [name, age] : ages) {
        std::cout << name << "(" << age << ") ";
    }
    std::cout << "\n";

    return 0;
}

15.4 遍历详解

基本遍历方式

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> scores = {
        {"Alice", 95},
        {"Bob", 87},
        {"Charlie", 92}
    };

    // 方式 1：C++17 结构化绑定（推荐）
    std::cout << "Using structured bindings:\n";
    for (const auto& [name, score] : scores) {
        std::cout << name << ": " << score << "\n";
    }

    // 方式 2：传统迭代器
    std::cout << "\nUsing iterators:\n";
    for (auto it = scores.begin(); it != scores.end(); ++it) {
        std::cout << it->first << ": " << it->second << "\n";
    }

    // 方式 3：反向遍历（unorderd_map 不保证顺序，所以反向意义不大）
    // 但可以用 rbegin/rend
    std::cout << "\nReverse:\n";
    for (auto it = scores.rbegin(); it != scores.rend(); ++it) {
        std::cout << it->first << ": " << it->second << "\n";
    }

    // 方式 4：只遍历 key 或 value
    std::cout << "\nKeys only:\n";
    for (const auto& [key, _] : scores) {  // _ 表示忽略 value
        std::cout << key << "\n";
    }

    return 0;
}

Bucket 遍历（调试用）

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> scores = {
        {"Alice", 95},
        {"Bob", 87},
        {"Charlie", 92}
    };

    std::cout << "Bucket info:\n";
    std::cout << "Bucket count: " << scores.bucket_count() << "\n";
    std::cout << "Load factor: " << scores.load_factor() << "\n";
    std::cout << "Max load factor: " << scores.max_load_factor() << "\n";

    // 遍历每个 bucket
    std::cout << "\nElements per bucket:\n";
    for (std::size_t i = 0; i < scores.bucket_count(); ++i) {
        std::size_t bucket_size = scores.bucket_size(i);
        if (bucket_size > 0) {
            std::cout << "Bucket " << i << " has " << bucket_size << " element(s): ";
            for (auto it = scores.begin(i); it != scores.end(i); ++it) {
                std::cout << it->first << " ";
            }
            std::cout << "\n";
        }
    }

    // 找到特定 key 所在的 bucket
    auto key_bucket = scores.bucket("Bob");
    std::cout << "\nBob is in bucket " << key_bucket << "\n";

    return 0;
}

15.5 自定义哈希函数

为什么需要自定义哈希

#include <unordered_map>
#include <string>
#include <iostream>

// 默认哈希对标准类型有效
std::unordered_map<std::string, int> string_map;
std::unordered_map<int, int> int_map;

// 但对于自定义类型，需要提供哈希函数
struct Point {
    int x, y;
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 自定义哈希
struct PointHash {
    std::size_t operator()(const Point& p) const {
        // 组合 x 和 y 的哈希
        return std::hash<int>{}(p.x) ^ (std::hash<int>{}(p.y) << 1);
    }
};

int main() {
    std::unordered_map<Point, std::string, PointHash> point_map;
    point_map[{1, 2}] = "point A";
    point_map[{3, 4}] = "point B";

    std::cout << point_map[{1, 2}] << std::endl;  // point A

    return 0;
}

自定义哈希的几种方式

#include <unordered_map>
#include <string>
#include <iostream>
#include <functional>

// 方式 1：struct 仿函数
struct CaseInsensitiveHash {
    std::size_t operator()(const std::string& s) const {
        std::string lower;
        lower.reserve(s.size());
        for (char c : s) {
            lower += std::tolower(c);
        }
        return std::hash<std::string>{}(lower);
    }
};

struct CaseInsensitiveEq {
    bool operator()(const std::string& a, const std::string& b) const {
        return std::equal(a.begin(), a.end(), b.begin(), b.end(),
            [](char c1, char c2) {
                return std::tolower(c1) == std::tolower(c2);
            });
    }
};

int main() {
    std::unordered_map<std::string, int, CaseInsensitiveHash, CaseInsensitiveEq> ci_map;
    ci_map["Apple"] = 1;
    ci_map["APPLE"] = 2;  // 覆盖 Apple
    ci_map["apple"] = 3;  // 覆盖 APPLE
    std::cout << ci_map["apple"] << std::endl;  // 3

    return 0;
}

#include <unordered_map>
#include <string>

int main() {
    // 方式 2：Lambda（C++14）
    auto custom_hash = [](const std::string& s) -> std::size_t {
        return std::hash<std::string>{}(s);
    };

    std::unordered_map<std::string, int, decltype(custom_hash)> map1(
        10,  // 初始 bucket 数
        custom_hash);

    // 方式 3：组合哈希
    struct Person {
        std::string name;
        int age;
        bool operator==(const Person& other) const {
            return name == other.name && age == other.age;
        }
    };

    struct PersonHash {
        std::size_t operator()(const Person& p) const {
            auto h1 = std::hash<std::string>{}(p.name);
            auto h2 = std::hash<int>{}(p.age);
            return h1 ^ (h2 << 1);
        }
    };

    std::unordered_map<Person, std::string, PersonHash> person_map;
    person_map[{"Alice", 25}] = "Engineer";

    return 0;
}

处理哈希冲突

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    // 负载因子影响哈希表性能
    std::unordered_map<std::string, int> map;

    std::cout << "Default load factor: " << map.max_load_factor() << "\n";

    // 降低负载因子，减少冲突，但浪费内存
    map.reserve(1000);           // 预分配
    map.max_load_factor(0.5);   // 设置最大负载因子

    // rehash - 重新分配 bucket
    map.rehash(100);  // 确保至少有 100 个 bucket

    // 当负载因子过高时，会自动 rehash
    // 但我们可以手动控制

    std::cout << "Bucket count: " << map.bucket_count() << "\n";

    return 0;
}

15.6 嵌套和复杂结构

嵌套 unordered_map

#include <unordered_map>
#include <string>
#include <vector>
#include <iostream>

int main() {
    // 嵌套：按年份分组的学生分数
    std::unordered_map<int, std::unordered_map<std::string, int>> year_grades;

    year_grades[2024]["Alice"] = 95;
    year_grades[2024]["Bob"] = 87;
    year_grades[2023]["Charlie"] = 92;

    // 访问
    std::cout << "Alice 2024: " << year_grades[2024]["Alice"] << "\n";

    // 遍历
    for (const auto& [year, students] : year_grades) {
        std::cout << "Year " << year << ":\n";
        for (const auto& [name, score] : students) {
            std::cout << "  " << name << ": " << score << "\n";
        }
    }

    return 0;
}

unordered_map 作为值

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    // 单词计数（类似 Python 的 defaultdict）
    std::vector<std::string> words = {"apple", "banana", "apple", "cherry", "banana", "apple"};
    std::unordered_map<std::string, int> word_count;

    for (const auto& word : words) {
        ++word_count[word];  // 自动创建并递增
    }

    for (const auto& [word, count] : word_count) {
        std::cout << word << ": " << count << "\n";
    }

    // 分组（类似 defaultdict 的 setdefault）
    std::vector<std::pair<std::string, int>> data = {
        {"apple", 1}, {"banana", 2}, {"apple", 3}
    };
    std::unordered_map<std::string, std::vector<int>> grouped;
    for (const auto& [name, val] : data) {
        grouped[name].push_back(val);  // 自动创建空 vector
    }
    // grouped = {"apple": [1, 3], "banana": [2]}

    return 0;
}

15.7 常见陷阱

默认值陷阱

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> ages = {{"Alice", 25}};

    // ❌ 陷阱：operator[] 会插入默认值
    int charlie_age = ages["Charlie"];  // 插入 ages["Charlie"] = 0
    std::cout << "Size: " << ages.size() << std::endl;  // 2！

    // ✅ 正确做法：用 find
    if (auto it = ages.find("Charlie"); it != ages.end()) {
        std::cout << it->second << "\n";
    } else {
        std::cout << "Not found\n";
    }

    // ✅ 或者用 at()
    try {
        int alice_age = ages.at("Alice");
        std::cout << "Alice: " << alice_age << "\n";
    } catch (...) {
        std::cout << "Not found\n";
    }

    return 0;
}

迭代器失效规则

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    std::unordered_map<std::string, int> ages = {
        {"Alice", 25},
        {"Bob", 30}
    };

    auto it = ages.find("Alice");

    // ✅ 插入不会使现有迭代器失效（通常）
    ages["Charlie"] = 28;  // 安全

    // ✅ 删除会使被删除元素的迭代器失效
    ages.erase("Alice");
    // it 现在是无效迭代器！
    // std::cout << it->second << "\n";  // ❌ 未定义行为！

    return 0;
}

线程安全

#include <unordered_map>
#include <string>
#include <iostream>
#include <thread>
#include <mutex>

int main() {
    // std::unordered_map 不是线程安全的！
    std::unordered_map<std::string, int> shared_data;

    // ❌ 危险：并发写入
    // std::thread t1([&]() { shared_data["a"] = 1; });
    // std::thread t2([&]() { shared_data["b"] = 2; });  // 数据竞争！

    // ✅ 正确做法：使用互斥锁
    std::mutex mtx;
    std::unordered_map<std::string, int> safe_data;

    auto increment = [&safe_data, &mtx](const std::string& key) {
        std::lock_guard<std::mutex> lock(mtx);
        ++safe_data[key];
    };

    // 或者用 std::shared_mutex（C++17）实现读写锁

    // ✅ 只读操作可以并发
    // 多个线程可以同时读取（如果没有写入）

    return 0;
}

15.8 完整示例：单词频率统计

#include <unordered_map>
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cctype>

// 文本分析器
class TextAnalyzer {
private:
    std::unordered_map<std::string, int> word_counts_;
    std::unordered_map<char, int> char_counts_;
    std::string text_;

public:
    explicit TextAnalyzer(const std::string& text) : text_(text) {}

    void analyze() {
        std::string word;
        std::istringstream stream(text_);

        while (stream >> word) {
            // 清理单词（转小写，移除标点）
            std::string cleaned;
            for (char c : word) {
                if (std::isalpha(c)) {
                    cleaned += std::tolower(c);
                }
            }

            if (!cleaned.empty()) {
                ++word_counts_[cleaned];
            }

            // 统计字符
            for (char c : cleaned) {
                ++char_counts_[c];
            }
        }
    }

    // 获取最常见的词
    std::vector<std::pair<std::string, int>> top_words(int n) const {
        std::vector<std::pair<std::string, int>> sorted(word_counts_.begin(),
                                                        word_counts_.end());
        std::sort(sorted.begin(), sorted.end(),
            [](const auto& a, const auto& b) {
                return a.second > b.second;
            });

        if (sorted.size() > static_cast<std::size_t>(n)) {
            sorted.resize(n);
        }
        return sorted;
    }

    // 获取字母频率
    double letter_frequency(char letter) const {
        int total = 0;
        for (const auto& [ch, count] : char_counts_) {
            if (std::isalpha(ch)) {
                total += count;
            }
        }
        if (total == 0) return 0.0;
        return static_cast<double>(char_counts_[letter]) / total;
    }

    void print_report() const {
        std::cout << "=== Word Frequency Report ===\n\n";

        std::cout << "Top 10 words:\n";
        auto top = top_words(10);
        for (const auto& [word, count] : top) {
            std::cout << "  " << word << ": " << count << "\n";
        }

        std::cout << "\nTotal unique words: " << word_counts_.size() << "\n";

        std::cout << "\nLetter frequencies:\n";
        for (char c = 'a'; c <= 'z'; ++c) {
            double freq = letter_frequency(c);
            if (freq > 0) {
                std::cout << "  " << c << ": " << std::fixed
                          << std::setprecision(2) << (freq * 100) << "%\n";
            }
        }
    }
};

int main() {
    std::string text = R"(
        The quick brown fox jumps over the lazy dog.
        The dog was not amused by the fox's antics.
        A quick brown dog chased the fox away.
    )";

    TextAnalyzer analyzer(text);
    analyzer.analyze();
    analyzer.print_report();

    return 0;
}

章节总结

操作	说明
unordered_map<K,V> m	默认构造
m[key] = value	添加/修改（会插入默认值）
m.insert({k, v})	显式插入
m.emplace(k, v)	原位构造
m.find(k)	查找，返回迭代器
m.contains(k)	C++20，查找是否存在
m.at(k)	安全访问，不存在抛异常
m.value_or(k, default)	C++20，安全访问默认值
m.erase(k)	按 key 删除
m.clear()	清空所有
m.reserve(n)	预分配空间
m.load_factor()	负载因子

选择建议：

• 需要 O(1) 查找 → unordered_map
• 需要有序遍历 → map
• 自定义 key 类型 → 提供 operator== 和哈希函数

---

下章预告：ch16 学习 std::tuple 和 std::optional，多返回值和可选值的解决方案。