2.2 关联容器

关联容器通过键(key)来组织数据,提供高效的查找、插入和删除操作。标准库提供两大类:有序关联容器(基于红黑树,按键排序)和无序关联容器(基于哈希表,O(1) 平均查找)。C++23 还引入了 std::flat_map——一种缓存友好的有序容器。

1. 有序关联容器

std::map<K, V> — 有序键值对

std::map 内部使用红黑树实现,所有元素按键的 operator< 排序。查找、插入、删除均为 O(log n)。

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

int main() {
    // 初始化
    std::map<std::string, int> scores{
        {"Alice", 95},
        {"Bob",   87},
        {"Carol", 92}
    };

    // 插入元素
    scores.insert({"Dave", 78});        // insert 方式
    scores.emplace("Eve", 88);          // emplace: 就地构造
    scores["Frank"] = 73;               // operator[]: 不存在则默认构造后赋值

    // 查找
    if (auto it = scores.find("Alice"); it != scores.end()) {
        std::cout << it->first << ": " << it->second << "\n";
    }

    // C++20: contains() — 更简洁的存在性检查
    if (scores.contains("Bob")) {
        std::cout << "Bob is in the map\n";
    }

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

    // 遍历 — 总是按 key 升序
    for (const auto& [name, score] : scores) {
        std::cout << name << " -> " << score << "\n";
    }
    // 输出: Alice -> 95, Bob -> 87, Carol -> 92, Dave -> 78, Eve -> 88
}

提示:operator[] 在键不存在时会默认构造一个值并插入。如果只是想查找而不插入,请使用 find() 或 contains()。

std::set<T> — 有序唯一元素集合

std::set 存储唯一元素,同样基于红黑树。没有"值"部分,元素本身就是键。

#include <set>
#include <iostream>

int main() {
    std::set<int> primes{2, 3, 5, 7, 11, 13};

    primes.insert(17);
    primes.insert(7);   // 重复元素,插入无效

    std::cout << "count(7) = " << primes.count(7) << "\n";  // 1
    std::cout << "count(4) = " << primes.count(4) << "\n";  // 0

    // 范围查找: [5, 13)
    auto lo = primes.lower_bound(5);
    auto hi = primes.lower_bound(13);
    for (auto it = lo; it != hi; ++it) {
        std::cout << *it << " ";  // 5 7 11
    }
}

自定义比较器

有序容器默认使用 std::less<Key>(即 operator<)。你可以通过模板参数或构造函数提供自定义比较逻辑:

#include <map>
#include <string>

// 方式一:函数对象
struct CaseInsensitiveLess {
    bool operator()(const std::string& a, const std::string& b) const {
        return std::lexicographical_compare(
            a.begin(), a.end(), b.begin(), b.end(),
            [](char c1, char c2) {
                return std::tolower(c1) < std::tolower(c2);
            });
    }
};

// 大小写不敏感的 map
std::map<std::string, int, CaseInsensitiveLess> config;
config["Timeout"] = 30;
config["timeout"] = 60;  // 视为相同 key,覆盖上面的值
// config.size() == 1

C++20 提示:有序容器支持透明比较器(heterogeneous lookup)。定义 using is_transparent = void; 后,find() 可以接受不同类型的参数,避免构造临时 key 对象。

2. 无序关联容器

当不需要有序遍历时,无序容器提供更快的平均性能。它们内部使用哈希表:元素通过哈希函数映射到桶(bucket),查找、插入平均 O(1),最坏 O(n)。

std::unordered_map 与 std::unordered_set

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

int main() {
    // unordered_map: 哈希表实现的键值对
    std::unordered_map<std::string, double> prices{
        {"apple",  3.5},
        {"banana", 2.8},
        {"cherry", 12.0}
    };

    prices["durian"] = 45.0;

    // 查找:平均 O(1)
    if (auto it = prices.find("banana"); it != prices.end()) {
        std::cout << "banana: " << it->second << " yuan\n";
    }

    // unordered_set: 哈希表实现的唯一集合
    std::unordered_set<std::string> visited{"home", "about"};
    visited.insert("contact");

    if (visited.contains("home")) {   // C++20
        std::cout << "Already visited home\n";
    }

    // 查看内部状态
    std::cout << "bucket_count: " << prices.bucket_count() << "\n";
    std::cout << "load_factor:  " << prices.load_factor() << "\n";
}

