map / unordered_map

map 基于红黑树，有序但 O(log n)；unordered_map 基于哈希表，无序但 O(1)。选对容器，性能差异可达 10x。

map — 有序关联容器

#include <map>

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

// 插入
scores["Alice"] = 95;                          // 下标运算符（不存在则插入默认值）
scores.insert({"Bob", 87});                    // insert
scores.emplace("Charlie", 92);                 // emplace（原地构造，推荐）
auto [it, ok] = scores.try_emplace("Dave", 88); // C++17，键不存在才插入

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

// 安全访问（C++20）
// scores.at("Alice");  // 不存在抛 std::out_of_range
// scores["NewKey"];    // 不存在则插入 0，危险！

// 删除
scores.erase("Bob");
scores.erase(scores.find("Charlie"));  // 通过迭代器删除

// 遍历（按键有序）
for (const auto& [key, val] : scores) {
    std::cout << key << ": " << val << "\n";
}

// 范围查找
auto lo = scores.lower_bound("B");  // 第一个 >= "B" 的键
auto hi = scores.upper_bound("D");  // 第一个 > "D" 的键
for (auto it = lo; it != hi; ++it) {
    std::cout << it->first << "\n";  // B、C、D 开头的键
}

unordered_map — 哈希表

#include <unordered_map>

std::unordered_map<std::string, int> freq;

// 词频统计（经典用法）
std::string text = "hello world hello cpp world hello";
for (const auto& word : split(text)) {
    ++freq[word];  // 不存在则插入 0，再 +1
}

// 或者更高效
freq["hello"]++;

// 查找
if (freq.count("hello")) {  // count 返回 0 或 1
    std::cout << freq["hello"] << "\n";
}

// C++20 contains
if (freq.contains("world")) {
    std::cout << "found\n";
}

// 性能调优
freq.reserve(1000);          // 预分配桶，避免 rehash
freq.max_load_factor(0.5);   // 降低负载因子，减少冲突（更多内存）
std::cout << freq.bucket_count() << "\n";  // 桶数量
std::cout << freq.load_factor() << "\n";   // 当前负载因子

自定义键类型

// map 需要 operator< 或自定义比较器
struct Point {
    int x, y;
    bool operator<(const Point& o) const {
        return x != o.x ? x < o.x : y < o.y;
    }
};

std::map<Point, std::string> point_map;
point_map[{1, 2}] = "A";

// unordered_map 需要 hash 和 operator==
struct PointHash {
    size_t operator()(const Point& p) const {
        // 常用哈希组合方式
        size_t h1 = std::hash<int>{}(p.x);
        size_t h2 = std::hash<int>{}(p.y);
        return h1 ^ (h2 << 32) ^ (h2 >> 32);
    }
};

struct PointEqual {
    bool operator()(const Point& a, const Point& b) const {
        return a.x == b.x && a.y == b.y;
    }
};

std::unordered_map<Point, std::string, PointHash, PointEqual> umap;
umap[{1, 2}] = "A";

// C++20 更简洁：只需定义 operator== + std::hash 特化
template<>
struct std::hash<Point> {
    size_t operator()(const Point& p) const noexcept {
        return std::hash<long long>{}((long long)p.x << 32 | p.y);
    }
};

multimap — 允许重复键

#include <map>

std::multimap<std::string, int> mm;
mm.insert({"Alice", 90});
mm.insert({"Alice", 95});  // 允许重复键
mm.insert({"Bob", 87});

// 查找所有同键元素
auto range = mm.equal_range("Alice");
for (auto it = range.first; it != range.second; ++it) {
    std::cout << it->second << "\n";  // 90, 95
}

std::cout << mm.count("Alice") << "\n";  // 2

性能对比与选择

// 基准测试（100万次操作，仅供参考）
// map:          ~200ms（O(log n)，红黑树，cache 不友好）
// unordered_map: ~50ms（O(1) 均摊，哈希表）

// 选 map 的场景：
// - 需要有序遍历
// - 需要范围查询（lower_bound/upper_bound）
// - 键类型没有好的哈希函数
// - 需要稳定的最坏情况性能

// 选 unordered_map 的场景：
// - 只需要查找/插入/删除
// - 键是 int/string 等有内置哈希的类型
// - 性能敏感，数据量大

// 高性能替代：absl::flat_hash_map（Google Abseil）
// 比 std::unordered_map 快 2-3x，内存更紧凑

节点操作（C++17）

// C++17 节点句柄：零拷贝地在容器间转移元素
std::map<int, std::string> m1 = {{1, "one"}, {2, "two"}};
std::map<int, std::string> m2;

// 从 m1 提取节点，插入 m2（零拷贝）
auto node = m1.extract(1);
node.key() = 10;  // 修改键（以前做不到！）
m2.insert(std::move(node));

// merge：将 m1 的所有节点移入 m2
m2.merge(m1);

关键认知

unordered_map 在大多数场景比 map 快 3-5x，但需要键类型有哈希函数。operator[] 会在键不存在时插入默认值，查找时用 find 或 contains 更安全。高性能场景考虑 absl::flat_hash_map。