有没有任何不使用红黑树的std::set实现？

Question

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

我之所以问这个问题，是因为在我的实验中，B树表现优于std::set（以及其他红黑树实现），具体取决于B值大小，速度提高了2到4倍。我很好奇是否有强制使用红黑树的充分理由，当似乎有更快的数据结构可用。

- Pat Morin

---

我并不是算法专家，但 std::set 和相关的容器都有着由标准规定的严格的最大复杂度（“大O”）要求。一个替代实现是否能够满足所有这些要求？ - Tristan Brindle

你可以在这里查看：为什么不应该使用set（以及你应该使用什么代替它）。 - davidhigh

@TristanBrindle：是的。B-2B树提供相同的复杂度保证。（事实上，红黑树实际上是使用二叉树模拟2-3-4树；这使它们更加复杂和缓慢。） - Pat Morin

@davidhigh：我在搜索中确实看到了那份文档。但它并没有回答我的问题。它建议使用线性更新/搜索时间数据结构，而不是O(log n)时间结构。如果您不打算进行多次搜索或修改，那么这很好，但stl::set仍然在STL中扮演着相当重要的角色。 - Pat Morin

Answer 1

谷歌的一些人实际上构建了一个基于B树的C ++标准库容器实现。它们似乎比标准二叉树实现具有更好的性能。

然而，有一个问题。C ++标准保证从地图或集合中删除元素仅会使指向地图或集合中相同元素的其他迭代器无效。由于节点拆分和合并，这些新结构的删除成员函数可能会使树中其他元素的迭代器无效。因此，这些实现并不是标准实现的完美替代品，不能用于符合规范的实现。

希望这有所帮助！

- templatetypedef

---

啊哈，这就是我一直在寻找的。我想肯定有什么问题。我没有意识到标准允许在树中存在其他迭代器时对树进行修改。不过这是一个相当非标准的用例。当出现这种情况时，应该可以绕过它。 - Pat Morin

阅读您指向的页面，我发现他们已经周到地提供了这样一个黑客：https://code.google.com/p/cpp-btree/wiki/UsageInstructions#Safe_B-Tree_maps_and_sets - Pat Morin

Answer 2

至少有一个实现是基于AVL树而不是红黑树的。

我没有尝试验证这个实现的符合性，但至少（与基于B树的实现不同），它至少可以被编写成完全符合标准要求。

- Jerry Coffin

---

我不确定 AVL 树是否适用；当更改已知位置时，insert 和 erase 需要平摊常数修改时间，而 AVL 树无法提供此功能。 - jbapple

很遗憾，它是GNU GPL许可证。 - plasmacel