自定义哈希函数

标准库为基本类型和 std::string 提供了 std::hash 特化。对于自定义类型,需要提供哈希函数:

#include <unordered_map>
#include <functional>

struct Point {
    int x, y;

    bool operator==(const Point&) const = default;  // C++20
};

// 方式一:特化 std::hash
template<>
struct std::hash<Point> {
    size_t operator()(const Point& p) const noexcept {
        // 组合多个哈希值的常用技巧
        size_t h1 = std::hash<int>{}(p.x);
        size_t h2 = std::hash<int>{}(p.y);
        return h1 ^ (h2 << 32) ^ (h2 >> 32);
    }
};

// 现在可以直接使用
std::unordered_map<Point, std::string> labels;
labels[{0, 0}] = "origin";
labels[{1, 2}] = "point A";

注意:哈希函数的质量直接影响性能。糟糕的哈希函数会导致大量冲突,使查找退化为 O(n)。避免使用简单的异或(x ^ y),因为 {1,2} 和 {2,1} 会产生相同的哈希值。

有序 vs 无序:性能对比

// 性能特征对比
// std::map<K,V>:
//   - 插入: O(log n)
//   - 查找: O(log n)
//   - 删除: O(log n)
//   - 有序遍历: O(n),天然有序
//   - 内存: 每个节点单独分配(指针开销大)

// std::unordered_map<K,V>:
//   - 插入: O(1) 平均, O(n) 最坏
//   - 查找: O(1) 平均, O(n) 最坏
//   - 删除: O(1) 平均
//   - 遍历: O(n),顺序不确定
//   - 内存: 桶数组 + 链表节点

3. std::flat_map (C++23)

std::flat_map 是 C++23 引入的有序关联容器适配器。它将键和值分别存储在两个连续的 std::vector 中,保持有序排列。这带来了显著的缓存友好性。

#include <flat_map>   // C++23
#include <string>
#include <iostream>

int main() {
    // API 与 std::map 几乎相同
    std::flat_map<std::string, int> scores;

    scores.insert({"Alice", 95});
    scores.emplace("Bob", 87);
    scores["Carol"] = 92;

    // 查找: O(log n) 二分搜索,但缓存命中率高
    if (scores.contains("Alice")) {
        std::cout << scores["Alice"] << "\n";
    }

    // 遍历: 连续内存,对 CPU 缓存非常友好
    for (const auto& [name, score] : scores) {
        std::cout << name << ": " << score << "\n";
    }

    // 可以自定义底层容器
    // std::flat_map<int, std::string,
    //     std::less<int>,
    //     std::vector<int>,
    //     std::vector<std::string>> custom_map;
}

何时使用 flat_map:

  • 元素数量较少(几百到几千),查找远多于插入/删除
  • 需要有序遍历且追求缓存效率
  • 一次性构建后主要做查询("build once, query many")

不适用场景:频繁插入/删除(因为底层 vector 需要移动元素,O(n) 代价)。

4. 实用操作

结构化绑定遍历

C++17 的结构化绑定让 map 遍历变得极其简洁:

std::map<std::string, std::vector<int>> student_scores{
    {"Alice", {95, 87, 92}},
    {"Bob",   {78, 85, 90}}
};

// 结构化绑定 + const 引用:零拷贝遍历
for (const auto& [name, scores] : student_scores) {
    int sum = 0;
    for (int s : scores) sum += s;
    std::cout << name << " avg: " << sum / scores.size() << "\n";
}

// 可修改值
for (auto& [name, scores] : student_scores) {
    scores.push_back(100);  // 给每人加一个满分
}

try_emplace — 避免冗余构造

try_emplace 只在键不存在时构造值。与 emplace 不同,如果键已存在,参数不会被移动走:

#include <map>
#include <string>
#include <vector>

std::map<std::string, std::vector<int>> data;

// emplace 的问题:即使 key 已存在,参数也可能被移动
std::vector<int> vals{1, 2, 3};
data.emplace("key", std::move(vals));
// 如果 "key" 已存在,vals 可能已被移动但插入失败!

