std :: set和std :: priority_queue之间的区别

Question

由于两者std::priority_queue和std::set(和std::multiset)都是存储元素的数据容器,并允许您以有序的方式访问它们,并且具有相同的插入复杂性O(log n),因此使用一个优于另一个(或者,什么样的情况需要一个)或者其他？)？

虽然我知道底层结构是不同的,但我对它们的实现差异并不那么感兴趣,因为我在比较它们的性能和适用于各种用途.

注意:我知道集合中没有重复.这就是我之所以提到的原因,std::multiset因为它具有与之完全相同的行为,std::set但可以在允许存储的数据作为相等元素进行比较的情况下使用.所以,请不要评论单/多键问题.

Answer 1

优先级队列只允许您按排序顺序访问一个元素 - 即,您可以获得最高优先级的项目,当您删除它时,您可以获得下一个最高优先级,依此类推.优先级队列也允许重复元素,因此它更像是多集而不是集.[编辑:正如@Tadeusz Kopec指出的那样,构建堆也是堆中项目数量的线性,其中构建集合是O(N log N),除非它是从已经订购的序列构建的(在这种情况下)它也是线性的.]

集合允许您按排序顺序进行完全访问,因此您可以在集合中间的某处找到两个元素,然后按顺序遍历从一个到另一个.

Answer 2

std::priority_queue 允许执行以下操作:

1. 插入元素 O(log n)
2. 获得最小的元素O(1)
3. 擦除最小的元素O(log n)

虽然std::set有更多的可能性:

1. 插入任何元素O(log n),常量大于instd::priority_queue
2. 找到任何元素O(log n)
3. 找到一个元素,> =而不是你要找的元素O(log n)(lower_bound)
4. 删除任何元素O(log n)
5. 按排序顺序移动到上一个/下一个元素 iterator
6. 获得最小的元素O(1)
7. 获得最大的元素O(1)

Answer 3

set/multiset通常由二叉树支持. http://en.wikipedia.org/wiki/Binary_tree

priority_queue通常由堆支持. http://en.wikipedia.org/wiki/Heap_(data_structure)

所以问题是你何时应该使用二叉树而不是堆？

两种结构都布置在树中,但是关于祖先之间关系的规则是不同的.

我们将父母的职位P称为左子,L称为右子的职位.

在二叉树中L <P <R

在堆P <L和P <R

所以二进制树排序"横向",堆排序"向上".

因此,如果我们将其视为三角形而不是二叉树L,P,R是完全排序的,而在堆中L和R之间的关系是未知的(只有它们与P的关系).

这具有以下效果:

• 如果你有一个未排序的数组,并希望将其转换为二叉树,则需要O(nlogn)时间.如果你想把它变成一堆它只需要O(n)时间,(因为它只是比较找到极端元素)

• 如果您只需要极端元素(某些比较函数的最低或最高),则堆效率更高.堆只做必要的比较(懒惰)来确定极端元素.

• 二叉树执行订购整个集合所需的比较,并始终对整个集合进行排序.

• 堆具有最低元素的恒定时间查找(查看),二进制树具有最低元素的对数时间查找.

Answer 4

由于std::priority_queueand和std::set（and std::multiset）都是存储元素的数据容器，并允许您以有序的方式访问它们，并且具有相同的插入复杂度O(log n)，因此使用一个与另一个相比有什么好处（或者，哪种情况需要使用一种）还是其他？）？

即使两个容器的插入和擦除操作具有相同的复杂度O（log n），对于来说，这些操作std::set都比慢std::priority_queue。那是因为要std::set进行许多内存分配。的每个元素std::set都以其自己的分配存储。std::priority_queue（std::vector默认情况下为底层容器）使用单一分配来存储所有元素。另一方面，std::priority_queue在其元素上使用许多交换操作，而std::set仅使用指针交换。因此，如果元素类型的交换操作非常慢，则使用std::set可能会更有效。此外，元素可能根本不可交换。

的内存开销std::set也更大，这是因为它必须在其节点之间存储许多指针。