priority_queue predicate

Discussion in 'C++' started by thomas, Oct 3, 2008.

  1. thomas

    thomas Guest

    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.
    thomas, Oct 3, 2008
    #1
    1. Advertising

  2. thomas

    thomas Guest

    On Oct 4, 12:44 am, Pete Becker <> wrote:
    > On 2008-10-03 12:41:16 -0400, Pete Becker <> said:
    >
    >
    >
    >
    >
    > > On 2008-10-03 12:05:38 -0400, thomas <> 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, Oct 3, 2008
    #2
    1. Advertising

  3. thomas

    thomas Guest

    On Oct 4, 1:31 am, thomas <> wrote:
    > On Oct 4, 12:44 am, Pete Becker <> wrote:
    >
    >
    >
    >
    >
    > > On 2008-10-03 12:41:16 -0400, Pete Becker <> said:

    >
    > > > On 2008-10-03 12:05:38 -0400, thomas <> 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.
    thomas, Oct 3, 2008
    #3
  4. thomas

    Fraser Ross Guest

    > > #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.
    Fraser Ross, Oct 4, 2008
    #4
  5. thomas

    Stefan Ram Guest

    standard include directives (was: priority_queue predicate)

    "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)?
    Stefan Ram, Oct 4, 2008
    #5
  6. On 3 Oct, 17:05, thomas <> 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
    Maxim Yegorushkin, Oct 4, 2008
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Tino

    clearing a priority_queue

    Tino, Jul 9, 2003, in forum: C++
    Replies:
    4
    Views:
    1,151
    Stuart Golodetz
    Jul 9, 2003
  2. newsock

    queue, deque, priority_queue

    newsock, Oct 24, 2003, in forum: C++
    Replies:
    15
    Views:
    2,420
    Tim Clacy
    Nov 4, 2003
  3. Dave
    Replies:
    7
    Views:
    541
    Jerry Coffin
    Apr 22, 2004
  4. Tino
    Replies:
    3
    Views:
    757
    rossum
    May 28, 2004
  5. red floyd

    std::priority_queue derivable?

    red floyd, Jun 16, 2004, in forum: C++
    Replies:
    2
    Views:
    450
    red floyd
    Jun 16, 2004
Loading...

Share This Page