std::map的排序方式是如何实现的？

Question

我们可以从多个来源看到，std::map是使用红黑树实现的。据我所知，这些类型的数据结构不会按任何特定顺序保存其元素，只是维护BST属性和平衡要求。

那么，为什么map :: begin是常数时间，并且我们能够迭代有序序列呢？

- Steve M

---

https://dev59.com/lmsz5IYBdhLWcg3wy7LU#7648812 - Matt Coubrough

@Matt Courbrough说std::map被保证是排序的，但没有说明它是如何使用红黑树来实现的。 - Steve M

可能误解了你的问题，但这些答案都是关于用于排序的比较函数。 - Matt Coubrough

DietrichEpp的回答涵盖了排序方面。关于“那么，为什么map::begin是常数时间”的问题 - 实现方案不是在调用begin时下降到树中（这将是O(log2N)），而是追踪当前树中最小值节点（可能内部选择指针或迭代器 - 最终可能是相同的东西，但是begin本身显然会返回一个迭代器），在erase、insert等操作之后如果有必要进行更新 - 因此可以在常数时间内提供。类似地，最后一个节点也会被类似地追踪（用于rbegin()）。 - Tony Delroy

@Tony D 对于起始迭代器来说，那很有道理。我猜它一定会在某个时候进行遍历和排序以获取序列的其余部分？ - Steve M

Answer 1

从一个假设出发，即std::map在内部维护了一棵二叉搜索树（这不是标准严格要求的，但大多数库可能像红黑树一样做）。在二叉搜索树中，要找到最小元素，只需沿着左侧分支走到达叶子节点，这需要O(log(N))时间。然而，如果您想在常数时间内提供"begin()"迭代器，只需在内部跟踪最小元素即可。每次插入导致最小元素更改时，您都要进行更新。当然，这会增加内存开销，但这是一种权衡。可能还有其他方法可以单独找到最小元素（比如故意保持根节点不平衡）。无论哪种方式，它们都不难实现。

为了遍历"有序"序列，您只需对树进行中序遍历。从最左边的叶节点开始，你顺序往上、右、再往上、再往右……如此简单的一组规则，易于实现，只需查看我写过的一个简单BST中序迭代器的快速实现。当你进行中序遍历时，你会按正确的顺序访问从最小到最大的每个节点。换句话说，它只是为你营造了"数组"已排序的假象，但实际上是遍历使其看起来像是排序的。

- Mikael Persson

---

谢谢，我缺少中序遍历产生排序顺序的那一部分。 - Steve M

@SteveM 顺便说一下，像 std::map 这样的容器并不擅长迭代。树遍历的逻辑，加上你一直在内存中跳来跳去，使得实际性能相当差。因此，将它们用于“主要查找，偶尔有序遍历”或查找值范围等情况。对于快速遍历，通常最好维护一个排序的 std::vector。我的图表提到了这一点。 - Mikael Persson

Answer 2

红黑树的平衡性能使您可以以O(log N)的代价在树的任何位置插入节点。对于典型的std::map实现，容器将保持树的排序状态，并在插入新节点时将其插入正确的位置以保持树的排序状态，然后重新平衡树以维护红黑属性。

因此，红黑树本质上并不是有序的。

- Dietrich Epp

Answer 3

红黑树是二叉搜索树。二叉搜索树不一定按任何特定顺序存储其元素，但您始终可以获得中序遍历。我不确定 map::begin 如何保证常数时间，我会假设这涉及始终记住到最小元素的路径（通常为 O(log(n))）。

- Cubic