小编典典

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

algorithm

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

尽管我知道底层结构是不同的,但我对它们的实现方式的差异并不感兴趣,而与比较它们的 性能适用 于各种用途的兴趣相比,我对此并不感兴趣。

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


阅读 514

收藏
2020-07-28

共1个答案

小编典典

优先级队列 使您可以按排序的顺序访问 一个
元素-即,您可以获得最高优先级的项目,而将其删除时,您可以获得第二高优先级的项目,依此类推。优先级队列还允许重复的元素,因此它更像是多集而不是集合。[编辑:正如@Tadeusz
Kopec所指出的那样,构建堆也与堆中的项目数量成线性关系,除非根据已经排序的序列构建(在这种情况下,否则构建一个集合为O(N log
N))它也是线性的。]

集合允许您按排序顺序进行完全访问,因此,例如,您可以在集合中间的某个位置找到两个元素,然后依次从一个元素移动到另一个元素。

2020-07-28