一、map 容器的实现

map 容器底层的实现是红黑树，内部是按照键值排序的（无序的是 unordered_map）。map的实现保证插入、查找和删除时间复杂度是O(log n)，而unordered_map则可以实现常数时间操作（内部由 hash table 实现）。

红黑树是一种自平衡二叉查找树，保证插入、查找和删除时间复杂度是O(log n)。

  1. 红黑树节点要么是红色，要么是黑色；
  2. 红黑树根节点是黑色的；
  3. 每个叶子节点都是黑色的；
  4. 如果一个节点是红色的，那么它的两个叶子节点是黑色的；
  5. 对于每个节点，从该节点到它的所有后代叶子的简单路径上，都包含相同数量的黑色节点。

红黑树的平衡性通过对节点的颜色的调整来实现的。当插入或删除节点时，会破坏红黑树的平衡性，那么就需要旋转和重新分配颜色。