CODEWITHSUNDEEP
c++lambdapriority-queue
Heyi Sun
Heyi Sun

Reputation: 31

lambda function doesn't work in priority_queue in c++ (when using [&])

When I am doing Leetcode.com, the following code cannot be compiled. 

auto cmp=[&](pair<int,int> a, pair<int,int> b){return heightMap[a.first]
         [a.second]<heightMap[b.first][b.second];};

priority_queue<pair<int,int>,vector<pair<int,int>>,decltype(cmp)> pq;

It works well when I use 

auto cmp=[](...){return true;}.

But I have to use 

auto cmp=[&](...){...}

because I need to access heightMap in the function.

I don't know why this cannot be compiled

Upvotes: 0

Views: 562

Answers (1)

M.M
M.M

Reputation: 141544

I assume you are working at block scope (i.e. inside a function).

The correct code -- for both the [&] and [] cases -- should be:

priority_queue<pair<int,int>,vector<pair<int,int>>, decltype(cmp)> pq(cmp);
//                                                                   ^^^^^

You can see this in the cppreference example.

If you think about it, the definition of pq with only decltype(cmp) can't know about any local variable -- that attachment is only formed in the actual creation of cmp.

The reason is that the default constructor for priority_queue is (C++17 [priqueue.cons]):

explicit priority_queue(const Compare& x = Compare(), Container&& y = Container());

As you can see, this involves default-constructing an object of type Compare. Prior to C++20, lambdas are not default constructible.

The default construction of stateless lambdas was added by P0624 which didn't quite make it into C++17, but does now appear in C++20 drafts.

Technically a C++17 compiler should reject even the [] version; but it seems some compilers have made a headstart on C++20 support.

I notice that clang++ 6.0.0 actually allows default construction of a lambda specified as [&] when it happens that no variable is actually captured; whereas the wording of P0624 says that that case should be rejected. Perhaps this will change again before C++20 is finalized.

Upvotes: 1

Related Questions