C++ Primer 第11章：关联容器

---

11.1 使用关联容器

11.1.1 关联容器概述

关联容器：元素按键（key）存储和访问，而非位置

┌──────────────────┬──────────────┬──────────────────────────────────┐
│ 容器类型          │ 底层结构      │ 特点                              │
├──────────────────┼──────────────┼──────────────────────────────────┤
│ map              │ 红黑树        │ 键值对，键唯一，按键有序            │
│ set              │ 红黑树        │ 只有键，键唯一，有序               │
│ multimap         │ 红黑树        │ 键值对，键可重复，有序              │
│ multiset         │ 红黑树        │ 只有键，键可重复，有序              │
│ unordered_map    │ 哈希表        │ 键值对，键唯一，无序，O(1)查找     │
│ unordered_set    │ 哈希表        │ 只有键，键唯一，无序，O(1)查找     │
│ unordered_multimap│ 哈希表       │ 键值对，键可重复，无序             │
│ unordered_multiset│ 哈希表       │ 只有键，键可重复，无序             │
└──────────────────┴──────────────┴──────────────────────────────────┘

头文件：
  map, multimap         → <map>
  set, multiset         → <set>
  unordered_map, ...    → <unordered_map>
  unordered_set, ...    → <unordered_set>

---

11.1.2 map 和 set 的基本使用

// map_set_basic.cpp -- map和set基本使用
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

int main()
{
    using namespace std;

    // ===== map：统计单词出现次数 =====
    map<string, int> wordCount;
    vector<string> words = {"the", "quick", "red", "fox",
                            "jumps", "over", "the", "slow",
                            "red", "turtle", "the"};

    for (const auto& w : words)
        ++wordCount[w];   // 如果键不存在，自动创建并初始化为0

    cout << "单词频率：" << endl;
    for (const auto& [word, count] : wordCount)   // C++17结构化绑定
        cout << "  " << word << ": " << count << endl;

    // ===== set：存储不重复的单词 =====
    set<string> uniqueWords(words.begin(), words.end());
    cout << "\n不重复单词（" << uniqueWords.size() << "个）：";
    for (const auto& w : uniqueWords)
        cout << w << " ";
    cout << endl;

    // ===== 关联容器的有序性 =====
    // map 和 set 按键的字典序自动排序
    map<int, string> m = {{3, "three"}, {1, "one"}, {4, "four"}, {2, "two"}};
    cout << "\nmap按键排序：" << endl;
    for (const auto& [k, v] : m)
        cout << "  " << k << " → " << v << endl;

    return 0;
}

---

11.2 关联容器概述

11.2.1 定义关联容器

// define_containers.cpp -- 定义关联容器
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

int main()
{
    using namespace std;

    // ===== map 的初始化 =====
    map<string, int> m1;                    // 空map
    map<string, int> m2 = {               // 列表初始化
        {"Alice", 90},
        {"Bob",   85},
        {"Carol", 92}
    };
    map<string, int> m3(m2);              // 拷贝构造

    // ===== set 的初始化 =====
    set<int> s1;                           // 空set
    set<int> s2 = {3, 1, 4, 1, 5, 9, 2}; // 列表初始化（自动去重排序）
    set<int> s3(s2.begin(), s2.end());    // 范围构造

    cout << "s2（自动去重排序）：";
    for (int x : s2) cout << x << " ";
    cout << endl;   // 1 2 3 4 5 9

    // ===== 自定义比较函数 =====
    // 默认使用 < 运算符，可以自定义
    auto cmp = [](const string& a, const string& b) {
        return a.size() < b.size();   // 按字符串长度排序
    };

    // 注意：自定义比较必须是严格弱序
    map<string, int, decltype(cmp)> byLength(cmp);
    byLength["hello"] = 1;
    byLength["hi"]    = 2;
    byLength["hey"]   = 3;
    byLength["world"] = 4;

    cout << "\n按长度排序的map：" << endl;
    for (const auto& [k, v] : byLength)
        cout << "  " << k << "(" << k.size() << "): " << v << endl;

    return 0;
}

