如何迭代std :: set会返回排序结果

Question

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

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

在红色和黑色树中,元素基于存储元素的"较少"运算符进行排序.所以基本上如果根是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

我们可以通过查看源代码(本例中为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;

  // ...
}

因此,每个节点都包含一个颜色,以及指向其父级及其左右子级的指针.增量实现为:

//  <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;
};

实际的增量不再在公共头中,而是在库的编译部分:

// <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;
 }

因此,最终,它是树遍历的教科书实现:迭代器保存指向"当前"节点的指针,并且只要它来自正确的子节点,它就到达下一个节点,它在树中上升.如果它来自左边的孩子,它将下降到右孩子的最左边的子节点.