c++ - 什么是基于集合的数据结构

Question

在 C++ 中，map 基于黑红树，因此插入/删除函数将花费 O(logn)，而 hash_map 基于哈希。

但我想知道基于什么数据结构设置？

set 和 map 一样排序，那么 set 是否也基于黑红树？

它的键和值是如何存储在那棵树中的？

如果是这样，unorder_set 的数据结构是什么？谢谢!

Answer 1

没有保证。该标准唯一要求的是操作成本，因此实现者可以自由使用他们想要的任何数据结构。通常 std::set 和 std::map 是平衡二叉树。

另外，std::unordered_set 和 std::unordered_map 是哈希表。我相信这实际上是由标准保证的，因为您可以手动指定散列函数。