473,703 Members | 2,772 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 11241
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
6350
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
3120
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
4470
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
4010
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
28690
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
5528
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
4159
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
2563
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
3525
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
8743
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
8659
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
0
9239
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
8993
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,...
1
6585
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
5920
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
4674
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
2
2422
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
2054
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.