STL 源码剖析：Map 与 红黑树

std::map 的底层并不是哈希表，而是一棵红黑树 (Red-Black Tree)。

1. Map 的本质

std::map<K, V> 是一种 关联式容器。

• 有序性：它会自动根据 Key 的大小进行排序（默认从小到大）。
• 底层结构：平衡二叉搜索树（RB-Tree）。

2. 为什么不用 AVL 树？

AVL 树是绝对平衡的二叉搜索树，查询效率极高。但是：

• AVL 树为了维护绝对平衡，在插入/删除节点时，需要频繁进行旋转操作。
• 红黑树 是弱平衡的。它允许左右子树高度差稍大一点，但换取了更少的旋转次数。

结论

对于频繁插入和删除的场景，红黑树的综合性能优于 AVL 树。 这就是 STL 选择红黑树作为 map 和 set 底层的原因。

3. Map vs Unordered_map

这是一道经典的面试题：

特性	std::map	std::unordered_map
底层实现	红黑树 (RB-Tree)	哈希表 (Hash Table)
有序性	Key 有序	无序
查找速度		平均 ，最坏
适用场景	需要按顺序遍历 / 范围查找	只需要快速存取，不关心顺序

4. 迭代器失效问题

• 插入操作：map 的插入不会导致现有迭代器失效（因为节点在内存中是稳定的，只是改了指针）。
• 删除操作：erase(it) 只会让指向当前被删除元素的迭代器失效，其他不受影响。

// ✅ 安全删除的写法
for (auto it = mp.begin(); it != mp.end(); ) {
    if (it->second == target) {
        mp.erase(it++); // 关键：先传递 it 给 erase，然后 it 自增指向下一个
    } else {
        ++it;
    }
}