std :: set和std :: priority_queue之间的区别 [英] Difference between std::set and std::priority_queue

问题描述

由于 std :: priority_queue 和 std :: set （和 std： ：multiset ）是存储元素并允许您以有序方式访问它们的数据容器，并且具有相同的插入复杂度 O（log n） ，使用一个相对于另一个有什么优点（或者，哪种情况需要一个或另一个？）？

Since both std::priority_queue and std::set (and std::multiset) are data containers that store elements and allow you to access them in an ordered fashion, and have same insertion complexity O(log n), what are the advantages of using one over the other (or, what kind of situations call for the one or the other?)?

虽然我知道底层结构是不同的，我对它们的实现方式的差异不那么感兴趣，而在比较它们的性能和适用性对各种用途的兴趣方面。

While I know that the underlying structures are different, I am not as much interested in the difference in their implementation as I am in the comparison their performance and suitability for various uses.

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

Note: I know about the no-duplicates in a set. That's why I also mentioned std::multiset since it has the exactly same behavior as the std::set but can be used where the data stored is allowed to compare as equal elements. So please, don't comment on single/multiple keys issue.

推荐答案

仅优先级队列 使您可以按顺序访问 one 元素-即，您可以获得最高优先级的项目，而将其删除时，您可以获得第二高优先级的项目，依此类推。优先级队列还允许重复的元素，因此它更像是多集而不是集合。 。

A priority queue only gives you access to one element in sorted order -- i.e., you can get the highest priority item, and when you remove that, you can get the next highest priority, and so on. A priority queue also allows duplicate elements, so it's more like a multiset than a set.

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

A set allows you full access in sorted order, so you can, for example, find two elements somewhere in the middle of the set, then traverse in order from one to the other.

这篇关于std :: set和std :: priority_queue之间的区别的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！