473,320 Members | 1,991 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

emptying a priority_queue efficiently

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();

Other classes offer a resize() or a clear() and my guess that this is much
more efficient than using a while-loop. However, these functions are not
available for a priority_queue. Any ideas? Thanks in advance for any help.

Jan
Feb 6 '07 #1
18 5500
* J.M.:
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();

Other classes offer a resize() or a clear() and my guess that this is much
more efficient than using a while-loop. However, these functions are not
available for a priority_queue. Any ideas? Thanks in advance for any help.
template< typename T >
void makeEmpty( std::priority_queue<T>& q )
{
std::priority_queue<Tempty;
std::swap( q, empty );
}

Of course, you need to measure measure measure.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Feb 6 '07 #2
J.M. escreveu:
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();

Other classes offer a resize() or a clear() and my guess that this is much
more efficient than using a while-loop. However, these functions are not
available for a priority_queue. Any ideas? Thanks in advance for any help.
I might be missing something, but since you always wish to obtain the
largest element, I guess a set and an operator< for your element type
would give you what you need. You might use rbegin() or begin() to get
to the last element, depending on whether your operator< sorts elements
in ascending or descending order, respectivelly.

Regards,

--
Ney André de Mello Zunino
http://blog.zunino.eti.br/
Feb 6 '07 #3
J.M. <jm***************@gmx.dewrote:
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();

Other classes offer a resize() or a clear() and my guess that this is much
more efficient than using a while-loop. However, these functions are not
available for a priority_queue. Any ideas? Thanks in advance for any help.
Alf P. Steinbach gave you a good answer. Another idea is to use a
different container and call std::make_heap() on it, but consistently
maintaining the heap property may be less efficient than just using the
priority queue.

--
Marcus Kwok
Replace 'invalid' with 'net' to reply
Feb 6 '07 #4
Marcus Kwok <ri******@gehennom.invalidwrote:
J.M. <jm***************@gmx.dewrote:
>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();

Other classes offer a resize() or a clear() and my guess that this is much
more efficient than using a while-loop. However, these functions are not
available for a priority_queue. Any ideas? Thanks in advance for any help.

Alf P. Steinbach gave you a good answer. Another idea is to use a
different container and call std::make_heap() on it, but consistently
maintaining the heap property may be less efficient than just using the
priority queue.
After more investigation, <algorithmalso offers std::push_heap() and
std::pop_heap() in addition to std::make_heap(), so maintaining the heap
property may not be as big of a hit as I thought. Of course, you will
need to measure for yourself if the performance is acceptable.

--
Marcus Kwok
Replace 'invalid' with 'net' to reply
Feb 6 '07 #5
J.M. wrote:
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();

Other classes offer a resize() or a clear() and my guess that this is much
more efficient than using a while-loop. However, these functions are not
available for a priority_queue. Any ideas? Thanks in advance for any help.

Jan
Besides previously given answers... you could design things so that the
priority_queue goes out of scope when you're done with it or, if that's
not possible, dynamically allocate it and attach it to a smart pointer
which you can manually delete as soon as convenient. (Implicit in this
is also the option to simply do nothing and wait for the queue to fall
out of scope, but I gather that this is not sufficient for you.)
Feb 6 '07 #6
Mark P schrieb:
J.M. wrote:
>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();

Other classes offer a resize() or a clear() and my guess that this is
much more efficient than using a while-loop. However, these functions are
not available for a priority_queue. Any ideas? Thanks in advance for any
help.

Jan

Besides previously given answers... you could design things so that the
priority_queue goes out of scope when you're done with it or, if that's
not possible,
Not possible, it is part of another class, and I want to refill it starting
with an empty queue.,,
dynamically allocate it and attach it to a smart pointer
which you can manually delete as soon as convenient.
Ok, that would work of course, I was just hoping that there was something
more elegant and in "spirit" with the STL of just clearing a container. I
think Alf's solution is easiest and seems to reduce the time quite a bit.
(It only requires me changing one line of code ;-)))

Thanks,

Jan
(Implicit in this
is also the option to simply do nothing and wait for the queue to fall
out of scope, but I gather that this is not sufficient for you.)
Feb 6 '07 #7
Marcus Kwok schrieb:
Marcus Kwok <ri******@gehennom.invalidwrote:
>J.M. <jm***************@gmx.dewrote:
>>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();

