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

容器std :: set（或std :: map）是STL提供的数据结构。在几乎所有的编译器中，它都被实现为具有保证的日志（n）插入，查找和删除时间的R树。如何通过std :: set迭代返回排序结果

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

在红黑树中的元素基于所存储的元件的“少”操作者来分类的。所以基本上如果一个根是N + 1，N将在左子树上，而N + 2将在右子树上，这个顺序将由较少的运算符决定。

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

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

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

来源

2015-11-04 ralzaul

我认为这可能是一个重复http://stackoverflow.com/questions/2558153/what-is-the-underlying-data-structure-of-a-stl-set-in-c – i4h

它不是上述问题的重复，基本上回答了我在这个问题中已经提到的信息 - 基础数据结构是R＆B树。 – ralzaul

通过查看源代码（本例中为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; 
}

所以，最终，它是一本教科书执行树遍历：迭代器持有一个指向“当前”节点的指针，并且只要它来自正确的子节点，就会到树中上一个节点。如果它来自左侧孩子，则会下降到右侧孩子的最左侧孩子节点。

来源

2015-11-04 18:20:31 Benno

迭代器执行[按顺序深度优先树遍历]。 1这通常是以递归算法实现的。由于迭代器的使用不能递归实现，所以迭代器在内部保存了一堆已存在的地方，以便它可以返回树。

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

来源

2015-11-04 16:14:55

RB树节点包含指向父节点的指针，因此不需要堆栈 - 迭代器只是指向节点的指针，并且递增或递减它只是遍历树。 –

所以为了遍历使用从叶子到根的反向指针？ – ralzaul

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

回答

相关问题