---

11.2.2 pair 类型

// pair_demo.cpp -- pair类型
#include <iostream>
#include <map>
#include <string>
#include <utility>   // pair 定义在这里

int main()
{
    using namespace std;

    // ===== pair 的创建 =====
    pair<string, int> p1("Alice", 90);
    pair<string, int> p2 = {"Bob", 85};
    auto p3 = make_pair("Carol", 92);   // 自动推断类型

    cout << "p1: " << p1.first << " = " << p1.second << endl;
    cout << "p2: " << p2.first << " = " << p2.second << endl;
    cout << "p3: " << p3.first << " = " << p3.second << endl;

    // ===== pair 的比较 =====
    // 先比较 first，first 相等再比较 second
    pair<int, int> a = {1, 2};
    pair<int, int> b = {1, 3};
    pair<int, int> c = {2, 1};
    cout << boolalpha;
    cout << "a < b: " << (a < b) << endl;   // true（first相等，比second）
    cout << "a < c: " << (a < c) << endl;   // true（first不同，比first）

    // ===== map 的元素类型是 pair =====
    map<string, int> scores = {{"Alice", 90}, {"Bob", 85}};

    // 遍历时，每个元素是 pair<const string, int>
    for (const pair<const string, int>& p : scores)
        cout << p.first << ": " << p.second << endl;

    // 使用 auto 更简洁
    for (const auto& [name, score] : scores)
        cout << name << ": " << score << endl;

    // ===== 函数返回 pair =====
    auto minMax = [](const vector<int>& v) -> pair<int, int> {
        return {*min_element(v.begin(), v.end()),
                *max_element(v.begin(), v.end())};
    };

    vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6};
    auto [minVal, maxVal] = minMax(nums);
    cout << "min=" << minVal << " max=" << maxVal << endl;

    return 0;
}

---

11.3 关联容器操作

11.3.1 关联容器的类型别名

// container_types.cpp -- 关联容器类型别名
#include <iostream>
#include <map>
#include <set>
#include <string>

int main()
{
    using namespace std;

    // map 的类型别名
    map<string, int> m;

    // key_type：键类型
    map<string, int>::key_type k = "hello";

    // mapped_type：值类型（只有map有）
    map<string, int>::mapped_type v = 42;

    // value_type：元素类型（pair<const key_type, mapped_type>）
    map<string, int>::value_type elem = {"world", 100};

    cout << "key: " << k << endl;
    cout << "value: " << v << endl;
    cout << "elem: " << elem.first << "=" << elem.second << endl;

    // set 的类型别名
    set<int> s;
    // set 的 key_type 和 value_type 相同
    set<int>::key_type   sk = 42;
    set<int>::value_type sv = 42;

    return 0;
}

---

11.3.2 添加元素

// add_elements.cpp -- 关联容器添加元素
#include <iostream>
#include <map>
#include <set>
#include <string>

int main()
{
    using namespace std;

    // ===== set 的插入 =====
    set<int> s;

    // insert 单个元素，返回 pair<iterator, bool>
    auto [it1, ok1] = s.insert(42);
    auto [it2, ok2] = s.insert(42);   // 重复插入

    cout << boolalpha;
    cout << "第一次插入42：" << ok1 << endl;   // true
    cout << "第二次插入42：" << ok2 << endl;   // false（已存在）

    // 插入范围
    s.insert({1, 2, 3, 4, 5});
    cout << "set：";
    for (int x : s) cout << x << " ";
    cout << endl;

    // ===== map 的插入 =====
    map<string, int> m;

    // 方式1：insert + pair
    m.insert({"Alice", 90});
    m.insert(make_pair("Bob", 85));
    m.insert(pair<string, int>("Carol", 92));

    // 方式2：下标运算符（如果键不存在，创建并值初始化）
    m["David"] = 88;
    m["Eve"];   // 创建键"Eve"，值初始化为0

    // 方式3：emplace（直接构造，更高效）
    m.emplace("Frank", 95);

    cout << "\nmap：" << endl;
    for (const auto& [k, v] : m)
        cout << "  " << k << ": " << v << endl;

    // ===== insert 的返回值 =====
    auto result = m.insert({"Alice", 100});   // Alice已存在
    cout << "\n插入Alice（已存在）：" << result.second << endl;   // false
    cout << "Alice的值：" << result.first->second << endl;        // 90（未改变）

    return 0;
}

