c++ - priority_queue、迭代器和排序

Question

考虑一个 std::priority_queue，其中 N 元素具有相同的优先级。现在考虑具有任意优先级的元素的一些 pop() 和 push()，因此生成的队列由所有这些 N 元素组成上面提到的加上M个新元素，其中所有的N+M元素都具有相同的优先级。

下面的 pop() 是否保证顶部元素的移除遵循 FIFO 顺序，即首先移除第一个插入的元素？

另一个问题是如何找到一个元素并将其从优先队列中移除？ (一个简短的例子表示赞赏)

Answer 1

我不认为有任何这样的保证。根据sgi's docs ，它取决于底层数据结构。

我认为大多数常见的实现都使用堆。推送和弹出堆上的任何项目只是更新其中的元素，使得没有节点的子节点大于父节点(对于最大堆)。在两个子节点具有相同优先级并且其中一个必须代替父节点的情况下，选择提升哪个节点没有区别。因此，选择左侧或右侧节点完全取决于实现。

如果在所有优先级都相等的情况下您确实需要让节点按 FIFO 顺序排列，请传入一个比较函数，该函数首先按优先级排序，并通过使用存储在对象中的值来打破平局，该值包含插入的对象数priority_queue 在它之前。

int cmp(my_object a, my_object b){
    if (a.priority!=b.priority) return a.priority<b.priority;
    else return a.index<b.index;
}