I'm new to STL containers (and C++ in general) so thought I would reach out to the community for help. I basically want to have a priority_queue that supports constant iteration. Now, it seems that std::priority_queue doesn't support iteration, so I'm going to have to use something else, but I'm not sure exactly what. Requirements: Maintains order on insertion (like a priority queue) Pop from top of list Get const access to each element of the list (don't care about the order in the queue for this stage) One option would be to keep a priority_queue and separately have an unordered_set of references, but I'd rather not have two containers floating around. I could also use a deque and search through for the right insertion position, but I'd rather have the container manage the sorting for me if possible (and constant-time insertion would be nicer than linear-time). Any suggestions?

Reputation: 436

STL iterable container like priority_queue

I'm new to STL containers (and C++ in general) so thought I would reach out to the community for help. I basically want to have a priority_queue that supports constant iteration. Now, it seems that std::priority_queue doesn't support iteration, so I'm going to have to use something else, but I'm not sure exactly what.

Requirements:

Maintains order on insertion (like a priority queue)
Pop from top of list
Get const access to each element of the list (don't care about the order in the queue for this stage)

One option would be to keep a priority_queue and separately have an unordered_set of references, but I'd rather not have two containers floating around. I could also use a deque and search through for the right insertion position, but I'd rather have the container manage the sorting for me if possible (and constant-time insertion would be nicer than linear-time). Any suggestions?

Upvotes: 0

Answers (4)

Boris

Reputation: 622

Have you observed heap (std::make_heap) ? It hasn't order inside of queue, but has priority "pop from top of list" which you need.

Upvotes: 1

Klaim

Reputation: 69682

Using a std::vector might be enough as others already pointed, but if you want already-ready implementation, maybe use Boost.Heap (which is a library with several priority queue containers): http://www.boost.org/doc/libs/1_53_0/doc/html/heap.html

Boost is a collection of libraries that basically complete the standard library (which is not really big). A lot of C++ developers have boost ready on their dev computer to use it when needed. Just be careful in your choices of libraries.

Upvotes: 2

juanchopanza

Reputation: 227418

There are two options that come to mind:

1) Implement your own iterable priority queue, using std::vector and the heap operation algorithms (see Heap Operations here).

2) derive (privately) from priority_queue. This gives you access to the underlying container via data member c. You can then expose iteration, random access, and other methods of interest in your public interface.

Upvotes: 3

Kim Strauss

Reputation: 329

You can use (ordered) set as a queue. set.begin() will be your top element, and you can pop it via erase(set.begin()).

Upvotes: 1

STL iterable container like priority_queue

Answers (4)

Related Questions