How to iterate on boost::mutable_queue

I need a priority queue where I can increase or decrease the priority key. So boost::mutable_queue seemed perfect despite the lack of documentation.

The problem is that I need to iterate at some point over all the elements in the que开发者_运维百科ue. How can I do that?

Or is there an othe data structure that would work (preferably in boost)?

Queues are not for iteration. The whole point of a queue is that you can only ever look at the element at the front of the queue.

If you want to iterate then I suggest just using an std::set, which is ordered. When you want to modify an element, you'll have to remove it and reinsert it with the new key. You can get the highest priority element using mySet.begin() (that returns an iterator to it).

Ideally, you'll want to use a heap. STL provides functions for making heaps, and that's what the std::priority_queue uses. However, you can't modify keys in the heap because there is no interface for it.

If you manage the heap yourself then you can. However, you'll need to make use of the std::__adjust_heap function from <heap.h>, which is undocumented. You can read all about why this function is undocumented in this interview with Alexander Stepanov (inventor of the STL). It had to be "removed" because apparently the STL was too big, which is also what happened to hash maps from the original standard.

The problem is that I need to iterate at some point over all the elements in the queue. How can I do that?

The mutable_queue is just an adaptor. Pass in an appropriate underlying container. Further note that being an adaptor it modifies the interface that is available to you. By definition, queues typically do not allow iteration. If it did, there'd be no need to have this adaptor. See the SGI STL documentation on this restriction.

Or is there an othe data structure that would work (preferably in boost)?

You possibly need to use a different data structure for your purposes. An appropriate choice depends on how you want to store and access your data. You may want to take a look at the std::deque container. However, you will need to encode the priority as part of the contained objects' state.