如何迭代 std::set returns 排序的结果

Question

容器std::set（或std::map）是STL提供的一种数据结构。在几乎所有的编译器中，它都被实现为一个 R&B 树，保证了 log(n) 的插入、查找和删除时间。

https://en.wikipedia.org/wiki/Red%E2%80%93black_tree

在红黑树中，元素根据存储元素的 "less" 运算符进行排序。所以基本上如果一个根是 N + 1 ， N 将在左子树上，而 N + 2 将在右子树上，这个顺序将由 less 运算符决定。

我的问题是在执行以下代码时：

 set<unsigned long>::iterator it;
 for (it = myset.begin(); it != myset.end(); it++) {
     cout << *it;
 }

元素按排序顺序返回。考虑到底层数据结构是红黑树这一事实，这怎么可能呢？是否存储了一个单独的链表以便能够从最左边的子树迭代到最右边的子树？如果不是，这个使用 R&B 树的实现背后的机制是什么？

Answer 1

迭代器执行[有序深度优先树遍历]。1这通常在递归算法中实现。由于无法递归地实现迭代器的使用，因此迭代器在内部保留了一个堆栈，以便它可以返回树上。

更新：感谢 Chris Dodd 指出 RB 树节点有指向其父节点的指针，因此迭代器可以简单地跟随这些节点直到下一个元素。

Answer 2

我们可以通过查看源代码（在本例中为 libstdc++ 5.2.1）找到明确的答案。这是树节点的样子：

// <libstdc++>/include/bits/stl_tree.h
struct _Rb_tree_node_base {
  typedef _Rb_tree_node_base* _Base_ptr;

  _Rb_tree_color    _M_color;
  _Base_ptr     _M_parent;
  _Base_ptr     _M_left;
  _Base_ptr     _M_right;

  // ...
}

所以每个节点都包含一个颜色，并指向它的parent和它的左右children。递增实现为：

//  <libstdc++>/include/bits/stl_tree.h
struct _Rb_tree_iterator {
  _Self& operator++() {
    _M_node = _Rb_tree_increment(_M_node);
    return *this;
  }

// ...

private:
    _Base_ptr _M_node;
};

实际增量不再是public headers，而是在库的编译部分：

// <libstdc++>/src/c++98/tree.cc
static _Rb_tree_node_base* local_Rb_tree_increment(_Rb_tree_node_base* __x) throw ()
{
    if (__x->_M_right != 0) {
        __x = __x->_M_right;
        while (__x->_M_left != 0)
            __x = __x->_M_left;
     } else {
         _Rb_tree_node_base* __y = __x->_M_parent;
         while (__x == __y->_M_right)  {
             __x = __y;
             __y = __y->_M_parent;
         }
         if (__x->_M_right != __y)
             __x = __y;
     }
     return __x;
 }

所以，最终，它是树遍历的教科书式实现：迭代器持有指向 "current" 节点的指针，为了到达下一个节点，它会在树中向上移动，只要它来了从右边 child。如果它来自左侧 child，它将下降到右侧 child.

的最左侧 child 节点

如何迭代 std::set returns 排序的结果

How iterating over a std::set returns sorted results

c++

iteration

stl

c++11