C++标准库中是否有红黑树或avl树实现？

Question

就像multiset是STL中的二叉搜索树实现一样，是否有可用的RB树或AVL树实现？

Answer 1

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

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

如果您想保证您使用的是 RB 树，您需要检查您的实现，推出自己的实现，或者获取保证它是 RB 树的第三方库。