By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,925 Members | 1,129 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 454,925 IT Pros & Developers. It's quick & easy.

STL: find() and iteration on priority_queue

P: n/a
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()?

TIA
Henning
Jul 12 '06 #1
Share this Question
Share on Google+
9 Replies


P: n/a
Henning Hasemann wrote:
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.
Well, they are not operations that are supposed to be done with a queue.
There is not much point in making a queue that offers random access. It
just wouldn't qualify as queue anymore.
Did I just miss these methods? Can I somehow access the vector to get .
begin() .end() and .find()?
If you want the functionality of a vector, just use a vector.

Jul 12 '06 #2

P: n/a
Rolf Magnus wrote:
Henning Hasemann wrote:
>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.

Well, they are not operations that are supposed to be done with a queue.
There is not much point in making a queue that offers random access. It
just wouldn't qualify as queue anymore.
I dont want random access. I just want a way to read all elements
without having to deconstruct the queue. (read-only acces is enough for me)
>Did I just miss these methods? Can I somehow access the vector to get .
begin() .end() and .find()?

If you want the functionality of a vector, just use a vector.
That comment was rather unhelpful.
I want the functionality of a priority_queue because I need fast access
to the "highest" element.
I also need to be able to find out if a certain element is contained.
Iterating isnt even necessary if I'd had only a contains()-method or
something.

To give you the whole picture I'm talking about a container for the
open-"list" used in the dijkstra algorithm and the 3 operations done
with it are inerting an element, getting and removing the element with
the highest value and testing if a certain element is contained.

Unfortunately the code is really time-critical and using a list and
insertion sort is simply to slow.

Any suggestions?

Jul 12 '06 #3

P: n/a
Did I just miss these methods? Can I somehow access the vector to get .
begin() .end() and .find()?
If you want the functionality of a vector, just use a vector.

That comment was rather unhelpful.
I want the functionality of a priority_queue because I need fast access
to the "highest" element.
I also need to be able to find out if a certain element is contained.
Iterating isnt even necessary if I'd had only a contains()-method or
something.
In that case, what's wrong with map or multimap? Seem to have all your
requirements?

Jul 12 '06 #4

P: n/a
Henning Hasemann wrote:
Rolf Magnus wrote:
>Henning Hasemann wrote:
>>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.

Well, they are not operations that are supposed to be done with a queue.
There is not much point in making a queue that offers random access. It
just wouldn't qualify as queue anymore.

I dont want random access. I just want a way to read all elements
without having to deconstruct the queue. (read-only acces is enough for
me)
>>Did I just miss these methods? Can I somehow access the vector to get .
begin() .end() and .find()?

If you want the functionality of a vector, just use a vector.

That comment was rather unhelpful.
I want the functionality of a priority_queue because I need fast access
to the "highest" element.
I also need to be able to find out if a certain element is contained.
Iterating isnt even necessary if I'd had only a contains()-method or
something.

To give you the whole picture I'm talking about a container for the
open-"list" used in the dijkstra algorithm and the 3 operations done
with it are inerting an element, getting and removing the element with
the highest value and testing if a certain element is contained.

Unfortunately the code is really time-critical and using a list and
insertion sort is simply to slow.

Any suggestions?
A) You can use a BAD HACK (tm):
#include <queue>
#include <iostream>
#include <algorithm>
#include <iterator>
typedef std::priority_queue<intint_priority_queue;

template < typename T >
T const * q_begin ( std::priority_queue<Tconst & q ) {
return ( &( q.top() ) );
}

template < typename T >
T const * q_end ( std::priority_queue<Tconst & q ) {
return ( &( q.top() ) + q.size() );
}

int main ( void ) {
int_priority_queue q;
q.push( 1 );
q.push( 2 );
q.push( 3 );
std::copy( q_begin( q ), q_end( q ),
std::ostream_iterator<int>( std::cout, " " ) );
std::cout << '\n';
}
Note that this is based on two assumptions:

a) The underlying sequence container is contiguous. This is guaranteed by
the standard for std::vector.

b) The priority_queue is implemented so that the top() element comes first
in the sequence. This is the way, heaps are organized. However, the
standard does not guarantee that priority_queue<Tworks this way. YMMV.

B) You can use a vector directly: <algorithmprovides push_heap() and
pop_heap() for any range.
C) For further speed-up, you may consider making use of the heap-structure
when deciding whether a certain element is contained in the queue: it
should take log( size() ) comparisons.
Best

Kai-Uwe Bux
Jul 12 '06 #5

P: n/a
Henning Hasemann wrote:
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()?
You didn't miss them because they're not provided *on purpose*. See
http://www.sgi.com/tech/stl/priority_queue.html (scroll down to note 2)
for reasons why and what you can do about it.

Kristo

Jul 12 '06 #6

P: n/a
Henning Hasemann wrote:
To give you the whole picture I'm talking about a container for the
open-"list" used in the dijkstra algorithm and the 3 operations done
with it are inerting an element, getting and removing the element with
the highest value and testing if a certain element is contained.
Unfortunately the code is really time-critical and using a list and
insertion sort is simply to slow.
Any suggestions?
Other than write some code that does what you want?

--
Salu2
Jul 12 '06 #7

P: n/a
Henning Hasemann wrote:
Rolf Magnus wrote:
>Henning Hasemann wrote:
>>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.
Well, they are not operations that are supposed to be done with a queue.
There is not much point in making a queue that offers random access. It
just wouldn't qualify as queue anymore.

I dont want random access. I just want a way to read all elements
without having to deconstruct the queue. (read-only acces is enough for me)
>>Did I just miss these methods? Can I somehow access the vector to get .
begin() .end() and .find()?
If you want the functionality of a vector, just use a vector.

That comment was rather unhelpful.
I want the functionality of a priority_queue because I need fast access
to the "highest" element.
I also need to be able to find out if a certain element is contained.
Iterating isnt even necessary if I'd had only a contains()-method or
something.

To give you the whole picture I'm talking about a container for the
open-"list" used in the dijkstra algorithm and the 3 operations done
with it are inerting an element, getting and removing the element with
the highest value and testing if a certain element is contained.

Unfortunately the code is really time-critical and using a list and
insertion sort is simply to slow.
Use private inheritance to inherit from priority_queue(). The
underlying container is a protected member. Make sure you make the
inherited functions visible with using declarations.

Jul 12 '06 #8

P: n/a
red floyd wrote:
Use private inheritance to inherit from priority_queue(). The
underlying container is a protected member. Make sure you make the
inherited functions visible with using declarations.
I don't have a copy of the standard here, but I suspect that's an
implementation detail. I wouldn't rely on the underlying container
being protected if you're trying to write code that is portable across
compilers.

Jul 13 '06 #9

P: n/a
Kristo wrote:
red floyd wrote:
>Use private inheritance to inherit from priority_queue(). The
underlying container is a protected member. Make sure you make the
inherited functions visible with using declarations.

I don't have a copy of the standard here, but I suspect that's an
implementation detail. I wouldn't rely on the underlying container
being protected if you're trying to write code that is portable across
compilers.
Actually, I got that info from Josuttis. Also, I just checked -- the
Standard 23.2.3.2/1 shows the underlying container and comparison
functions as protected members. So it's not an implementation detail.
Jul 13 '06 #10

This discussion thread is closed

Replies have been disabled for this discussion.