Priority_queue, iterator and ordering

Question

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

Does the following pop() provide that removing the top item follows the FIFO order in which the first inserted item is deleted first?

Another question: how can I find an item and remove it from the priority queue? (brief examples are given)

Answer 1

I do not think there is such a guarantee. According to sgi docs , it depends on the underlying data structure.

I think most common implementations use a bunch. Clicking and popping up any item on the heap simply updates the items in it so that there is no node where its children are larger than the parent (for maximum heap). In the case when both children have the same priority, and one of them should take the place of the parent, there is no difference in choosing which node should promote. Thus, for the implementation you need to select the left or right node.

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

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

Answer 2

How can I find an item and remove it from the priority queue? (brief examples are given)

You don’t “find” elements inside priority queues, as is the case with cards or sets ... rather, it is a queue, and the queue's behavior is to delete an element in front of the queue and click new elements on the back of the queue. Access to elements in the middle of the queue diverges from the expected behavior (and if you change this object, this can seriously affect the expected behavior pattern). In the case of a priority queue, items are sorted, so the first item in the queue is the item with the highest priority or, if all items have the same priority, it returns your first question, which is "no", this will not be guaranteed in FIFO order, since many implementations use heap-sorting, and the results of the sorting will be ambiguous for objects with equal priority, since the heap is a linear representation of the binary tree (i.e. for two equal child objects it becomes usmyslennym choice between two subsidiaries of the root elements to be selected as the new root node by removing the root node from the queue during the pop() ) ... in other words will be grouped together with the same priority, but the order that they jumped out of the line can be out of order FIFO. You can see a quick example of this action: http://ideone.com/DjSDi

Answer 3

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

This will give you more options. (including the kind of operations you are describing). However, you have to implement the logic.

In general, standard container adapters (stack, priority_queue) are restrictive in their open set of operations.

Answer 4

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

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

2- you cannot access the item at the top of the priority queue. you can use only:

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

see here for a more detailed description