在 C++ 中，map 基于黑红树，因此插入/删除函数将花费 O(logn)，而 hash_map 基于哈希。
但我在徘徊，基于什么数据结构设置？
Set 和 map 一样排序，那么 set 是否也基于黑红树？
它的键和值如何存储在该树中？
如果是这样，unorder_set 的数据结构是什么？谢谢！
问问题
596 次
4 回答
19
没有保证。该标准唯一要求的是操作成本，因此实施者可以自由使用他们想要的任何数据结构。通常std::set和std::map是平衡二叉树。
此外，std::unordered_set和std::unordered_map是哈希表。我相信这实际上是由标准保证的，因为您可以手动指定散列函数。
于 2013-10-30T19:45:25.777 回答
9
set和类型可以任意实现，map只要它符合 C++ 规范的时间复杂度要求，它基于平衡二叉搜索树的时间复杂度。map尽管红/黑树对于和很常见set，但它们并不是唯一的选择。你可以用 AVL 树、B 树、AA 树等来实现它们。
希望这可以帮助！
于 2013-10-30T19:45:39.623 回答
7
有序的关联容器，即，std::set<...>以及std::map<...>它们的“多”版本，是基于节点的并且具有最坏情况的O(ln n)复杂性。这意味着使用平衡树。除了复杂性之外，当树发生变异时，指针和迭代器都不会失效（当然，指向erase()d 对象的指针或迭代器除外）。
遗憾的是，B-tree 没有正确的迭代器失效属性（并且由于使用 a 的强制表示，映射需要重复存储密钥以获得大部分优势std::pair<Key, Value>）。在实践中，红/黑树似乎是最有效的，但还有其他可能的平衡策略，例如 AVL 树。跳过列表也可能具有必要的属性。无论哪种情况，该标准都没有规定确切的实施策略。
于 2013-10-30T19:54:45.773 回答
1
As others have said, there doesn't seem to be any guarantee of a specific implementation in the standard. However, the standard does make certain performance guarantees, such as insertion in O(log n) time for sets, which seems to be the real question that you are asking.
于 2013-10-30T21:13:06.743 回答