---

11.3.3 删除元素

// delete_elements.cpp -- 关联容器删除元素
#include <iostream>
#include <map>
#include <set>
#include <string>

int main()
{
    using namespace std;

    map<string, int> m = {
        {"Alice", 90}, {"Bob", 85}, {"Carol", 92},
        {"David", 88}, {"Eve", 75}
    };

    // ===== erase(key)：按键删除，返回删除的元素数量 =====
    size_t n = m.erase("Bob");
    cout << "删除Bob：" << n << " 个" << endl;   // 1

    n = m.erase("Unknown");
    cout << "删除Unknown：" << n << " 个" << endl;   // 0

    // ===== erase(iterator)：按迭代器删除 =====
    auto it = m.find("Carol");
    if (it != m.end())
        m.erase(it);

    // ===== erase(first, last)：删除范围 =====
    // 删除所有键在 [Alice, David) 之间的元素
    auto first = m.lower_bound("Alice");
    auto last  = m.lower_bound("David");
    m.erase(first, last);

    cout << "剩余元素：" << endl;
    for (const auto& [k, v] : m)
        cout << "  " << k << ": " << v << endl;

    // ===== set 的删除 =====
    set<int> s = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    s.erase(5);   // 删除值为5的元素
    s.erase(s.begin());   // 删除第一个元素

    cout << "\nset：";
    for (int x : s) cout << x << " ";
    cout << endl;

    return 0;
}

---

11.3.4 map 的下标操作

// map_subscript.cpp -- map的下标操作
#include <iostream>
#include <map>
#include <string>

int main()
{
    using namespace std;

    map<string, int> m;

    // ===== 下标运算符 [] =====
    // 如果键不存在，自动创建并值初始化
    m["Alice"] = 90;   // 创建键"Alice"，赋值90
    m["Bob"];          // 创建键"Bob"，值初始化为0

    cout << "m[\"Alice\"] = " << m["Alice"] << endl;   // 90
    cout << "m[\"Bob\"]   = " << m["Bob"]   << endl;   // 0

    // ⚠️ 下标操作会插入元素！
    // 对 const map 不能使用下标
    // const map<string, int> cm = m;
    // cm["Alice"];   // ❌ 错误！

    // ===== at() 方法（C++11）=====
    // 如果键不存在，抛出 out_of_range 异常
    try
    {
        cout << "m.at(\"Alice\") = " << m.at("Alice") << endl;
        cout << "m.at(\"Unknown\") = " << m.at("Unknown") << endl;
    }
    catch (const out_of_range& e)
    {
        cout << "键不存在：" << e.what() << endl;
    }

    // ===== 下标 vs at() vs find() =====
    // 下标：不存在时创建，适合写操作
    // at()：不存在时抛异常，适合读操作（需要键存在）
    // find()：不存在时返回end()，适合检查键是否存在

    // 安全读取的推荐方式
    auto it = m.find("Carol");
    if (it != m.end())
        cout << "Carol: " << it->second << endl;
    else
        cout << "Carol不存在" << endl;

    return 0;
}

---

11.3.5 访问元素

// access_elements.cpp -- 关联容器访问元素
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <multimap>

