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)

Answer 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.

Answer 2

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