«

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.

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:riority_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:riority_queue' : no appropriate
default constructor available
------------------------

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:riority_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:riority_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.

> > #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:air<int,int> PII;
typedef std:air<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.

"Fraser Ross" <> 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)?

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:riority_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