473,585 Members | 2,496 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

STL: find() and iteration on priority_queue

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
9 28555
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
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
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
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_q ueue<intint_pri ority_queue;

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

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

int main ( void ) {
int_priority_qu eue q;
q.push( 1 );
q.push( 2 );
q.push( 3 );
std::copy( q_begin( q ), q_end( q ),
std::ostream_it erator<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: <algorithmprovi des 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
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
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
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
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
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
2714
by: Tom | last post by:
Hi, I need some help with stl maps. I am using a std::map that is sorted in a very special way. Therefore I am using my own sort function. That works fine. But this is only half the problem. Additionally "map.find()" should use a different comparison function. My map is like: map < myString, Whatever>
30
2709
by: Przemo Drochomirecki | last post by:
Hi, The task was indeed simple. Read 2.000.000 words (average length = 9), sort them and write it to new file. I've made this in STL, and it was almost 17 times slower than my previous "clear-C-code". I used <vector>, <algorithm>, <iostream> and <algorithm>. Is STL really so slow? Thx in adv. Przemo
25
2250
by: rokia | last post by:
in a project, I use many,many stl such as stack,list,vctor etc. somewhere the vector's size is more than 2K. is this a efficient way?
3
4434
by: Prakash Bande | last post by:
Hi, I have bool operator == (xx* obj, const string st). I have declared it as friend of class xx. I am now able to do this: xx ox; string st; if (&ox == st) { } But, when I have a vector<xx*> and use stl find string xyz;
13
20121
by: zaineb | last post by:
Hi, This is a follow-up of sort of this thread: http://groups.google.com/group/comp.lang.c++/browse_thread/thread/de12af6539e0d645/662cab752779f1fa?lnk=st&q=c%2B%2B+vector+vs+map&rnum=1&hl=en#662cab752779f1fa I've been chewing on this problem for a while. When I came across the above thread, I figured that maybe other members have a better...
8
6163
by: olanglois | last post by:
Hi, I was asking myself to following question. What is better to erase an element from a STL map: calling (option #1) size_type erase(const key_type& k) or calling (option #2)
10
7518
by: Christian Chrismann | last post by:
Hi, I've a question on the STL find algorithm: My code: int main( void ) { vector< ClassA* myVector; ClassA *ptrElement1 = ...;
1
2721
by: vermarajeev | last post by:
Hi, EveryBody This question is really interesting one. My question is related to "STL Find Algorithm" Defination Direct from book Now my questions are
4
5520
by: Anonymous | last post by:
I ahve a vector of doubles taht I need to extract values from. I was just about to use the STL find() algo, but I have a couple of questions: first: can you specify the tolerance threshold to match on doubles? second: if yes, how may this be done (i.e. how many one specify the tolerance threshold for comparing doubles?)
0
7908
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...
0
7836
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...
0
8336
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
1
7950
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...
0
6606
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...
0
3863
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
1
2343
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
1
1447
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
0
1175
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...

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.