std::map 与 unordered_map 选型指南

一个是平衡二叉搜索树，一个是哈希表。选型不靠感觉，靠三个问题：要不要有序、查找是否热点、键的哈希是否便宜。

一、复杂度与常数

维度	std::map	std::unordered_map
底层结构	红黑树	桶数组 + 链表/节点
查找	O(log n)，稳定	均摊 O(1)，最坏 O(n)
迭代顺序	按键升序	无序，可能随 rehash 变化
内存	每节点多指针，较省	桶数组 + 节点，通常更多
迭代器失效	仅删除的元素	rehash 后全部失效
键要求	operator<	std::hash + operator==

小数据量（几十个元素）时 map 可能更快，因为哈希计算与缓存不友好抵消了渐进优势。真实结论必须 benchmark。

二、operator[] 的隐式插入

std::map<std::string, int> m;
int x = m["not_exist"];      // m 里插入了 "not_exist" -> 0

operator[] 会默认构造值并插入，这是 const 容器不能用它的原因，也是"查询却污染容器"的经典 bug。

安全查询：

// C++17
if (auto it = m.find(key); it != m.end()) { use(it->second); }

// 计数（注意 map 的 count 是 0/1）
if (m.count(key)) { use(m.at(key)); }

// C++20
if (m.contains(key)) { use(m.at(key)); }

需要"不存在则插入"时，用 try_emplace（C++17）避免无谓构造：

m.try_emplace(key, expensiveValue());   // 已存在则不构造 value
// 对比 m.insert({key, expensiveValue()}); 无论是否插入都构造

三、C++17 的结构化插入：insert_or_assign

m.insert_or_assign("a", 1);   // 等价于 m["a"] = 1，但语义清晰且不要求值可默认构造

四、删除的两种正确写法

// C++11 起：erase 返回下一个迭代器
for (auto it = m.begin(); it != m.end(); ) {
    if (shouldRemove(it->second)) it = m.erase(it);
    else ++it;
}

// C++20
std::erase_if(m, [](const auto& kv) { return shouldRemove(kv.second); });

错误写法：在范围 for 里 m.erase(key) 再继续迭代，会导致迭代器失效。

五、自定义键类型

用于 map

需要 operator< 或自定义比较器：

struct Point { int x, y; };

struct PointLess {
    bool operator()(const Point& a, const Point& b) const {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    }
};
std::map<Point, int, PointLess> mp;

比较器必须满足严格弱序（Strict Weak Ordering）：cmp(a,a) == false，且传递性成立。写成 <= 是极常见的错误，会导致未定义行为。

用于 unordered_map

需要 std::hash 特化或自定义哈希仿函数：

struct PointHash {
    std::size_t operator()(const Point& p) const {
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};
std::unordered_map<Point, int, PointHash> um;

哈希质量差会让所有元素挤进同一个桶，退化为链表。改哈希时记得同步验证冲突率。

六、预留桶数与负载因子

std::unordered_map<int, Foo> um;
um.reserve(10000);              // 一次到位，避免多次 rehash
std::cout << um.load_factor();  // 默认上限约 1.0
um.max_load_factor(0.7f);       // 降低负载因子，空间换查找速度

大规模插入前不 reserve 是 unordered_map 最典型的性能坑。

七、内存与缓存友好性

• map/unordered_map 都是节点式容器，每个元素单独分配，遍历时缓存命中率低；
• 若数据量在几万以内且需要频繁全量遍历，扁平结构（std::vector<std::pair<K,V>> + 排序）常常更快；
• 只读数据可以先用 vector 排序，用 std::lower_bound 查找，内存与速度都优于 map。

std::vector<std::pair<int, std::string>> table;   // 构建后不再修改
std::sort(table.begin(), table.end());
auto it = std::lower_bound(table.begin(), table.end(), key,
                           [](const auto& kv, int k) { return kv.first < k; });

八、常见陷阱清单

陷阱	后果	修复
用 operator[] 查询	意外插入	find / contains
比较器用 <=	未定义行为、丢元素	严格弱序
迭代时 erase	迭代器失效	it = m.erase(it)
unordered_map 未 reserve	频繁 rehash	预留预期规模
用可变对象当键	破坏有序性/哈希	键保持不可变
遍历 unordered_map 依赖顺序	结果不稳定	需要顺序就换 map 或自行排序

九、决策流程

1. 需要按键有序遍历 → map；
2. 不需要顺序，查找是热点，键哈希便宜 → unordered_map；
3. 元素数很小（< 100）→ 都可以，倾向 map（可预测）；
4. 数据只读且要紧凑内存 → 排序 vector + 二分；
5. 需要按值查找（非键）→ 两种都不合适，考虑建立反向索引。

容器选错不会让程序崩溃，只会让它慢，而且慢得莫名其妙。选型前先想清楚访问模式。