Printing priority_queue without emptying it?

[Eric Lilja]

Hello, I have a the following priority_queue: priority_queue< pair<int,
string pq;

AFAICT, priority_queues doesn't support iterators. My question: is
there a way to print its contents without emptying it?
Right now I'm using the following code:

while (!pq.empty())
{
cout << setw(3) << pq.top().first << ": " << pq.top().second <<
endl;
pq.pop();
}

-Eric

[Rolf Magnus]

Eric Lilja wrote:

Hello, I have a the following priority_queue: priority_queue< pair<int,
string pq;

AFAICT, priority_queues doesn't support iterators. My question: is
there a way to print its contents without emptying it?

You could create a copy and empty that.

Right now I'm using the following code:

while (!pq.empty())
{
cout << setw(3) << pq.top().first << ": " << pq.top().second <<
endl;
pq.pop();
}

[P.J. Plauger]

"Rolf Magnus" <ra******@t-online.dewrote in message
news:er******** *****@news.t-online.com...

Eric Lilja wrote:

>Hello, I have a the following priority_queue: priority_queue< pair<int,
string pq;

AFAICT, priority_queues doesn't support iterators. My question: is
there a way to print its contents without emptying it?

You could create a copy and empty that.

>Right now I'm using the following code:

while (!pq.empty())
{
cout << setw(3) << pq.top().first << ": " << pq.top().second <<
endl;
pq.pop();
}

You can derive a class from priority_queue that accesses its protected
member c, which is the underlying container. Note that it is organized
as a heap, if the order of presentation matters to you.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

[=?iso-8859-1?q?Erik_Wikstr=F6m?=]

On Feb 15, 3:12 pm, "Eric Lilja" <mindcoo...@gma il.comwrote:

Hello, I have a the following priority_queue: priority_queue< pair<int,
string pq;

AFAICT, priority_queues doesn't support iterators. My question: is
there a way to print its contents without emptying it?
Right now I'm using the following code:

while (!pq.empty())
{
cout << setw(3) << pq.top().first << ": " << pq.top().second <<
endl;
pq.pop();

}

I also ran into this some time ago and decided that it was better for
me to use a normal vector and sort it before starting to retrieve
elements. This was actually faster than inserting the elements into
the priority_queue and then retrieving them since insertion was O(1)
for the vector. This option might not be available for you if you do
not first insert all the elements and later only extracts.

What you can do is to use the the fact that you can specify the
container in the constructor, something like:

std::vector base;
std::priority_q ueue(std::less( ), base) queue;

Then push()/pop() from the queue but iterate over base. Be aware that
if you make any changes to base you should run std::make_heap( ) on it.

You might have guessed by now that priority_queue is just a wrapper
that uses make_heap(), pop_heap() and push_heap() on a underlying
container, which is why it's called an adaptor and not a container.

--
Erik Wikström

[P.J. Plauger]

"Erik Wikström" <er****@student .chalmers.sewro te in message
news:11******** **************@ v33g2000cwv.goo glegroups.com.. .

On Feb 15, 3:12 pm, "Eric Lilja" <mindcoo...@gma il.comwrote:

Hello, I have a the following priority_queue: priority_queue< pair<int,
string pq;

AFAICT, priority_queues doesn't support iterators. My question: is
there a way to print its contents without emptying it?
Right now I'm using the following code:

while (!pq.empty())
{
cout << setw(3) << pq.top().first << ": " << pq.top().second <<
endl;
pq.pop();

}

I also ran into this some time ago and decided that it was better for
me to use a normal vector and sort it before starting to retrieve
elements. This was actually faster than inserting the elements into
the priority_queue and then retrieving them since insertion was O(1)
for the vector. This option might not be available for you if you do
not first insert all the elements and later only extracts.

What you can do is to use the the fact that you can specify the
container in the constructor, something like:

std::vector base;
std::priority_q ueue(std::less( ), base) queue;

Then push()/pop() from the queue but iterate over base. Be aware that
if you make any changes to base you should run std::make_heap( ) on it.

You might have guessed by now that priority_queue is just a wrapper
that uses make_heap(), pop_heap() and push_heap() on a underlying
container, which is why it's called an adaptor and not a container.

[pjp] Nope. This constructor uses base to *initialize* the protected
member c, which is of type container_type, not container_type& . So
any changes to the priority_queue are *not* reflected in base.

P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com

[David O]

<snip>

You can derive a class from priority_queue that accesses its protected
member c, which is the underlying container. Note that it is organized
as a heap, if the order of presentation matters to you.

P.J. Plauger
Dinkumware, Ltd.http://www.dinkumware.com

Deriving from priority_queue is necessary to resolve other
limitations. I once needed to implemented a timeout queue for a
relatively large number of protocol sessions, which seemed a natural
mapping to a priority_queue of (smart pointers to) session objects
inversely sorted by their time value, so the soonest to elapse was
always highest priority.

Adding sessions is naturally done by push(), and using the time value
of the top() element as parameter of the main loop select() prevents
busy waiting (priming the queue with a sentinel object set to expire
at the end of time simplifies a lot of details). Unfortunately, this
doesn't allow for the times to change (so as to reset a timeout) or to
remove an element (for an expired session), so I added functions to
the derived class to do this - fortunately, the algorithms to
rebalance the heap (e.g. __push_heap(), __adjust_heap() ) are probably
already in your standard library implementation, but require their
names and interfaces are library dependant.

Best Regards,

David O.

[=?ISO-8859-1?Q?Erik_Wikstr=F6m?=]

On 2007-02-15 17:53, P.J. Plauger wrote:

"Erik Wikström" <er****@student .chalmers.sewro te in message
news:11******** **************@ v33g2000cwv.goo glegroups.com.. .

On Feb 15, 3:12 pm, "Eric Lilja" <mindcoo...@gma il.comwrote:

>Hello, I have a the following priority_queue: priority_queue< pair<int,
string pq;

AFAICT, priority_queues doesn't support iterators. My question: is
there a way to print its contents without emptying it?
Right now I'm using the following code:

while (!pq.empty())
{
cout << setw(3) << pq.top().first << ": " << pq.top().second <<
endl;
pq.pop();

}

I also ran into this some time ago and decided that it was better for
me to use a normal vector and sort it before starting to retrieve
elements. This was actually faster than inserting the elements into
the priority_queue and then retrieving them since insertion was O(1)
for the vector. This option might not be available for you if you do
not first insert all the elements and later only extracts.

What you can do is to use the the fact that you can specify the
container in the constructor, something like:

std::vector base;
std::priority_q ueue(std::less( ), base) queue;

Then push()/pop() from the queue but iterate over base. Be aware that
if you make any changes to base you should run std::make_heap( ) on it.

You might have guessed by now that priority_queue is just a wrapper
that uses make_heap(), pop_heap() and push_heap() on a underlying
container, which is why it's called an adaptor and not a container.

[pjp] Nope. This constructor uses base to *initialize* the protected
member c, which is of type container_type, not container_type& . So
any changes to the priority_queue are *not* reflected in base.

Oh, right you are. Missread the standard there, will be more carful the
next time.

--
Erik Wikström