STL priority queue

Write here if you have problems with your C++ source code

Moderator: Board moderators

Post Reply
Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

STL priority queue

Post by Mohammad Mahmudur Rahman » Thu Dec 16, 2004 11:36 pm

suppose I have a structure as follwos -
[cpp]
struct test_
{
int id,val1,val2;
};
[/cpp]

Then a STL priority queue with type test_ is created. Now if I want to set val1 as the key of the priority queue, I guess I need to write my own comparison function overriding the default COMP. Now can someone please give me an example of such a custom compare function & how the priority_queue is to be declared then? Thanks in advance.
You should never take more than you give in the circle of life.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Fri Dec 17, 2004 2:09 am

No, you just have to add operator< to test_ class. For instance:
[cpp]struct test_{
int id, val1, val2;
bool operator<(const test_ &t)const{
if(val1 != t.val1)return (val1 < t.val1);
else return (val2 < t.val2);
}
}

int main(){
priority_queue<test_> q;
}

[/cpp]Note that priority_queue will return by default the biggest element when top() is called.
If you want to use a custom binary bool function object, then you should do it this way:
[cpp]
priority_queue<test_, vector<test_>, cmp_object> q;
[/cpp]
For instance, to get the smallest element in queue, use greater<type_> object:
[cpp]
priority_queue<test_, vector<test_>, greater<test_> > q;
[/cpp]
In this case you have to define operator> in class test_.

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Fri Dec 17, 2004 2:12 am

[cpp]struct Foo
{
int key;
int value;

bool operator<(const Foo& foo) const
{
return key < foo.key;
}
};

priority_queue<Foo> myPriorityQueue;[/cpp]

There are many other ones to do it, but usually it is just best to override the less than operator, which is the default for any ordered STL container.

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman » Sat Dec 18, 2004 8:19 pm

Many thanks to both of you for help. I have finally been made it to work.
You should never take more than you give in the circle of life.

sqm
New poster
Posts: 3
Joined: Sun Jan 30, 2005 2:18 pm
Location: Bialystok, POLAND

Post by sqm » Mon Jan 31, 2005 3:57 pm

I wonder if someone could help me:
I have priority_queue of pointers to struct:

struct type{
int val;
};

priority_queue<type*>Q;

How can I overload operator?

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Tue Feb 01, 2005 5:17 pm

It's quite straightforward. You must provide a function or a function object that compares type*. An example:

Code: Select all

struct type{
        int val;
};

struct comparator{
        bool operator()(const type * s1, const type * s2){
                return (s1 -> val < s2 -> val);
        }
};
You use it this way:

Code: Select all

priority_queue<type*, vector<type*>, comparator> q;

Post Reply

Return to “C++”