emptying a priority_queue efficiently

[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.

Jan

 

[Alf P. Steinbach]

* 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:riority_queue<T>& q )
{
std:riority_queue<T> empty;
std::swap( q, empty );
}

Of course, you need to measure measure measure.

 

[=?ISO-8859-1?Q?Ney_Andr=E9_de_Mello_Zunino?=]

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,

 

[Marcus Kwok]

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]

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, <algorithm> also offers std:ush_heap() and
std:op_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.

 

[Mark P]

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.)

 

[J.M.]

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

 

[J.M.]

After more investigation, <algorithm> also offers std:ush_heap() and
std:op_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

 

[J.M.]

* J.M.:

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

Seems to work quite well. Thx.

Jan

 

[J.M.]

Seems to work quite well. Thx.

Jan

Addendum:

It seems the following is even faster:

template< typename T >
void makeEmpty( std:riority_queue<T>& q )
{
std:riority_queue<T> empty;
q = empty;
}

 

[Victor Bazarov]

[..]
It seems the following is even faster:

template< typename T >
void makeEmpty( std:riority_queue<T>& q )
{
std:riority_queue<T> empty;
q = empty;
}

Or, shorter:

q = std:riority_queue<T>();



V

 

[Andrew Koenig]

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

Perhaps even easier:

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

 

[Victor Bazarov]

Perhaps even easier:

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

I can't seem to locate the 'swap' member in 'std:riority_queue'
adapter...

V

 

[Alf P. Steinbach]

* Andrew Koenig:

Perhaps even easier:

template<typename T>
void makeEmpty (std:riority_queue<T>& q)
{
std:riority_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?

 

[Victor Bazarov]

[..]
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

 

[Alf P. Steinbach]

* Victor Bazarov:

[..]
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!

 

[Andrew Koenig]

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:riority_queue<T> empty;
std::swap( q, empty );

effectively does this:

std:riority_queue<T> empty;
{
std:riority_queue<T> foo = 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:riority_queue<T>();

If you can't do that, you can't use swap either

 

[Alf P. Steinbach]

* Andrew Koenig:

Oh, foo; you're right.

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

std:riority_queue<T> empty;
std::swap( q, empty );

effectively does this:

std:riority_queue<T> empty;
{
std:riority_queue<T> foo = 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:riority_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:riority_queue<T>
{
static Container& of( std:riority_queue<T>& q )
{
return static_cast<AccessContainer_&>( q ).c;
}
};

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

template< typename T, class Container >
void makeEmpty( std:riority_queue<T, Container>& q )
{
std:riority_queue<T, Container> empty;
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.

 

[Howard Hinnant]

* Andrew Koenig:

Perhaps even easier:

template<typename T>
void makeEmpty (std:riority_queue<T>& q)
{
std:riority_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