std::swap of std::priority_queue with lambda comparator compiles under C++20 but not C++17: "error: object of type value_compare cannot be assigned"

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?

Solution

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