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

Question

在C++中,map基于黑红树,因此,插入/删除功能将花费O(logn),而hash_map基于哈希.

但我在徘徊,基于什么数据结构设置？

集合按地图排序,因此,是否也基于黑红树设置？

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

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

Answer 1

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

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

Answer 2

该set和map类型可以实现相当多,但是你会喜欢的,只要它符合C++规范,它立足于一个平衡二叉搜索树的时间复杂度的时间复杂度的时间复杂度的要求.虽然红/黑树是共同map和set,他们不是唯一的选择.您可以使用AVL树,B树,AA树等实现它们.

希望这可以帮助!

Answer 3

有序关联容器,即std::set<...>与std::map<...>他们的"多"的版本,是基于节点的并且具有最坏情况O(ln n)的复杂性.这意味着使用了平衡树.除了复杂性之外,当树发生变异时,指针和迭代器都不会失效(当然,erase()d对象的指针或迭代器除外).

遗憾的是,B树没有正确的迭代器失效属性(并且对于映射需要重复存储密钥以获得大部分优势,因为使用了强制表示std::pair<Key, Value>).在实践中,似乎红/黑树最有效,但还有其他可能的平衡策略,例如AVL树.跳过列表也可能具有必要的属性.在任何一种情况下,该标准都没有强制要求确切的实施策略.