int main()
{
    using namespace std;

    map<string, int> m = {
        {"Alice", 90}, {"Bob", 85}, {"Carol", 92}
    };

    // ===== find：查找键，返回迭代器 =====
    auto it = m.find("Bob");
    if (it != m.end())
        cout << "找到Bob：" << it->second << endl;

    // ===== count：统计键的出现次数 =====
    // 对于 map/set，count 只返回 0 或 1
    cout << "Alice存在：" << boolalpha << (m.count("Alice") > 0) << endl;
    cout << "David存在：" << (m.count("David") > 0) << endl;

    // ===== contains（C++20）=====
    // cout << m.contains("Alice") << endl;

    // ===== lower_bound / upper_bound / equal_range =====
    // 这些函数对有序关联容器特别有用

    map<int, string> scores = {
        {60, "D"}, {70, "C"}, {80, "B"}, {90, "A"}
    };

    // lower_bound(k)：第一个键 >= k 的迭代器
    auto lb = scores.lower_bound(75);
    cout << "\nlower_bound(75)：" << lb->first << "→" << lb->second << endl;

    // upper_bound(k)：第一个键 > k 的迭代器
    auto ub = scores.upper_bound(75);
    cout << "upper_bound(75)：" << ub->first << "→" << ub->second << endl;

    // equal_range(k)：返回 [lower_bound, upper_bound) 的 pair
    auto range = scores.equal_range(80);
    cout << "equal_range(80)：";
    for (auto it = range.first; it != range.second; ++it)
        cout << it->first << "→" << it->second << " ";
    cout << endl;

    // ===== multimap 中查找所有相同键的元素 =====
    multimap<string, string> authors = {
        {"Barth", "Sot-Weed Factor"},
        {"Barth", "Lost in the Funhouse"},
        {"Alain", "Tipping Point"},
        {"Barth", "Chimera"}
    };

    string author = "Barth";
    cout << "\n" << author << "的作品：" << endl;

    // 方式1：equal_range
    auto [first, last] = authors.equal_range(author);
    for (auto it = first; it != last; ++it)
        cout << "  " << it->second << endl;

    // 方式2：lower_bound + upper_bound
    auto beg = authors.lower_bound(author);
    auto end = authors.upper_bound(author);
    for (auto it = beg; it != end; ++it)
        cout << "  " << it->second << endl;

    return 0;
}

---

11.4 无序容器

11.4.1 unordered_map 和 unordered_set

// unordered_containers.cpp -- 无序容器
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <vector>

int main()
{
    using namespace std;

    // ===== unordered_map：哈希表实现，O(1)平均查找 =====
    unordered_map<string, int> umap;

    // 操作与 map 基本相同
    umap["Alice"] = 90;
    umap["Bob"]   = 85;
    umap.insert({"Carol", 92});
    umap.emplace("David", 88);

    cout << "unordered_map（无序）：" << endl;
    for (const auto& [k, v] : umap)
        cout << "  " << k << ": " << v << endl;

    // ===== unordered_set =====
    unordered_set<int> uset = {3, 1, 4, 1, 5, 9, 2, 6};
    cout << "\nunordered_set（无序，去重）：";
    for (int x : uset) cout << x << " ";
    cout << endl;

    // ===== 性能对比 =====
    // map：O(log n) 查找，有序
    // unordered_map：O(1) 平均查找，无序

    // 大量数据时，unordered_map 通常更快
    unordered_map<int, int> fastMap;
    for (int i = 0; i < 1000000; i++)
        fastMap[i] = i * i;

    // O(1) 查找
    auto it = fastMap.find(999999);
    if (it != fastMap.end())
        cout << "\n999999^2 = " << it->second << endl;

    // ===== 桶操作 =====
    cout << "\n桶信息：" << endl;
    cout << "桶数量：" << umap.bucket_count() << endl;
    cout << "负载因子：" << umap.load_factor() << endl;
    cout << "最大负载因子：" << umap.max_load_factor() << endl;

    return 0;
}

---

11.4.2 自定义哈希函数

// custom_hash.cpp -- 自定义哈希函数
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <string>

// 自定义类型
struct Point
{
    int x, y;
    bool operator==(const Point& other) const
    {
        return x == other.x && y == other.y;
    }
};

