[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.c++

priority_queue predicate

thomas

10/3/2008 4:06:00 PM

priority_queue usually uses the greater<int> predicate function.

But as you know, we don't always use priority_queue<int>. Actually we
may need the "priority_queue<pair<int,int>, vector<pair<int,int> >,
cmp> hp;" thing.

My question is how should I write the "cmp" function?

I tried this one:

bool cmp(pair<int,int> &x, pair<int,int> &y){
return x.second < y.second;
}

but it doesn't work while it usually makes sense for "sort" predicate.

Any comments? Thanks in advance.
9 Answers

Pete Becker

10/3/2008 4:41:00 PM

0

On 2008-10-03 12:05:38 -0400, thomas <FreshThomas@gmail.com> said:

> priority_queue usually uses the greater<int> predicate function.
>
> But as you know, we don't always use priority_queue<int>. Actually we
> may need the "priority_queue<pair<int,int>, vector<pair<int,int> >,
> cmp> hp;" thing.
>
> My question is how should I write the "cmp" function?

It depends on what you want it to do.

>
> I tried this one:
>
> bool cmp(pair<int,int> &x, pair<int,int> &y){
> return x.second < y.second;
> }
>
> but it doesn't work while it usually makes sense for "sort" predicate.
>

It should work just fine, if you want your elements sorted by their
second field. If that's not what you want, then you need a different
comparison function.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

Pete Becker

10/3/2008 4:44:00 PM

0

On 2008-10-03 12:41:16 -0400, Pete Becker <pete@versatilecoding.com> said:

> On 2008-10-03 12:05:38 -0400, thomas <FreshThomas@gmail.com> said:
>
>> priority_queue usually uses the greater<int> predicate function.
>>
>> But as you know, we don't always use priority_queue<int>. Actually we
>> may need the "priority_queue<pair<int,int>, vector<pair<int,int> >,
>> cmp> hp;" thing.
>>
>> My question is how should I write the "cmp" function?
>
> It depends on what you want it to do.
>
>>
>> I tried this one:
>>
>> bool cmp(pair<int,int> &x, pair<int,int> &y){
>> return x.second < y.second;
>> }
>>
>> but it doesn't work while it usually makes sense for "sort" predicate.
>>
>
> It should work just fine, if you want your elements sorted by their
> second field. If that's not what you want, then you need a different
> comparison function.

However, it should probably take its arguments by const reference or by
value. But since you haven't posted real code, nor provided any details
about what "doesn't work" means, it's not possible to tell what, if
anything, is wrong.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

thomas

10/3/2008 5:32:00 PM

0

On Oct 4, 12:44 am, Pete Becker <p...@versatilecoding.com> wrote:
> On 2008-10-03 12:41:16 -0400, Pete Becker <p...@versatilecoding.com> said:
>
>
>
>
>
> > On 2008-10-03 12:05:38 -0400, thomas <FreshTho...@gmail.com> said:
>
> >> priority_queue usually uses the greater<int> predicate function.
>
> >> But as you know, we don't always use priority_queue<int>. Actually we
> >> may need the "priority_queue<pair<int,int>, vector<pair<int,int> >,
> >> cmp> hp;" thing.
>
> >> My question is how should I write the "cmp" function?
>
> > It depends on what you want it to do.
>
> >> I tried this one:
>
> >> bool cmp(pair<int,int> &x, pair<int,int> &y){
> >>     return x.second < y.second;
> >> }
>
> >> but it doesn't work while it usually makes sense for "sort" predicate.
>
> > It should work just fine, if you want your elements sorted by their
> > second field. If that's not what you want, then you need a different
> > comparison function.
>
> However, it should probably take its arguments by const reference or by
> value. But since you haven't posted real code, nor provided any details
> about what "doesn't work" means, it's not possible to tell what, if
> anything, is wrong.
>
> --
>   Pete
> Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
> Standard C++ Library Extensions: a Tutorial and Reference
> (www.petebecker.com/tr1book)- Hide quoted text -
>
> - Show quoted text -

-------code-----
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cmath>
#include<list>
#include<stack>
#include<queue>

using namespace std;

bool cmp(const pair<PII,int> &x, const pair<PII,int> &y){
return x.second < y.second;
}
priority_queue<pair<PII, int>, vector<pair<PII,int> >, cmp>
heap; //pair<pair<node I, node j>, weight>

int main(){

}
---------end---------

for simplicity, you can compile the code above.
I'm using vc8, and got the errors:
----------------------
------ Build started: Project: pku, Configuration: Debug Win32 ------
Compiling...
a.cpp
...\a.cpp(14) : error C2065: 'PII' : undeclared identifier
...\a.cpp(17) : error C3203: 'pair' : unspecialized class template
can't be used as a template argument for template parameter '_Ty',
expected a real type
...\a.cpp(17) : error C3203: 'pair' : unspecialized class template
can't be used as a template argument for template parameter '_Ty',
expected a real type
...\a.cpp(17) : error C2923: 'std::priority_queue' : 'cmp' is not a
valid template type argument for parameter '_Pr'
..\a.cpp(14) : see declaration of 'cmp'
...\a.cpp(17) : error C2133: 'heap' : unknown size
...\a.cpp(17) : error C2512: 'std::priority_queue' : no appropriate
default constructor available
------------------------

thomas

10/3/2008 5:34:00 PM

0

On Oct 4, 1:31 am, thomas <FreshTho...@gmail.com> wrote:
> On Oct 4, 12:44 am, Pete Becker <p...@versatilecoding.com> wrote:
>
>
>
>
>
> > On 2008-10-03 12:41:16 -0400, Pete Becker <p...@versatilecoding.com> said:
>
> > > On 2008-10-03 12:05:38 -0400, thomas <FreshTho...@gmail.com> said:
>
> > >> priority_queue usually uses the greater<int> predicate function.
>
> > >> But as you know, we don't always use priority_queue<int>. Actually we
> > >> may need the "priority_queue<pair<int,int>, vector<pair<int,int> >,
> > >> cmp> hp;" thing.
>
> > >> My question is how should I write the "cmp" function?
>
> > > It depends on what you want it to do.
>
> > >> I tried this one:
>
> > >> bool cmp(pair<int,int> &x, pair<int,int> &y){
> > >>     return x.second < y.second;
> > >> }
>
> > >> but it doesn't work while it usually makes sense for "sort" predicate.
>
> > > It should work just fine, if you want your elements sorted by their
> > > second field. If that's not what you want, then you need a different
> > > comparison function.
>
> > However, it should probably take its arguments by const reference or by
> > value. But since you haven't posted real code, nor provided any details
> > about what "doesn't work" means, it's not possible to tell what, if
> > anything, is wrong.
>
> > --
> >   Pete
> > Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
> > Standard C++ Library Extensions: a Tutorial and Reference
> > (www.petebecker.com/tr1book)-Hide quoted text -
>
> > - Show quoted text -
>
> -------code-----
> #include<iostream>
> #include<vector>
> #include<map>
> #include<set>
> #include<cstdlib>
> #include<cmath>
> #include<list>
> #include<stack>
> #include<queue>
>
> using namespace std;
>
> bool cmp(const pair<PII,int> &x, const pair<PII,int> &y){
>         return x.second < y.second;}
>
> priority_queue<pair<PII, int>, vector<pair<PII,int> >, cmp>
> heap;   //pair<pair<node I, node j>, weight>
>
> int main(){
>
> }
>
> ---------end---------
>
> for simplicity, you can compile the code above.
> I'm using vc8, and got the errors:
> ----------------------
> ------ Build started: Project: pku, Configuration: Debug Win32 ------
> Compiling...
> a.cpp
> ..\a.cpp(14) : error C2065: 'PII' : undeclared identifier
> ..\a.cpp(17) : error C3203: 'pair' : unspecialized class template
> can't be used as a template argument for template parameter '_Ty',
> expected a real type
> ..\a.cpp(17) : error C3203: 'pair' : unspecialized class template
> can't be used as a template argument for template parameter '_Ty',
> expected a real type
> ..\a.cpp(17) : error C2923: 'std::priority_queue' : 'cmp' is not a
> valid template type argument for parameter '_Pr'
>         ..\a.cpp(14) : see declaration of 'cmp'
> ..\a.cpp(17) : error C2133: 'heap' : unknown size
> ..\a.cpp(17) : error C2512: 'std::priority_queue' : no appropriate
> default constructor available
> ------------------------- Hide quoted text -
>
> - Show quoted text -

-------------code-----------
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cstdlib>
#include<cmath>
#include<list>
#include<stack>
#include<queue>

using namespace std;

#define PII pair<int,int>


bool cmp(const pair<PII,int> &x, const pair<PII,int> &y){
return x.second < y.second;
}
priority_queue<pair<PII, int>, vector<pair<PII,int> >, cmp>
heap; //pair<pair<node I, node j>, weight>

int main(){

}
---------------
this one in case you don't know what PII is.

Pete Becker

10/3/2008 7:14:00 PM

0

On 2008-10-03 13:33:55 -0400, thomas <FreshThomas@gmail.com> said:

> On Oct 4, 1:31 am, thomas <FreshTho...@gmail.com> wrote:
>> On Oct 4, 12:44 am, Pete Becker <p...@versatilecoding.com> wrote:
>>
>>
>>
>>
>>
>>> On 2008-10-03 12:41:16 -0400, Pete Becker <p...@versatilecoding.com> sa
> id:
>>
>>>> On 2008-10-03 12:05:38 -0400, thomas <FreshTho...@gmail.com> said:
>>
>>>>> priority_queue usually uses the greater<int> predicate function.
>>
>>>>> But as you know, we don't always use priority_queue<int>. Actually w
> e
>>>>> may need the "priority_queue<pair<int,int>, vector<pair<int,int> >,
>>>>> cmp> hp;" thing.
>>
>>>>> My question is how should I write the "cmp" function?
>>
>>>> It depends on what you want it to do.
>>
>>>>> I tried this one:
>>
>>>>> bool cmp(pair<int,int> &x, pair<int,int> &y){
>>>>>     return x.second < y.second;
>>>>> }
>>
>>>>> but it doesn't work while it usually makes sense for "sort" predicat
> e.
>>
>>>> It should work just fine, if you want your elements sorted by their
>>>> second field. If that's not what you want, then you need a different
>>>> comparison function.
>>
>>> However, it should probably take its arguments by const reference or by
>>> value. But since you haven't posted real code, nor provided any details
>>> about what "doesn't work" means, it's not possible to tell what, if
>>> anything, is wrong.
>>
>>> --
>>>   Pete
>>> Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
>>> Standard C++ Library Extensions: a Tutorial and Reference
>>> (www.petebecker.com/tr1book)-Hide quoted text -
>>
>>> - Show quoted text -
>>
>> -------code-----
>> #include<iostream>
>> #include<vector>
>> #include<map>
>> #include<set>
>> #include<cstdlib>
>> #include<cmath>
>> #include<list>
>> #include<stack>
>> #include<queue>
>>
>> using namespace std;
>>
>> bool cmp(const pair<PII,int> &x, const pair<PII,int> &y){
>>         return x.second < y.second;}
>>
>> priority_queue<pair<PII, int>, vector<pair<PII,int> >, cmp>
>> heap;   //pair<pair<node I, node j>, weight>
>>
>> int main(){
>>
>> }
>>
>> ---------end---------
>>
>> for simplicity, you can compile the code above.
>> I'm using vc8, and got the errors:
>> ----------------------
>> ------ Build started: Project: pku, Configuration: Debug Win32 ------
>> Compiling...
>> a.cpp
>> ..\a.cpp(14) : error C2065: 'PII' : undeclared identifier
>> ..\a.cpp(17) : error C3203: 'pair' : unspecialized class template
>> can't be used as a template argument for template parameter '_Ty',
>> expected a real type
>> ..\a.cpp(17) : error C3203: 'pair' : unspecialized class template
>> can't be used as a template argument for template parameter '_Ty',
>> expected a real type
>> ..\a.cpp(17) : error C2923: 'std::priority_queue' : 'cmp' is not a
>> valid template type argument for parameter '_Pr'
>>         ..\a.cpp(14) : see declaration of 'cmp'
>> ..\a.cpp(17) : error C2133: 'heap' : unknown size
>> ..\a.cpp(17) : error C2512: 'std::priority_queue' : no appropriate
>> default constructor available
>> ------------------------- Hide quoted text -
>>
>> - Show quoted text -
>
> -------------code-----------
> #include<iostream>
> #include<vector>
> #include<map>
> #include<set>
> #include<cstdlib>
> #include<cmath>
> #include<list>
> #include<stack>
> #include<queue>
>
> using namespace std;
>
> #define PII pair<int,int>
>
>
> bool cmp(const pair<PII,int> &x, const pair<PII,int> &y){
> return x.second < y.second;
> }
> priority_queue<pair<PII, int>, vector<pair<PII,int> >, cmp>
> heap; //pair<pair<node I, node j>, weight>
>
> int main(){
>
> }
> ---------------
> this one in case you don't know what PII is.

Presumably the result of compiling this code was different from the
result shown in the previous message.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

Fraser Ross

10/4/2008 9:06:00 AM

0

> > #include<iostream>
> > #include<vector>
> > #include<map>
> > #include<set>
> > #include<cstdlib>
> > #include<cmath>
> > #include<list>
> > #include<stack>
> > #include<queue>
The headers required are queue, utility and vector.

> >
> > using namespace std;
> >
> > #define PII pair<int,int>
A typedef is preferable. Two of them would be useful.
typedef std::pair<int,int> PII;
typedef std::pair<PII,int> element;

> > bool cmp(const pair<PII,int> &x, const pair<PII,int> &y){
> > return x.second < y.second;
> > }
Comparisons can be done on second but first would be more akin to the
associative containers.

> > priority_queue<pair<PII, int>, vector<pair<PII,int> >, cmp>
The third argument must be a type. It must be this: bool (*)(element
const &x, element const &y).

> > heap; //pair<pair<node I, node j>, weight>
A constructor that sets the comparison function must be invoked i.e.
heap(cmp)

A functor is easier to use than a function when you know how to use
them. I would rewrite the code to use a functor and to sort on first
instead of second.

Fraser.

ram

10/4/2008 11:55:00 AM

0

"Fraser Ross" <z@zzzzzz.com> writes:
>>>#include<stack>
>>>#include<queue>
>The headers required are queue, utility and vector.

In a class, I explained that using certain names and
operators requires certain include directives.

Then I was asked if it would be possible to always
copy /all/ standard include directives to the start
of a program. I answered that no one does this, but
that it would be possible.

Is there a reason not to do so (except for a possible
increase in compilation time)?

Maxim Yegorushkin

10/4/2008 1:18:00 PM

0

On 3 Oct, 17:05, thomas <FreshTho...@gmail.com> wrote:
> priority_queue usually uses the greater<int> predicate function.
>
> But as you know, we don't always use priority_queue<int>. Actually we
> may need the "priority_queue<pair<int,int>, vector<pair<int,int> >,
> cmp> hp;" thing.
>
> My question is how should I write the "cmp" function?
>
> I tried this one:
>
> bool cmp(pair<int,int> &x, pair<int,int> &y){
>     return x.second < y.second;
>
> }
>
> but it doesn't work while it usually makes sense for "sort" predicate.

std::sort() accepts the predicate by value and deduces its type, so
both function pointers and function objects (with operator()) work.

std::priority_queue<>, on the other hand, does not deduce the template
types, so that you have to specify it explicitly. The type of your
predicate is a function pointer:

typedef priority_queue<
pair<int,int>
, vector<pair<int,int> >
, bool(*)(pair<int,int>&, pair<int,int>&) // <--- here
> Q;

Constructors of the queue use a default-initialised value for the
predicate, which in your case is a NULL function pointer. Obviously,
you need to pass a pointer to you predicate function explicitly when
constructing the queue:

Q q(cmp);

It may be a bit easier to make your predicate a class, so that you
don't have to pass it into constructors:

struct cmp2
{
bool operator()(pair<int,int> const&, pair<int,int> const&)
const;
};

typedef priority_queue<
pair<int,int>
, vector<pair<int,int> >
, cmp2
> Q2;

Q2 q2; // <--- default-initialised cmp2 works

Please also note, that when you use function pointers the calls
through a function pointer can not be inlined. With function objects
they can.

--
Max

Paavo Helde

10/4/2008 10:54:00 PM

0

ram@zedat.fu-berlin.de (Stefan Ram) kirjutas:

> "Fraser Ross" <z@zzzzzz.com> writes:
>>>>#include<stack>
>>>>#include<queue>
>>The headers required are queue, utility and vector.
>
> In a class, I explained that using certain names and
> operators requires certain include directives.
>
> Then I was asked if it would be possible to always
> copy /all/ standard include directives to the start
> of a program. I answered that no one does this, but
> that it would be possible.
>
> Is there a reason not to do so (except for a possible
> increase in compilation time)?

Actually, a similar approach can be used for *reducing* compile times in
certain implementations (e.g. MSVC++). The idea is that you gather most
includes, including all needed standard includes, into a single header,
which is then marked to be precompiled. All cpp files include this header
first. As this header will be compiled only once it often means
significantly faster compile times for large projects.

As it might be quite hard to guess which standard includes any cpp might
need in an evolving project, I can imagine that it would be sometimes
practical to put *all* standard includes in the precompiled file, just in
case. Never done that myself, though.

hth
Paavo