有没有人见过 STL 的实现，其中 stl::set 是not作为红黑树实现？
我问的原因是，在我的实验中，B 树的表现优于std::set（以及其他红黑树实现）的系数为 2 到 4，具体取决于 B 的值。我很好奇，当似乎有更快的数据结构可用时，是否有令人信服的理由使用红黑树。
谷歌的一些人实际上建立了一个C++ 标准库容器的基于 B 树的实现。它们似乎比标准二叉树实现具有更好的性能。
不过，有一个问题。 C++ 标准保证从映射或集合中删除元素只会使指向映射或集合中相同元素的其他迭代器无效。对于基于 B 树的实现，由于节点分裂和合并，这些新结构上的擦除成员函数可能会使树中其他元素的迭代器无效。因此，这些实现并不是标准实现的完美替代，并且不能在一致的实现中使用。
希望这可以帮助！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
