问如何实现std::map的排序？

EN

从std::map在内部维护BST的前提出发(这不是标准严格要求的，但大多数库可能会这样做，就像一棵红黑树)。

在BST中，要找到最小的元素，您只需跟随左边的分支，直到到达叶子，即O(log(N))。但是，如果您想在恒定时间内交付"begin()“迭代器，那么只在内部跟踪最小元素是非常简单的。每次插入导致最小元素发生更改时，您都会更新它，仅此而已。当然，这是内存开销，但这是一种权衡。

可能还有其他方法来选择最小的元素(比如故意保持根节点的不平衡)。不管怎样，这并不难。

要迭代“有序”序列，只需对树执行有序遍历即可。从最左边的叶节点开始，你走(上)，(右)，(上，上)，(右)，.就这样..。这是一组简单的规则，很容易实现，就像我不久前写的参见简单BST顺序迭代器的快速实现。一样。当您进行有序遍历时，您将以正确的顺序访问每个节点，从最小到最大。换句话说，它只是给你“数组”排序的错觉，但在现实中，是遍历使它看起来像是排序的。

红黑树的平衡属性允许您在树中的任何位置插入一个节点，代价为O(log )。对于典型的std::map实现，容器将保持树的排序，每当插入新节点时，将其插入到正确的位置以保持树的排序，然后重新平衡树以维护红黑属性。

所以不，红黑树不是天生分类的。

RB树是二元搜索树。二进制搜索树不一定以任何特定的顺序存储它们的元素，但是始终可以得到无序遍历。我不确定map::begin如何保证恒定的时间，我假设这包括始终记住最小元素的路径(通常是O(log(N)。