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!

Threedecker

Potential duplicate of #3867776 – Hultin

Answer 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 );

Americanist

Thanks, that works if I have to declare it separately do you think there is any benefit of using a lambda object over a functor? – Threedecker

Re: default constructor: [expr.prim.lambda]/19 says the default constuctor and copy assignment operators are deleted, and the copy constructor and destructor are implicitly defined, for closures. – Hultin

Why do you have to also pass it directly to the constructor? – Leomaleon

@Leomaleon because the class of a lambda function never has a default constructor, even when it has no captures. So priority_queue can only construct a comparison function object by copying. – Americanist

Is their a modernized version of this or is this still up to date? – Hull

@Hull refer to the answer by Unmitigated. Since C++ 20, lambdas without captures are default constructible and the syntax gets simplified. – Mancino

Answer 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; }
            } );

Hultin

+1 for being closer than interjay, but this still doesn't work because each lambda function has a unique type, even two objects with identical definitions. – Americanist

function is way better since it does not duplicate code (and apparently, it is the only correct thing to do). – Shrader

@Alexandre: There is another alternative, which sacrifices being a one-liner but is otherwise cleaner than function. – Americanist

You need to add a closing > to the priority_queue. Could not edit because of the 6 char. requirement. – Zoller

Answer 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.

Legging

Answer 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);

Fain

Answer 5

Since C++ 20, lambdas without captures are default constructible, so we can simply wrap the lambda in decltype as the third template parameter without requiring a separate variable at all.

priority_queue<adjlist_edge, vector<adjlist_edge>, 
  decltype([](adjlist_edge &a, adjlist_edge &b){return a.second > b.second;})> pq;

Truett