第二节 · 一一对应 · 关联容器

顺序容器按照元素添加的顺序存储数据。但有时候，我们需要根据键（key）来快速查找数据，这就是关联容器的用武之地。

关联容器就像一本字典——你通过单词（键）快速找到释义（值），而不需要从头翻到尾。

---

关联容器概览

容器	说明	特点
map	键值对映射	键有序，键唯一
set	集合	元素有序，元素唯一
multimap	多重映射	键有序，键可重复
multiset	多重集合	元素有序，元素可重复
unordered_map	哈希映射	无序，查找更快
unordered_set	哈希集合	无序，查找更快

---

map：键值对映射

map 存储键值对，每个键唯一，按键排序：

#include <map>
#include <string>
#include <iostream>
using namespace std;

int main()
{
    map<string, int> scores;
    
    // 插入元素
    scores["Alice"] = 95;
    scores["Bob"] = 87;
    scores.insert({"Carol", 92});
    scores.insert(make_pair("David", 78));
    
    // 访问元素
    cout << scores["Alice"] << endl;  // 95
    cout << scores.at("Bob") << endl; // 87
    
    // 注意：[] 访问不存在的键会创建该键！
    cout << scores["Unknown"] << endl;  // 0（新创建的）
    
    // 安全地检查键是否存在
    if (scores.find("Eve") != scores.end())
        cout << "找到了" << endl;
    else
        cout << "没找到" << endl;
    
    // 或使用 count
    if (scores.count("Alice") > 0)
        cout << "Alice 存在" << endl;
    
    // 遍历（按键排序）
    for (const auto& pair : scores)
    {
        cout << pair.first << ": " << pair.second << endl;
    }
    
    // C++17 结构化绑定
    for (const auto& [name, score] : scores)
    {
        cout << name << ": " << score << endl;
    }
    
    return 0;
}

---

set：集合

set 存储唯一元素，自动排序：

#include <set>

set<int> s;

// 插入元素
s.insert(5);
s.insert(3);
s.insert(8);
s.insert(3);  // 重复，不会插入
// s: 3, 5, 8

// 检查元素是否存在
if (s.count(5) > 0)
    cout << "5 存在" << endl;

// C++20: contains
// if (s.contains(5))
//     cout << "5 存在" << endl;

// 删除元素
s.erase(3);

// 遍历（自动排序）
for (int x : s)
    cout << x << " ";  // 5 8
cout << endl;

---

multimap 和 multiset

允许重复键或重复元素：

#include <map>
#include <set>

// multimap：允许重复键
multimap<string, int> mm;
mm.insert({"Alice", 95});
mm.insert({"Alice", 87});  // 同一个键，不同值
mm.insert({"Bob", 92});

// 查找所有匹配的键
auto range = mm.equal_range("Alice");
for (auto it = range.first; it != range.second; ++it)
{
    cout << it->first << ": " << it->second << endl;
}
// Alice: 95
// Alice: 87

// multiset：允许重复元素
multiset<int> ms;
ms.insert(5);
ms.insert(5);
ms.insert(5);
cout << ms.count(5) << endl;  // 3

---

unordered_map 和 unordered_set

使用哈希表实现，查找更快（平均 O(1)），但不保持顺序：

#include <unordered_map>
#include <unordered_set>

// unordered_map
unordered_map<string, int> umap;
umap["one"] = 1;
umap["two"] = 2;
umap["three"] = 3;

// 操作方式与 map 相同
cout << umap["two"] << endl;  // 2

// unordered_set
unordered_set<int> uset = {5, 3, 8, 1, 9};
uset.insert(4);
cout << uset.count(5) << endl;  // 1

// 注意：遍历顺序不确定
for (int x : uset)
    cout << x << " ";  // 顺序可能是任意的
cout << endl;

---

map 的常用操作

map<string, int> m = {{"a", 1}, {"b", 2}, {"c", 3}};

// 大小
cout << m.size() << endl;   // 3
cout << m.empty() << endl;  // false

// 插入
m.insert({"d", 4});
m["e"] = 5;
m.emplace("f", 6);  // 原地构造

// 删除
m.erase("a");           // 按键删除
m.erase(m.begin());     // 按迭代器删除

// 查找
auto it = m.find("b");
if (it != m.end())
    cout << it->second << endl;

// 清空
m.clear();

// 交换
map<string, int> m2;
m.swap(m2);

---

自定义排序

map 和 set 默认按升序排序。可以通过比较函数自定义：

// 方法一：使用函数对象
struct DescCompare
{
    bool operator()(int a, int b) const
    {
        return a > b;  // 降序
    }
};

set<int, DescCompare> s = {1, 5, 3, 8, 2};
for (int x : s)
    cout << x << " ";  // 8 5 3 2 1

// 方法二：使用 greater
set<int, greater<int>> s2 = {1, 5, 3, 8, 2};
for (int x : s2)
    cout << x << " ";  // 8 5 3 2 1

// 对于 map
map<int, string, greater<int>> m;
m[1] = "one";
m[3] = "three";
m[2] = "two";
for (const auto& [k, v] : m)
    cout << k << " ";  // 3 2 1

---

实际应用：单词计数

#include <iostream>
#include <map>
#include <string>
#include <sstream>
using namespace std;

int main()
{
    string text = "hello world hello cpp world world";
    map<string, int> wordCount;
    
    istringstream iss(text);
    string word;
    while (iss >> word)
    {
        wordCount[word]++;
    }
    
    for (const auto& [w, count] : wordCount)
    {
        cout << w << ": " << count << endl;
    }
    // cpp: 1
    // hello: 2
    // world: 3
    
    return 0;
}

---

如何选择关联容器

• 需要键值对：map、unordered_map

• 只需要集合：set、unordered_set

• 需要按顺序遍历：map、set

• 只需要快速查找：unordered_map、unordered_set

• 允许重复：multimap、multiset

---

习题

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

• 使用 set 找出两个数组的交集和并集。

• 比较 map 和 unordered_map 在大量数据下的查找性能。