c++ - c++标准库中有没有红黑树或者avl树的实现？

Question

就像multiset是STL中的二叉搜索树实现，有没有RB树或者AVL树实现？

Answer 1

通常您不会将 multiset 实现为二叉搜索树。使用一个会破坏标准的性能保证，因为树可能最终看起来像一个没有 O(logN) 插入和删除的链表。

通常是 std::set/std::multiset/std::map/std::multimap 被实现为 RB 树，因为它具有这些性能保证。但这不是必需的。该标准仅保证容器在不同操作中的性能，如何实现则取决于实现。

如果你想保证你使用的是 RB 树，你需要检查你的实现，自己滚动，或者获得保证它是 RB 树的第三方库。