// 自定义哈希函数
struct PointHash
{
    size_t operator()(const Point& p) const
    {
        // 组合两个哈希值
        size_t h1 = hash<int>{}(p.x);
        size_t h2 = hash<int>{}(p.y);
        return h1 ^ (h2 << 1);   // 简单的哈希组合
    }
};

// 使用 lambda 作为哈希函数
auto strHash = [](const string& s) -> size_t {
    size_t h = 0;
    for (char c : s)
        h = h * 31 + c;
    return h;
};

auto strEqual = [](const string& a, const string& b) {
    return a == b;
};

int main()
{
    using namespace std;

    // 使用自定义哈希的 unordered_set
    unordered_set<Point, PointHash> points;
    points.insert({1, 2});
    points.insert({3, 4});
    points.insert({1, 2});   // 重复，不插入

    cout << "点集合大小：" << points.size() << endl;   // 2

    // 使用 lambda 哈希
    unordered_map<string, int,
                  decltype(strHash),
                  decltype(strEqual)> customMap(0, strHash, strEqual);

    customMap["hello"] = 1;
    customMap["world"] = 2;

    cout << "customMap[\"hello\"] = " << customMap["hello"] << endl;

    return 0;
}

---

11.5 综合示例：电话簿系统

// phonebook.cpp -- 综合示例：电话簿系统
#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <stdexcept>

class PhoneBook
{
private:
    // 姓名 → 电话号码集合（一个人可以有多个号码）
    map<string, set<string>> contacts_;

    // 电话号码 → 姓名（反向查找）
    unordered_map<string, string> phoneToName_;

    // 验证电话号码格式（简化）
    bool isValidPhone(const string& phone) const
    {
        if (phone.empty()) return false;
        for (char c : phone)
            if (!isdigit(c) && c != '-' && c != '+' && c != ' ')
                return false;
        return true;
    }

public:
    // 添加联系人
    bool addContact(const string& name, const string& phone)
    {
        if (name.empty())
            throw invalid_argument("姓名不能为空");
        if (!isValidPhone(phone))
            throw invalid_argument("无效的电话号码：" + phone);

        // 检查号码是否已被其他人使用
        auto it = phoneToName_.find(phone);
        if (it != phoneToName_.end() && it->second != name)
        {
            cout << "警告：号码 " << phone
                 << " 已被 " << it->second << " 使用" << endl;
            return false;
        }

        contacts_[name].insert(phone);
        phoneToName_[phone] = name;
        return true;
    }

    // 删除联系人
    bool removeContact(const string& name)
    {
        auto it = contacts_.find(name);
        if (it == contacts_.end()) return false;

        // 删除反向索引
        for (const auto& phone : it->second)
            phoneToName_.erase(phone);

        contacts_.erase(it);
        return true;
    }

    // 删除特定号码
    bool removePhone(const string& name, const string& phone)
    {
        auto it = contacts_.find(name);
        if (it == contacts_.end()) return false;

        it->second.erase(phone);
        phoneToName_.erase(phone);

        // 如果没有号码了，删除联系人
        if (it->second.empty())
            contacts_.erase(it);

        return true;
    }

    // 按姓名查找
    const set<string>* findByName(const string& name) const
    {
        auto it = contacts_.find(name);
        if (it == contacts_.end()) return nullptr;
        return &it->second;
    }

    // 按号码查找
    string findByPhone(const string& phone) const
    {
        auto it = phoneToName_.find(phone);
        if (it == phoneToName_.end()) return "";
        return it->second;
    }

    // 搜索（前缀匹配）
    vector<string> search(const string& prefix) const
    {
        vector<string> results;
        // lower_bound 找到第一个 >= prefix 的键
        auto it = contacts_.lower_bound(prefix);
        while (it != contacts_.end() &&
               it->first.substr(0, prefix.size()) == prefix)
        {
            results.push_back(it->first);
            ++it;
        }
        return results;
    }

