Can I access elements of a Priority Que using an iterator?

Question

Vectors and Linked Lists

Vectors are stored in memory serially, and therefore any element may be accessed using the operator[], just as in an array.

A linked list contains elements which may not be stored continuously in memory, and therefore a random element must be accessed by following pointers, using an iterator.

(You probably already knew this.)

Advantage of Priority Que

Recently I discovered the 'priority queue', which works kind of like a stack, but elements are push()-ed into the container, and this function places them in an order according to comparisons made with the operator<, I believe.

This suits me perfectly, as I am testing for events and placing them in the queue according to the time remaining until they occur. The queue automatically sorts them for me as I push() and pop() elements. (Popping does not affect the order.) I can write an operator< so this isn't a problem.

Issues I have not been able to resolve

There are three things which I need to be able to do with this event queue:

1:) Search the event queue for an item. I assume this can be done with an algorithm in the standard library? For example, 'find'? If not I can implement one myself, provided I can do point 2. (See below)

2:) Iterate over the queue. I think the default underlying container is std::vector... Is there a way to access random elements within the underlying vector? What if I choose to use std::deque instead? I need to do this to modify certain event parameters. (Events are placed in the queue.) As an example, I may need to process an event and then subtract a constant amount of time from each remaining event's 'time_to_event' parameter. I suspect this cannot be done due to this question.

3:) Remove an element from the queue. Sometimes when processing events, other events become invalidated, and therefore need to be removed.

Can points 1-3 be done? All the information I have on std::priority_queue has come from cplusplus.com, and so my default answer would be "no", there is no way to do any of these things. If I can't do all three things, then I guess I will have to write my own Priority Queue wrapper. (Oh boring)

Solution 1

No, you can't iterate over items in an std::priority_queue. All it supports is inserting items, and removing the highest priority item.

When you want more flexibility, you probably want to use std::make_heap to build the heap structure into your container, std::push_heap to add an item, and std::pop_heap to remove an item.

Since these are algorithms you apply to a container, you can still use the container's iterators as you see fit. Depending on how you modify the data in the heap, you may need to re-build the heap afterwards -- if you modify it in a way that the heap property no longer applies. You can test that with std::is_heap if you have any question.

Aside: many of us find http://www.cppreference.com more useful and accurate than the site you've linked.

Solution 2

Take a look at Boost.Heap. It looks like it addresses at least two of your issues (iteration and mutability).

Comments

[FreelanceConsultant]

Okay thanks Jerry, guess I had better start writing my own wrapper class then. (As I understand it this is how the priority queue is implemented anyway.

[WhozCraig]

@EdwardBird If you do that, the algorithms for heap management will likely make you're life a LOT easier. See the general algorithms section of the standard library, noting specifically the heap-operations.

[FreelanceConsultant]

What do you mean by mutability in this context?

[FreelanceConsultant]

@WhozCraig Yeah of course, no point implementing them all again is there?

[Ferruccio]

@EdwardBird - You can change the priority of an item. So, to remove an item from the list, you can change its priority to the max, forcing it to the front of the queue and pop it off.