2

I mistakenly omitted the compare argument when defining a std::priority_queue:

#include <queue>

int main()
{
    constexpr auto cmp{[](int a, int b) { return a > b; }};
    std::priority_queue<int, std::vector<int>, decltype(cmp)> pq;
}

, and it compiled successfully and worked properly when I used it to implement Dijkstra's algorithm. Then I realized that I passed only the type information of cmp when constructing pq.

However, the code compiles only if --std=c++20 flag is used. I skimmed the priority_queue reference on cppreference.com but couldn't find any notice about a change that occurred since C++20.

I used the following version of g++:

g++ (Ubuntu 10.3.0-1ubuntu1~20.04) 10.3.0

Is this an intended behavior since C++20, and if so, what has affected this change?

Jay Lee
  • 1,684
  • 1
  • 15
  • 27

1 Answers1

4

The change happened on lambdas.

If no captures are specified, the closure type has a defaulted default constructor. Otherwise, it has no default constructor (this includes the case when there is a capture-default, even if it does not actually capture anything). (Since C++20)

Before C++20, lambda closure types are not DefaultConstructible, the comparator object can't be default-constructed in the default constructor of std::priority_queue, then you have to pass the lambda object to the constructor of std::priority_queue taking comparator object.

constexpr auto cmp{[](int a, int b) { return a > b; }};
std::priority_queue<int, std::vector<int>, decltype(cmp)> pq(cmp);
songyuanyao
  • 169,198
  • 16
  • 310
  • 405
  • Does it mean that the specific `return a > b;`, but not, e.g., `return a <= b`, is implied from the lambda type signature itself? – Jay Lee Oct 04 '21 at 07:38
  • @JayLee The signature doesn't matter, you can change the ordering what you want, using `return a > b;` you'll get the smallest element as the `top()`; using `return a < b;` you'll get the largest element as the `top()`. – songyuanyao Oct 04 '21 at 07:47
  • Maybe I should rephrase my question: How does the compiler manages to construct `cmp` itself only from `decltype(cmp)`? – Jay Lee Oct 04 '21 at 07:50
  • For example, I can find out the argument & the return type of a lambda: https://stackoverflow.com/questions/7943525/is-it-possible-to-figure-out-the-parameter-type-and-return-type-of-a-lambda , and I can see that the compiler can construct `cmp` from the `(cmp)` in the expression `decltype(cmp)`. But is the body of `cmp` actually being deduced from the `decltype(cmp)` itself? – Jay Lee Oct 04 '21 at 07:55
  • 2
    @JayLee `decltype(cmp)` gives the type of the lambda, then default-construct it as the comparator. It's just same as [this code](https://wandbox.org/permlink/h2mr3IKHSRcgwsj5) unless the compiler generates the lambda closure type for you instead a user-defined one. – songyuanyao Oct 04 '21 at 07:55
  • Maybe I'm overthinking this... Thank you! – Jay Lee Oct 04 '21 at 07:56
  • So the compiler identifies each lambda via labeling: `main::{lambda(int, int)#1}`, `main::{lambda(int, int)#2}`, etc. Now everything is clear to me! – Jay Lee Oct 04 '21 at 08:11