Other classes offer a resize() or a clear() and my guess that this is
much more efficient than using a while-loop. However, these functions
are not available for a priority_queue. Any ideas? Thanks in advance for
any help.

Alf P. Steinbach gave you a good answer. Another idea is to use a
different container and call std::make_heap() on it, but consistently
maintaining the heap property may be less efficient than just using the
priority queue.

After more investigation, <algorithmalso offers std::push_heap() and
std::pop_heap() in addition to std::make_heap(), so maintaining the heap
property may not be as big of a hit as I thought. Of course, you will
need to measure for yourself if the performance is acceptable.
Well, I suppose all of that is feasible, but I was looking for a "quick fix"
and I think Alf's suggestion works best in that regard.

Thx

Jan
Feb 6 '07 #8
Alf P. Steinbach schrieb:
* J.M.:
>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();

Other classes offer a resize() or a clear() and my guess that this is
much more efficient than using a while-loop. However, these functions are
not available for a priority_queue. Any ideas? Thanks in advance for any
help.

template< typename T >
void makeEmpty( std::priority_queue<T>& q )
{
std::priority_queue<Tempty;
std::swap( q, empty );
}
Seems to work quite well. Thx.

Jan
>
Of course, you need to measure measure measure.
Feb 6 '07 #9
J.M. schrieb:
Alf P. Steinbach schrieb:
>* J.M.:
>>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();

Other classes offer a resize() or a clear() and my guess that this is
much more efficient than using a while-loop. However, these functions
are not available for a priority_queue. Any ideas? Thanks in advance for
any help.

template< typename T >
void makeEmpty( std::priority_queue<T>& q )
{
std::priority_queue<Tempty;
std::swap( q, empty );
}

Seems to work quite well. Thx.

Jan
Addendum:

It seems the following is even faster:

template< typename T >
void makeEmpty( std::priority_queue<T>& q )
{
std::priority_queue<Tempty;
q = empty;
}
>>
Of course, you need to measure measure measure.
Feb 6 '07 #10
J.M. wrote:
[..]
It seems the following is even faster:

template< typename T >
void makeEmpty( std::priority_queue<T>& q )
{
std::priority_queue<Tempty;
q = empty;
}
Or, shorter:

q = std::priority_queue<T>();

:-)

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Feb 6 '07 #11
"Alf P. Steinbach" <al***@start.nowrote in message
news:52*************@mid.individual.net...
template< typename T >
void makeEmpty( std::priority_queue<T>& q )
{
std::priority_queue<Tempty;
std::swap( q, empty );
}
Perhaps even easier:

template<typename T>
void makeEmpty (std::priority_queue<T>& q)
{
std::priority_queue<T>().swap(q);
}

Feb 6 '07 #12
Andrew Koenig wrote:
"Alf P. Steinbach" <al***@start.nowrote in message
news:52*************@mid.individual.net...
> template< typename T >
void makeEmpty( std::priority_queue<T>& q )
{
std::priority_queue<Tempty;
std::swap( q, empty );
}

Perhaps even easier:

template<typename T>
void makeEmpty (std::priority_queue<T>& q)
{
std::priority_queue<T>().swap(q);
}
I can't seem to locate the 'swap' member in 'std::priority_queue'
adapter...

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Feb 6 '07 #13
* Andrew Koenig:
"Alf P. Steinbach" <al***@start.nowrote in message
news:52*************@mid.individual.net...
> template< typename T >
void makeEmpty( std::priority_queue<T>& q )
{
std::priority_queue<Tempty;
std::swap( q, empty );
}

Perhaps even easier:

template<typename T>
void makeEmpty (std::priority_queue<T>& q)
{
std::priority_queue<T>().swap(q);
}
Checking... C++98, nope; C++2003, nope; November 2006 draft, nope.

But, shouldn't there be a DR about that?

Checking... Active library issues as of 12th january 2007[1], nope.
Cheers,

- Alf
Notes:
[1] Could someone please teach how to write dates in English?

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Feb 6 '07 #14
Alf P. Steinbach wrote:
[..]
Notes:
[1] Could someone please teach how to write dates in English?
Do you mean like this: http://en.wikipedia.org/wiki/Date_format

