面试题：C++ 中 map 容器键值存储原理相关问题

Question

请简述 C++ STL 中 map 容器是如何存储键值对的，并且说明为什么 map 中的键是唯一的。

Answer 1

map 容器存储键值对的方式

1. 数据结构：map 容器通常基于红黑树（一种自平衡的二叉搜索树）实现。红黑树具有以下性质：
   • 每个节点是红色或黑色。
   • 根节点是黑色。
   • 每个叶节点（NIL 节点，空节点）是黑色。
   • 如果一个节点是红色的，则它的两个子节点都是黑色的。
   • 从任一节点到其每个叶节点的所有简单路径都包含相同数目的黑色节点。
2. 存储过程：当向 map 中插入一个键值对 (key, value) 时，会根据键 key 的值在红黑树中找到合适的插入位置。因为红黑树是二叉搜索树，左子树的所有节点的键值小于根节点的键值，右子树的所有节点的键值大于根节点的键值。通过比较键值，沿着树的节点不断向下查找，直到找到合适的插入位置，然后将新的键值对插入为一个新的节点。

map 中键唯一的原因

1. 基于二叉搜索树的性质：由于 map 基于二叉搜索树实现，在二叉搜索树中，每个节点的键值是唯一的。如果插入一个已存在键的键值对，在查找插入位置时，会发现该键已经存在于树中，根据 map 的定义，它不会重复插入相同键的元素。
2. 功能需求：map 的设计目的是提供一种通过键快速查找对应值的机制。如果键不唯一，就无法明确通过键找到唯一确定的值，这会破坏 map 作为键值对映射容器的基本功能。例如，在一个存储学生学号和学生信息的 map 中，如果学号（键）可以重复，就无法通过学号准确获取对应的学生信息。