// try_emplace:key 已存在时不会触碰参数
std::vector<int> safe_vals{4, 5, 6};
auto [it, inserted] = data.try_emplace("key", std::move(safe_vals));
if (!inserted) {
    // safe_vals 保证未被移动,仍然有效
    std::cout << "key exists, safe_vals still has "
              << safe_vals.size() << " elements\n";
}

insert_or_assign — 明确的"插入或更新"

std::map<std::string, int> config;

// insert_or_assign: 存在则赋值,不存在则插入
// 返回 {iterator, bool},bool 表示是否为新插入
auto [it1, was_new1] = config.insert_or_assign("timeout", 30);
// was_new1 == true (新插入)

auto [it2, was_new2] = config.insert_or_assign("timeout", 60);
// was_new2 == false (已存在,执行赋值)
// config["timeout"] == 60

// 对比 operator[]:
// config["timeout"] = 60;  // 功能相同,但无法区分是插入还是更新

extract 和 merge (C++17)

extract 可以从容器中"摘出"一个节点而不销毁它,实现零拷贝的键修改或容器间移动:

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

int main() {
    std::map<std::string, int> src{
        {"alpha", 1}, {"beta", 2}, {"gamma", 3}
    };
    std::map<std::string, int> dst{
        {"delta", 4}
    };

    // extract: 摘出节点,修改 key(唯一合法修改 key 的方式)
    auto node = src.extract("beta");
    if (!node.empty()) {
        node.key() = "BETA";        // 修改 key!
        dst.insert(std::move(node)); // 移入目标 map
    }

    // merge: 批量移动节点(零拷贝)
    dst.merge(src);  // src 中不冲突的节点全部移入 dst
    // src 现在只保留与 dst 冲突的节点

    std::cout << "dst: ";
    for (const auto& [k, v] : dst) {
        std::cout << k << "=" << v << " ";
    }
    // dst: BETA=2 alpha=1 delta=4 gamma=3
}

contains() vs find() != end()

std::map<std::string, int> m{{"x", 1}, {"y", 2}};

// C++20 之前:冗长的存在性检查
if (m.find("x") != m.end()) { /* ... */ }
if (m.count("x") > 0) { /* ... */ }     // count 对 map 只能是 0 或 1

// C++20:简洁明了
if (m.contains("x")) { /* ... */ }

// 注意:如果需要使用找到的值,仍然用 find()
if (auto it = m.find("x"); it != m.end()) {
    use(it->second);  // 使用值
}
// contains() 只告诉你"存在与否",不返回值

5. 选择指南

下表对比三种主要的键值对容器,帮助你根据场景选择:

特性 std::map std::unordered_map std::flat_map (C++23)
底层结构 红黑树 哈希表 排序的 vector 对
查找复杂度 O(log n) O(1) 平均 O(log n),缓存友好
插入复杂度 O(log n) O(1) 平均 O(n)(需移动元素)
有序遍历 天然有序 无序 天然有序
内存布局 散落的节点(指针跳转) 桶数组 + 链表 连续内存
缓存友好性 差 中等 优秀
迭代器稳定性 插入/删除不失效 rehash 时失效 插入/删除均失效
最佳场景 需要有序遍历、频繁增删 大量数据、快速查找 构建后主要查询、小规模
Key 要求 operator< 或自定义比较 std::hash + operator== operator< 或自定义比较

性能陷阱:std::map 的每个节点都是独立的堆分配,对 CPU 缓存极不友好。在百万级元素的纯查找场景中,std::unordered_map 可能比 std::map 快 5-10 倍。但如果你需要范围查询(range query)或有序输出,std::map 是唯一直接支持的选择。

本节小结

  • std::map / std::set:红黑树实现,O(log n) 操作,元素总是有序
  • std::unordered_map / std::unordered_set:哈希表实现,O(1) 平均查找,需要提供哈希函数
  • std::flat_map (C++23):底层使用排序 vector,缓存友好,适合"写少读多"场景
  • C++17 引入 try_emplace、insert_or_assign、extract、merge,大幅增强了 map 操作的精确性和效率
  • C++20 的 contains() 取代了繁琐的 find() != end() 模式
  • 选择容器时,先明确你的核心需求:有序?高速查找?缓存友好?频繁增删?