473,666 Members | 2,634 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

Printing priority_queue without emptying it?

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

Feb 15 '07 #1
6 11224
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();
}
Feb 15 '07 #2
"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
Feb 15 '07 #3
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

Feb 15 '07 #4
"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
Feb 15 '07 #5
<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.

Feb 15 '07 #6
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
Feb 15 '07 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
6347
by: Tino | last post by:
Hopefully a simple question: What is the best/safest/fastest way to clear/make empty a std::priority_queue? Thanks, Ryan
7
3119
by: Dave | last post by:
Hello all, I'm pondering why the default underlying container for std::priority_queue<> is std::vector<>. It would seem that inserts are liable to happen anywhere, which would make std::list<> a superior alternative. Why factors am I not considering here? Why in the general case would std::vector<> be best? Thanks, Dave
3
4463
by: Tino | last post by:
In using std::priority_queue, I'm concerned about the expense of memory allocation and copying as the priority_queue grows large. std::vector has reserve() to address this concern, though there doesn't seem to be anything like this for priority_queue. Also, I don't know anything about how priority_queue is implemented (specifically, MSVC++ 6.0), so maybe I don't have anything to worry about. Guidance, please? Regards, Ryan
3
4006
by: zl2k | last post by:
hi, all Here is what I want to do: to wrap my self defined class in a shared_ptr and then insert it into the priority_queue. The priority_queue should pump the least element of the self defined class first. To make it simple, here is the toy code. myClass.h ------------------------------------------ #ifndef MYCLASS_H #define MYCLASS_H
9
28624
by: Henning Hasemann | last post by:
I'm using a stl-priority queue and want - find out if a certain item is contained in the queue - to be able iterate over all items without having to pop() them, order does not matter. I couldnt find methods for these which suprises me as both should be easily solvable with access to the underlying vector. Did I just miss these methods? Can I somehow access the vector to get . begin() .end() and .find()?
18
5525
by: J.M. | last post by:
I would like to use a data structure (e.g. from the STL) that always allows me to retrieve the largest element. (I want to push in elements, and remove the largest, push in further elements, etc.) It seems a priority_queue from the STL would work fine. However at some point, I am finished (even though the queue is not empty) and want to throw away the rest of the elements. It seems, I have to do this using: while (!Q.empty()) Q.pop(); ...
8
4157
by: thomas | last post by:
priority_queue usually uses the greater<intpredicate function. But as you know, we don't always use priority_queue<int>. Actually we may need the "priority_queue<pair<int,int>, vector<pair<int,int, cmphp;" thing. My question is how should I write the "cmp" function? I tried this one:
24
2560
by: Joe, G.I. | last post by:
Can anyone help me w/ a priority_queue. I'm generating MyEvent classes and I put them on a priority_queue, but I don't know how to get them in priority. The priority is the event w/ the smallest timestamp. // just a wrapper around priority_queue pq = new MyPriorityQueue(); // I generate 10 events w/ a random timestamp for (int i = 0; i < 10; i++) { MyEvent *event = new MyEvent();
5
3523
card
by: card | last post by:
I was wondering if anyone has a definitive answer on whether the STL priority_queue is dynamic? What I mean by this is best illustrated by a simple example. Suppose I have a priority queue of class called Position with a comparator class called PositionCompare as follows: priority_queue<Position, vector<Position>, PositionCompare> _pQ; Now, I go along and keep inserting Position objects into _pQ. These Position objects are really...
0
8863
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. Here is my compilation command: g++-12 -std=c++20 -Wnarrowing bit_field.cpp Here is the code in...
1
8549
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
0
8636
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
7378
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
1
6189
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms. Adolph will...
0
4358
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
2765
by: 6302768590 | last post by:
Hai team i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
2
2005
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
2
1763
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.