C++ priority_queue with lambda comparator error

Question

I have the following erroneous code which I am trying to compile in VC2010, but I'm getting the error C2974 this only occurs when I include the lambda expression, so I'm guessing it has something to do with that.

typedef pair<pair<int, int>, int> adjlist_edge;
priority_queue< adjlist_edge , vector<adjlist_edge>,
    [](adjlist_edge a, adjlist_edge b) -> bool {
        if(a.second > b.second){ return true; } else { return false; }
    }> adjlist_pq;

I know the form of the template definition is correct as

priority_queue<int , vector<int>, greater<int>> pq;

Works as expected. Any ideas what I'm doing wrong? Is there something obviously wrong with the lambda that looks wrong that I might be overlooking? Thanks for reading!

Solution 1

First define the lambda object, then pass it to the template's type using decltype and also pass it directly to the constructor.

auto comp = []( adjist a, adjlist b ) { return a.second > b.second; };
priority_queue< adjlist_edge , vector<adjlist_edge>, decltype( comp ) >
     adjlist_pq( comp );

Solution 2

priority_queue takes the comparator as a template argument. Lambda functions are objects, and thus can't be used as template arguments (only very few types can be, among them integral types).

You can try using decltype there:

priority_queue< adjlist_edge , vector<adjlist_edge>,
               decltype( [](adjlist_edge a, adjlist_edge b) -> bool {
                if(a.second > b.second){ return true; } else { return false; }
               })>
adjlist_pq( [](adjlist_edge a, adjlist_edge b) -> bool {
                if(a.second > b.second){ return true; } else { return false; }
             } );

Failing that (and it will), you can use function<>:

priority_queue< adjlist_edge , vector<adjlist_edge>,
                function<bool(adjlist_edge,adjlist_edge)> >
adjlist_pq( [](adjlist_edge a, adjlist_edge b) -> bool {
                if(a.second > b.second){ return true; } else { return false; }
            } );

Solution 3

The accepted answer answered how to define a priority_queue with lambda expression as a custom Compare object. I would address another aspect of the question: why it fails when define a pq in your way:

typedef pair<pair<int, int>, int> adjlist_edge;
priority_queue< adjlist_edge , vector<adjlist_edge>,
    [](adjlist_edge a, adjlist_edge b) -> bool {
        if(a.second > b.second){ return true; } else { return false; }}> adjlist_pq;

Why we MUST pass the lambda as a parameter when constructing the priority queue? The reason lies in that lambda expression does not have a default constructor. So if you does not provide it when constructing the priority queue, the "supposed existing default constructor" of the lambda expression will be called. Clearly, it would fail.

With regard to your question: it is whether the Compare object(lambda or function object) has a default constructor makes the difference.

Solution 4

Following is an example for building a minheap using priority queue. I have used a lambda to define the comparator, given linked lists defined by vector<ListNode *> &lists

// This comparator will be used to build minheap.
auto comp = [&](ListNode *a, ListNode *b) {
    return a->val > b->val;
};

// This priority queue is the min heap
priority_queue<ListNode *, vector<ListNode *>, decltype(comp)> pq(comp);

View more solutions