c++ - STL maps中的key是如何升序排列的？

Question

当我在 for 循环中遍历 map 时

for(auto it : my_map )
cout << it.first << "\n" ;

当数据实际以平衡树的形式存储时，我如何获得有序列表。另外这个操作的时间复杂度是多少 O(n) ？

Answer 1

好问题。 map 确实被实现为平衡树(通常实现选择红黑树)。整个树的所有节点都保存值(即不仅仅是叶节点)，并且它们被排序使得来自任何节点的“左”分支仅包含“小于”节点自身值的值，“右”分支包含更大的值值(value)观。

例如:

           m
         /   \
        f     q
       / \   / \
      c   h o   t
         /
        g

要遍历树，您最初从 C 开始，必须由 map 对象本身中的指针跟踪，否则开始不会是 O(1)。然后从任何给定节点，迭代只是执行以下 3 个适用选项中的第一个:

1) 如果您已经在最右边的节点， map 对象也必须跟踪该节点，停止； 否则...

2) 如果有一个去右 child ，然后尽可能地跟随它的“左 child ”指针向下，否则......

3) 按照链接回到父节点/祖父节点等节点，直到您发现刚刚上升的节点是其父节点的左节点(此时父节点的值将大于任何您从中上升的节点；请注意，比较指针/链接始终很便宜，因此这比比较某些类型可能很昂贵的键值要好)

• 例如，当您将 g 提升到 h 时，您将来自左子节点，因此应该在 h 处停止；然后在下一次迭代中你将首先上升到 f 但看到你不是来自左 child 所以继续从 f 上升到 m，它来自左 child ，所以这将是你迭代期间的下一站

Also how is time complexity of this operation O(n) ?

假设您在纸上画了一棵树并用箭头书写以显示您如何使用上面的逻辑遍历树，您将看到在任何给定的“左 child / parent ”链接之后只有一次下降，然后是一次上升通过相同的链接。因此，链接遍历的次数 < 2n，比较的次数就更少了——显然是 O(n)。