带有RB树的地图的内部实现

Question

如何在内部借助红黑树实现地图，如何存储键和值以及为什么查找最小值或最大值的复杂度为O（1）？如果我错了，请纠正我]

Answer 1

std :: map将键和值存储为：

std::pair<KeyType const, ValueType>

该对存储在映射内部的节点类型内，该节点类型将指针与左，右树子代添加到父代（必须具有父代指针才能执行树的有效迭代）。

std :: map本身只需要保留一个分配器对象以及内部节点类型的指针部分。

地图对象的指针包含对树的根元素以及min和max元素的引用。这确实要求插入和擦除要比仅插入或删除值执行更多的工作，因为在适当的情况下必须更新这些指针。可以确定，在插入和擦除方面进行的这种额外的微不足道的努力是值得的折衷，因为它可以具有O（1）begin（）和end（）。