    // 显示所有联系人
    void display() const
    {
        if (contacts_.empty())
        {
            cout << "电话簿为空" << endl;
            return;
        }

        cout << "\n" << string(50, '=') << endl;
        cout << left << setw(15) << "姓名"
             << "电话号码" << endl;
        cout << string(50, '-') << endl;

        for (const auto& [name, phones] : contacts_)
        {
            cout << left << setw(15) << name;
            bool first = true;
            for (const auto& phone : phones)
            {
                if (!first) cout << string(15, ' ');
                cout << phone << endl;
                first = false;
            }
        }
        cout << string(50, '=') << endl;
        cout << "共 " << contacts_.size() << " 个联系人" << endl;
    }

    // 统计信息
    void statistics() const
    {
        int totalPhones = 0;
        for (const auto& [name, phones] : contacts_)
            totalPhones += phones.size();

        cout << "\n===== 统计信息 =====" << endl;
        cout << "联系人数：" << contacts_.size() << endl;
        cout << "电话号码总数：" << totalPhones << endl;
        if (!contacts_.empty())
            cout << "平均每人号码数：" << (double)totalPhones / contacts_.size() << endl;
    }
};

int main()
{
    using namespace std;

    PhoneBook pb;

    // 添加联系人
    try
    {
        pb.addContact("张三", "138-1234-5678");
        pb.addContact("张三", "010-12345678");   // 同一人多个号码
        pb.addContact("李四", "139-8765-4321");
        pb.addContact("王五", "021-87654321");
        pb.addContact("张伟", "186-5555-6666");
        pb.addContact("张明", "187-7777-8888");
    }
    catch (const exception& e)
    {
        cerr << "错误：" << e.what() << endl;
    }

    // 显示所有联系人
    pb.display();

    // 按姓名查找
    cout << "\n===== 查找张三 =====" << endl;
    if (auto phones = pb.findByName("张三"))
    {
        cout << "张三的电话：";
        for (const auto& p : *phones) cout << p << " ";
        cout << endl;
    }

    // 按号码查找
    cout << "\n===== 按号码查找 =====" << endl;
    string name = pb.findByPhone("139-8765-4321");
    cout << "139-8765-4321 → " << (name.empty() ? "未找到" : name) << endl;

    // 前缀搜索
    cout << "\n===== 搜索\"张\" =====" << endl;
    auto results = pb.search("张");
    for (const auto& r : results)
        cout << "  " << r << endl;

    // 删除号码
    pb.removePhone("张三", "010-12345678");
    cout << "\n删除张三的010号码后：";
    if (auto phones = pb.findByName("张三"))
        for (const auto& p : *phones) cout << p << " ";
    cout << endl;

    // 统计
    pb.statistics();

    return 0;
}

---

📝 第11章知识点总结

知识点	核心要点
关联容器类型	map/set（有序唯一）、multimap/multiset（有序可重复）、unordered_*（无序哈希）
map vs set	map存键值对，set只存键；都按键有序，键唯一
pair	first/second 访问，make_pair 创建，map的元素类型是 pair<const K, V>
insert 返回值	map/set的insert返回 pair<iterator, bool>，bool表示是否插入成功
下标 vs at()	[] 不存在时创建（不能用于const map），at() 不存在时抛异常
find vs count	find 返回迭代器，count 返回数量（map/set只返回0或1）
lower_bound	第一个键 >= k 的迭代器
upper_bound	第一个键 > k 的迭代器
equal_range	返回 [lower_bound, upper_bound) 的 pair，用于multimap查找所有相同键
multimap 遍历	用 equal_range 或 lower_bound+upper_bound 遍历相同键的所有元素
unordered_map	哈希表，O(1)平均查找，无序，操作接口与map基本相同
自定义哈希	提供哈希函数对象和相等比较函数，用于自定义类型的无序容器
有序容器排序	默认用 < 运算符，可以提供自定义比较函数（严格弱序）
map 的键是 const	value_type 是 pair<const K, V>，不能修改键