由于std::priority_queueand和std::set(and std::multiset)都是存储元素的数据容器,并允许您以有序的方式访问它们,并且具有相同的插入复杂度O(log n),因此使用一个与另一个相比有什么好处(或者,哪种情况需要使用一个)还是其他?)?
std::priority_queue
std::set
std::multiset
O(log n)
尽管我知道底层结构是不同的,但我对它们的实现方式的差异并不感兴趣,而与比较它们的 性能 和 适用 于各种用途的兴趣相比,我对此并不感兴趣。
注意: 我知道集合中没有重复项。这就是为什么我也提到了std::multiset它,因为它的行为与完全相同,std::set但是可以在允许存储的数据作为相等元素进行比较的情况下使用。因此,请不要对单键/多键问题发表评论。
优先级队列 仅 使您可以按排序的顺序访问 一个 元素-即,您可以获得最高优先级的项目,而将其删除时,您可以获得第二高优先级的项目,依此类推。优先级队列还允许重复的元素,因此它更像是多集而不是集合。[编辑:正如@Tadeusz Kopec所指出的那样,构建堆也与堆中的项目数量成线性关系,除非根据已经排序的序列构建(在这种情况下,否则构建一个集合为O(N log N))它也是线性的。]
集合允许您按排序顺序进行完全访问,因此,例如,您可以在集合中间的某个位置找到两个元素,然后依次从一个元素移动到另一个元素。