V
--
Please remove capital 'A's when replying by e-mail
I do not respond to top-posted replies, please don't ask
Feb 6 '07 #15
* Victor Bazarov:
Alf P. Steinbach wrote:
>[..]
Notes:
[1] Could someone please teach how to write dates in English?

Do you mean like this: http://en.wikipedia.org/wiki/Date_format
Ah, thank you very much!

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Feb 6 '07 #16
"Alf P. Steinbach" <al***@start.nowrote in message
news:52*************@mid.individual.net...
Checking... C++98, nope; C++2003, nope; November 2006 draft, nope.
Oh, foo; you're right.

But in that case you really don't want to use swap at all, because executing

std::priority_queue<Tempty;
std::swap( q, empty );

effectively does this:

std::priority_queue<Tempty;
{
std::priority_queue<Tfoo = q;
q = empty;
empty = foo;
}

which results in copying all of the elements of q before destroying them.
So you'd be better off with

q = std::priority_queue<T>();

If you can't do that, you can't use swap either :-)
Feb 6 '07 #17
* Andrew Koenig:
"Alf P. Steinbach" <al***@start.nowrote in message
news:52*************@mid.individual.net...
>Checking... C++98, nope; C++2003, nope; November 2006 draft, nope.

Oh, foo; you're right.

But in that case you really don't want to use swap at all, because executing

std::priority_queue<Tempty;
std::swap( q, empty );

effectively does this:

std::priority_queue<Tempty;
{
std::priority_queue<Tfoo = q;
q = empty;
empty = foo;
}

which results in copying all of the elements of q before destroying them.
So you'd be better off with

q = std::priority_queue<T>();

If you can't do that, you can't use swap either :-)
Well, the idea was that an implementation can provide a specialized
version of swap, and for an optimization, it doesn't matter how less
than ideally portable that is: one must measure in each environment.

After all, I thought, if a given implementation doesn't provide such a
swap specialization[1], then the client code programmer could (the trick
then being to provide it only for an implementation that doesn't) --
assuming that the prohibition against adding function overloads to
namespace std was just an oversight, not the commitee's Real Intention:
template< typename T, class Container = std::vector<T
struct AccessContainer_: std::priority_queue<T>
{
static Container& of( std::priority_queue<T>& q )
{
return static_cast<AccessContainer_&>( q ).c;
}
};

namespace std
{
template< typename T, class Container >
void swap(
std::priority_queue<T, Container>& a,
std::priority_queue<T, Container>& b
)
{
typedef AccessContainer_<T, ContainerAccessContainer;
std::swap( AccessContainer::of( a ), AccessContainer::of( b ) );
}
}

template< typename T, class Container >
void makeEmpty( std::priority_queue<T, Container>& q )
{
std::priority_queue<T, Containerempty;
std::swap( q, empty );
}
However, while this compiles fine with g++ 3.4.4 and Comeau Online
4.3.8, it fails with Visual C++ 7.1, which somehow thinks the call to
std::swap is ambigious.

I checked the source code of its library and the version it calls
without that overload, is the generic non-specialized one.

Any hint welcome...
Notes:
[1] Technically it's a function overload, not a specialization.

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
Feb 6 '07 #18
In article <52*************@mid.individual.net>,
"Alf P. Steinbach" <al***@start.nowrote:
* Andrew Koenig:
"Alf P. Steinbach" <al***@start.nowrote in message
news:52*************@mid.individual.net...
template< typename T >
void makeEmpty( std::priority_queue<T>& q )
{
std::priority_queue<Tempty;
std::swap( q, empty );
}
Perhaps even easier:

template<typename T>
void makeEmpty (std::priority_queue<T>& q)
{
std::priority_queue<T>().swap(q);
}

Checking... C++98, nope; C++2003, nope; November 2006 draft, nope.

But, shouldn't there be a DR about that?

Checking... Active library issues as of 12th january 2007[1], nope.
Perhaps you should submit one. :-)

-Howard
Feb 6 '07 #19

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

Similar topics

4
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
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<>...
3
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...
3
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...
9
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...
6
by: Eric Lilja | last post by:
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...
8
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>,...
24
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...
5
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...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....

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.