priority_queue, iterator and ordering

Consider a std::priority_queue where N elements have the same priority. Now consider some pop()s and push()s of elements with any priority, so that the resulting queue consists of all those N elements mentioned above plus M new elements, where all the N+M elements have the same priority.

Does a following pop() guarantee that the removal of the top element follows a FIFO order in which the first inserted element is r开发者_如何转开发emoved first?

Another question is how can I find an element and remove it from a priority queue? (a short examples is appreciated)

---

I don't think there is any such guarantee. According to to sgi's docs, it depends on the underlying data structure.

I think most common implementations use a heap. Pushing and popping any item on a heap simply updates the elements in it in such a way that there is no node where its children are larger than the parent (for max heap). In the case where both children have the same priority and one of them must take the place of the parent, there is no distinction made on choosing which node to promote. So it is entirely up to the implementation to pick the left or the right node.

If you really need to have the nodes in FIFO order if all priorities are equal, pass in a comparison function that first orders by priority and breaks ties by using a value stored in the object that holds the number of objects pushed into the priority_queue before it.

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

---

how can I find an element and remove it from a priority queue? (a short examples is appreciated)

You don't "find" elements inside of priority queues like you would with maps or sets ... rather it's a queue, and the behavior of a queue is to remove the element at the front of the queue, and push new elements on the back of the queue. Accessing elements in the middle of the queue diverges from that expected behavior (and if you modified that object, would/could seriously break the expected behavior pattern). In the case of a priority queue, the elements are sorted, so the first element off the queue is the element with the highest priority, or, if all the elements have the same priority, it leads back to your first question, which is "no", it will not be guaranteed to be in FIFO order, since many implementations use a heap-sort, and the results of the sort will be ambiguous for objects of equal priority since a heap is a linear-representation of a binary tree (i.e., for two equal child objects, there becomes an ambiguous choice between the two children of the root to choose as the new root node when removing the root node from the queue during a pop()) ... in other words objects of the same priority will be grouped together, but the order they are popped from the queue may not be in FIFO order. You can see a quick example of that in-action here: http://ideone.com/DjSDi

---

You could/should simulate a (double ended) priority queue using a standard list (or vector) and make_heap, push_heap, pop_heap.

This would get you more options. (including the kind of operations that you describe). You'd have to implement the logic yourself, though.

In general, the standard container adaptors (stack, priority_queue) are restrictive in their exposed set of operations.

---

1- if you want to enforce the FIFO ordering when elements have the same priority add a field t to your class (it's says when element is added to the priority queue) and in operator< compare t if two elements had the same priority.

or you can use pair< T , int > when T is your element's type and set the int to t when t is an integer when you add something to your priority queue you -- it.

2- you can't access any element else top of your priority queue. you can use only:

constructor
top()
pop()
push()
size()
empty()

see here for more description