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

Question

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

Answer 1

通常您不会将

multiset

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

通常

std::set

/

std::multiset

/

std::map

/

std::multimap

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

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

Answer 2

从我的帖子中得知，不，截至今天，即 2022 年 1 月 10 日，红黑树还没有标准的 C++ 库。

Answer 3

std::map 是一个排序的关联容器，其中包含具有唯一键的键值对。使用比较函数 Compare 对键进行排序。搜索、删除和插入操作具有对数复杂度。地图通常被实现为红黑树 https://en.cppreference.com/w/cpp/container/map