由于std::priority_queue和std::set(and std::multiset) 都是存储元素并允许您以有序方式访问它们的数据容器，并且具有相同的插入复杂性O(log n)，因此使用一个比另一个有什么优势（或者，什么样的情况需要一个还是其他？）？
虽然我知道底层结构是不同的，但我对它们实现的差异并不感兴趣，而是对它们的性能和对各种用途的适用性进行比较。
注意：我知道集合中的无重复项。这就是我还提到的原因，std::multiset因为它具有与 完全相同的行为，std::set但可以在允许将存储的数据作为相等元素进行比较的情况下使用。所以请不要评论单/多键问题。
优先级队列只允许您按排序顺序访问一个元素——即，您可以获得最高优先级的项目，当您删除它时，您可以获得下一个最高优先级，依此类推。优先级队列还允许重复元素，因此它更像是一个多重集而不是一个集。[编辑：正如@Tadeusz Kopec 所指出的，构建一个堆也与堆中的项目数成线性关系，其中构建一个集合是 O(N log N) 除非它是从已经排序的序列构建的（在这种情况下它也是线性的）。]
集合允许您按排序顺序进行完全访问，例如，您可以在集合中间的某个位置找到两个元素，然后按顺序从一个元素遍历到另一个元素。
std::priority_queue允许执行以下操作：
O(log n)O(1)O(log n)而std::set有更多的可能性：
O(log n)且常数大于instd::priority_queueO(log n)O(log n)( lower_bound)O(log n)iterator O(1)O(1)O(1)O(1)set/multiset 通常由二叉树支持。 http://en.wikipedia.org/wiki/Binary_tree
priority_queue 通常由堆支持。 http://en.wikipedia.org/wiki/Heap_(data_structure)
所以问题是什么时候应该使用二叉树而不是堆？
两种结构都布置在树中，但是关于祖先之间关系的规则是不同的。
我们将位置 P 称为父，L 为左孩子，R 为右孩子。
在二叉树中 L < P < R。
在堆中 P < L 和 P < R
因此，二叉树“横向”排序，而堆“向上”排序。
因此，如果我们将其视为一个三角形，那么在二叉树中 L、P、R 是完全排序的，而在堆中 L 和 R 之间的关系是未知的（只有它们与 P 的关系）。
这具有以下效果：
如果您有一个未排序的数组并想将其变成二叉树，则需要O(nlogn)时间。如果你想把它变成一个堆只需要O(n)时间，（因为它只是比较找到极端元素）
如果您只需要极端元素（某些比较函数的最低或最高），堆会更有效。堆只进行确定极端元素所需的比较（懒惰地）。
二叉树执行对整个集合排序所需的比较，并始终保持整个集合排序。
堆具有最低元素的恒定时间查找（peek），二叉树具有最低元素的对数时间查找。
由于
std::priority_queue和std::set(andstd::multiset) 都是存储元素并允许您以有序方式访问它们的数据容器，并且具有相同的插入复杂性O(log n)，因此使用一个比另一个有什么优势（或者，什么样的情况需要一个还是其他？）？
即使两个容器的插入和擦除操作具有相同的复杂度O(log n)，这些操作 forstd::set比 for 慢std::priority_queue。那是因为std::set做了很多内存分配。的每个元素std::set都存储在自己的分配中。std::priority_queue（默认使用底层std::vector容器）使用单一分配来存储所有元素。另一方面std::priority_queue，对其元素使用许多交换操作，而std::set仅使用指针交换。因此，如果交换对于元素类型来说是非常慢的操作，那么使用std::set可能会更有效。此外，元素可能根本不可交换。
内存开销std::set也更大，因为它必须在其节点之间存储许多指针。