第11章：关联容器（Associative Containers）

一、导读

1.1 本章学习目标

第11章介绍C++标准库的关联容器。本章核心目标：

掌握map和set：有序关联容器
理解unordered_map和unordered_set：基于哈希表的无序容器
学会关联容器的操作：插入、查找、删除
理解有序和无序容器的性能差异
掌握自定义比较函数

1.2 为什么本章如此重要

关联容器提供了高效的键值查找能力。map基于红黑树实现，提供O(log n)的查找；unordered_map基于哈希表，提供O(1)的平均查找。选择合适的关联容器对程序性能至关重要。

1.3 核心问题引导

map和unordered_map有什么区别？什么时候用哪个？

set和map的关系是什么？

如何自定义map的排序规则？

关联容器的迭代器遍历顺序是什么？

二、核心概念详解

11.1 map和set

cpp

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

int main() {
    // map：键值对，按键排序
    std::map<std::string, int> ages;
    ages["Alice"] = 20;
    ages["Bob"] = 21;
    ages.insert({"Charlie", 19});
    
    // 遍历（按键排序）
    for (const auto &[name, age] : ages) {
        std::cout << name << ": " << age << std::endl;
    }
    
    // 查找
    auto it = ages.find("Bob");
    if (it != ages.end()) {
        std::cout << "Bob's age: " << it->second << std::endl;
    }
    
    // count
    if (ages.count("Alice")) {
        std::cout << "Alice is in the map" << std::endl;
    }
    
    // set：集合，元素唯一且有序
    std::set<int> numbers = {5, 2, 8, 1, 9, 3};
    numbers.insert(4);
    numbers.insert(2);  // 重复元素不会插入
    
    std::cout << "Set: ";
    for (int n : numbers) std::cout << n << " ";
    std::cout << std::endl;
    
    // lower_bound和upper_bound
    auto lb = numbers.lower_bound(5);
    auto ub = numbers.upper_bound(5);
    std::cout << "lower_bound(5): " << *lb << std::endl;
    if (ub != numbers.end())
        std::cout << "upper_bound(5): " << *ub << std::endl;
    
    return 0;
}

11.2 unordered_map和unordered_set

cpp

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

int main() {
    // unordered_map：基于哈希表，O(1)平均查找
    std::unordered_map<std::string, std::vector<int>> scores;
    
    scores["Alice"].push_back(95);
    scores["Alice"].push_back(88);
    scores["Bob"].push_back(82);
    scores["Bob"].push_back(90);
    
    for (const auto &[name, s] : scores) {
        std::cout << name << ": ";
        int sum = 0;
        for (int score : s) {
            sum += score;
            std::cout << score << " ";
        }
        std::cout << "(avg: " << sum / s.size() << ")" << std::endl;
    }
    
    // unordered_set
    std::unordered_set<std::string> words = {"hello", "world", "cpp"};
    words.insert("hello");  // 重复不插入
    
    if (words.count("world")) {
        std::cout << "world is in the set" << std::endl;
    }
    
    // 负载因子
    std::cout << "Load factor: " << scores.load_factor() << std::endl;
    std::cout << "Bucket count: " << scores.bucket_count() << std::endl;
    
    // 预分配
    scores.reserve(1000);
    
    return 0;
}

11.3 自定义比较

cpp

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

struct CaseInsensitiveCompare {
    bool operator()(const std::string &a, const std::string &b) const {
        auto it1 = a.begin(), it2 = b.begin();
        while (it1 != a.end() && it2 != b.end()) {
            char c1 = std::tolower(*it1);
            char c2 = std::tolower(*it2);
            if (c1 < c2) return true;
            if (c1 > c2) return false;
            ++it1; ++it2;
        }
        return a.size() < b.size();
    }
};

int main() {
    std::map<std::string, int, CaseInsensitiveCompare> m;
    m["Hello"] = 1;
    m["HELLO"] = 2;  // 覆盖，因为不区分大小写
    m["World"] = 3;
    
    for (const auto &[key, val] : m) {
        std::cout << key << ": " << val << std::endl;
    }
    
    return 0;
}

三、实战案例

3.1 词频统计

cpp

#include <iostream>
#include <map>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>

int main() {
    std::string text = "the quick brown fox jumps over the lazy dog the fox";
    
    // 使用map统计词频
    std::map<std::string, int> word_count;
    std::istringstream iss(text);
    std::string word;
    while (iss >> word) {
        word_count[word]++;
    }
    
    // 转换为vector排序
    std::vector<std::pair<std::string, int>> sorted_words(
        word_count.begin(), word_count.end());
    
    std::sort(sorted_words.begin(), sorted_words.end(),
              [](const auto &a, const auto &b) {
                  return a.second > b.second;
              });
    
    for (const auto &[w, count] : sorted_words) {
        std::cout << w << ": " << count << std::endl;
    }
    
    return 0;
}

四、本章小结

第11章介绍了关联容器：map/set（有序，O(log n)查找）和unordered_map/unordered_set（无序，O(1)平均查找）。map基于红黑树，unordered_map基于哈希表。

五、思考与练习

思考题

map的底层实现是什么？为什么查找是O(log n)？

unordered_map如何处理哈希冲突？

什么时候应该用map而不是unordered_map？

如何自定义unordered_map的哈希函数？

编程练习

使用map实现一个简单的电话簿。

使用unordered_set实现数组去重。

实现一个LRU缓存，使用list和unordered_map。