Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > Printing priority_queue without emptying it?

Reply
Thread Tools

Printing priority_queue without emptying it?

 
 
Eric Lilja
Guest
Posts: n/a
 
      02-15-2007
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

 
Reply With Quote
 
 
 
 
Rolf Magnus
Guest
Posts: n/a
 
      02-15-2007
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();
> }


 
Reply With Quote
 
 
 
 
P.J. Plauger
Guest
Posts: n/a
 
      02-15-2007
"Rolf Magnus" <(E-Mail Removed)> wrote in message
news:er1pv0$r7q$02$(E-Mail Removed)-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


 
Reply With Quote
 
=?iso-8859-1?q?Erik_Wikstr=F6m?=
Guest
Posts: n/a
 
      02-15-2007
On Feb 15, 3:12 pm, "Eric Lilja" <(E-Mail Removed)> 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?
> 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:riority_queue(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

 
Reply With Quote
 
P.J. Plauger
Guest
Posts: n/a
 
      02-15-2007
"Erik Wikström" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) oups.com...

On Feb 15, 3:12 pm, "Eric Lilja" <(E-Mail Removed)> 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?
> 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:riority_queue(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


 
Reply With Quote
 
David O
Guest
Posts: n/a
 
      02-15-2007
<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.

 
Reply With Quote
 
=?ISO-8859-1?Q?Erik_Wikstr=F6m?=
Guest
Posts: n/a
 
      02-15-2007
On 2007-02-15 17:53, P.J. Plauger wrote:
> "Erik Wikström" <(E-Mail Removed)> wrote in message
> news:(E-Mail Removed) oups.com...
>
> On Feb 15, 3:12 pm, "Eric Lilja" <(E-Mail Removed)> 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?
>> 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:riority_queue(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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
emptying a priority_queue efficiently J.M. C++ 18 02-06-2007 11:23 PM
reserve with std::priority_queue Tino C++ 3 05-28-2004 09:14 PM
priority_queue<> underlying container Dave C++ 7 04-22-2004 05:17 PM
queue, deque, priority_queue newsock C++ 15 11-04-2003 02:26 PM
clearing a priority_queue Tino C++ 4 07-09-2003 10:05 PM



Advertisments