std::swap of std::priority_queue with lambda comparator compiles under C 20 but not C 17: "er-CodePudding

The following code, which std::swaps two std::priority_queue<int, std::vector<int>, decltype(some lambda)>s, results in a compiler error in C 17, but not in C 20.

#include <queue>

int main()
{
    auto cmp = [](int x, int y) {return x > y;};
    std::priority_queue<int, std::vector<int>, decltype(cmp)> pq1(cmp), pq2(cmp);
    std::swap(pq1, pq2); // adding this line results in an error
    return 0;
}

The error under C 17 is

error: object of type 'value_compare' (aka '(the lambda cmp)') cannot be assigned because its copy assignment operator is implicitly deleted
    {c = _VSTD::move(__q.c); comp = _VSTD::move(__q.comp); return *this;}

note: in instantiation of member function 'std::priority_queue<int, std::vector<int>, (lambda at main.cpp:13:16)>::operator=' requested here
  __x = _VSTD::move(__y);

note: in instantiation of function template specialization 'std::swap<std::priority_queue<int, std::vector<int>, (lambda at main.cpp:13:16)>>' requested here
    swap(pq1, pq2);

I feel the key here is that somehow, the lambda cmp's copy assignment operator is implicitly deleted. I've learned from the top answer at std::priority_queue syntax with lambda is confusing that C 20 made lambdas without default captures default-constructible (see cppreference source as well), but the issue here seems to be with copy-constructing, not default-constructing.

Why doesn't the code compile under C 17, and what changes in C 20 let it compile?

CodePudding user response：

"seems to be with copy-constructing": No, as the error message says it is with copy-assigning.

Swapping requires reassignment between the two objects, not only construction, because the two objects are not replaced by new ones. Only their values are exchanged.

Before C 20 lambdas were not assignable at all and so this can't work. Since C 20 lambdas without capture are copy-assignable and so this works.

If you want a quick-and-dirty workaround for C 17, you can convert a non-generic lambda without captures to a function pointer which is copy-assignable (and -constructible). The function pointer conversion can be done explicitly or implicitly with the trick. Note that one can cause UB if using this incorrectly (see below) and that it is likely less performant, requiring an indirect function call to the comparator:

auto cmp =  [](int x, int y) {return x > y;};
std::priority_queue<int, std::vector<int>, decltype(cmp)> pq1(cmp), pq2(cmp);
std::swap(pq1, pq2); // works now

The clean and performant solution that also works in the generic case is to use a proper function object type with a name:

struct cmp {
     // might want to add noexcept/constexpr here
     bool operator()(int x, int y) const {return x > y;}
};

std::priority_queue<int, std::vector<int>, cmp> pq1, pq2;
std::swap(pq1, pq2); // works now

Note that here you don't need to pass anything to the constructor. The function object type is default-constructible.

Specifically for the lambda in your question, you can also just use std::greater<int> or std::greater<> as the type. std::greater implements a predicate function object for x > y, in the latter version with deduced parameter types.

If you don't pass cmp in the function pointer variant to the constructor, the default-initialization will initialize it to a null pointer value and cause undefined behavior if actually used by the priority queue.

In C 20 you also don't need to actually pass cmp in your original variant to the constructors, because lambdas without capture are now also default-constructible as you mentioned.