我们从多个来源可以看到std :: map是使用红黑树实现的。据我了解，这些类型的数据结构不会以任何特定顺序保存其元素，而只是保持BST属性和高度平衡要求。
那么map :: begin是恒定时间又如何，并且我们能够遍历有序序列呢？
从std::map内部维护BST的前提开始（标准并没有严格要求BST，但是大多数库可能会这样做，就像红黑树一样）。
在BST中，要找到最小的元素，只需跟随左分支，直到到达叶子O（log（N））。但是，如果要在恒定时间内交付“ begin（）”迭代器，仅在内部跟踪最小的元素就非常简单。每次插入导致最小的元素更改时，就进行更新，仅此而已。当然，这是内存开销，但是这是一个折衷。
可能还有其他方法可以选出最小的元素（例如，使根节点故意不平衡）。无论哪种方式，都不难。
要遍历“有序”序列，您只需对树进行有序遍历。从最左边的叶节点开始，您可以（向上），（右侧），（向上，向上），（右侧）等等。。。等等。这是一组简单的规则，易于实现，请看我不久前写的一个简单的BST有序迭代器的快速实现。在进行有序遍历时，您将以正确的顺序访问从最小到最大的每个节点。换句话说，它只是给您一种幻想，即“数组”已排序，但实际上，遍历使它看起来像已排序。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句