是否有任何stl :: set实现都不使用红黑树？ [英] Does any stl::set implementation not use a red-black tree?

问题描述

有没有人看到过STL的实现，其中stl :: set不是作为红黑树实现的？

Has anyone seen an implementation of the STL where stl::set is not implemented as a red-black tree?

原因我想问的是，在我的实验中，B-2B树的表现优于stl :: set（以及其他红黑树实现），其结果取决于B的值，为2到4倍。我很好奇是否存在引人注目的在出现更快的数据结构时使用红黑树的原因。

The reason I ask is that, in my experiments, B-2B trees outperform stl::set (and other red-black tree implementations) by a factor of 2 to 4 depending on the value of B. I'm curious if there is a compelling reason to use red-black trees when there appear to be faster data structures available.

推荐答案

Google的一些人实际上建立了一个基于B树的C ++实现标准库容器。它们似乎比标准二叉树实现要好得多。

Some folks over at Google actually built a B-tree based implementation of the C++ standard library containers. They seem to have much better performance than standard binary tree implementations.

不过有一个陷阱。 C ++标准保证从映射或集合中删除元素只会使指向该映射或集合中相同元素的其他迭代器无效。使用基于B树的实现，由于节点的拆分和合并，这些新结构上的擦除成员函数可能会使对树中其他元素的迭代器无效。结果，这些实现不是标准实现的完美替代，也不能在一致的实现中使用。

There is a catch, though. The C++ standard guarantees that deleting an element from a map or set only invalidates other iterators pointing to the same element in the map or set. With the B-tree based implementation, due to node splits and consolidations, the erase member functions on these new structures may invalidate iterators to other elements in the tree. As a result, these implementations aren't perfect replacements for the standard implementations and couldn't be used in a conformant implementation.

希望这会有所帮助！

这篇关于是否有任何stl :: set实现都不使用红黑树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！