Priority Queue With a Custom Comparator No Matching Constructor

Question

I am trying to create a priority queue with a custom comparator but the following code gives me a compile error:

    auto comparator = [](std::pair<std::vector<int>, File&> const &a, std::pair<std::vector<int>, File&> const &b) {
      return a.first.front() > b.first.front();  
};

     std::priority_queue<std::pair<std::vector<uint64_t>, File&>,
      std::vector<std::pair<std::vector<uint64_t>, File&>>,
      decltype(comparator)> pq;

This is the error I am getting:

In template: no matching constructor for initialization of 'std::priority_queue<std::pair<std::vector, moderndbs::File &>, std::vector<std::pair<std::vector, moderndbs::File &>>, (lambda at

Your comparator knows how to compare values of type `std::pair, File&>`, but you are trying to use it to compare values of a different type `std::pair, File&>` — Igor Tandetnik, May 02 '21 at 23:23
Since you only pass the type of `comparator` to the priority queue, but not the instance itself, the queue has to default-construct one. However, lambdas are not default-constructible before C++20. You need to compile with C++20 support enabled for this to work, or else pass `comparator` to `pq`'s constructor, as in `std::priority_queue<...> pq{comparator}` — Igor Tandetnik, May 02 '21 at 23:27

score 1 · Accepted Answer · answered May 02 '21 at 23:30

There's a mismatch in your question, between uint64_t and int. Assuming that this is squared away:

You need at least C++20 in order to compile the shown code. Prior to C++20, lambdas are not default-constructible, and you attempting to default-construct your std::priority_queue.

You need to explicitly pass the comparator to the constructor. Tested with gcc 10, with -std=c++17:

#include <queue>
#include <functional>
#include <vector>
#include <cstdint>

class File{};

void foo()
{
    auto comparator = [](std::pair<std::vector<int>,
                 File &> const &a,
                 std::pair<std::vector<int>,
                 File &> const &b) {
        return a.first.front() > b.first.front();
    };

    std::priority_queue<std::pair<std::vector<int>,
                      File &>,
                std::vector<std::pair<std::vector<int>,
                          File &>
                    >,
                decltype(comparator)> pq{comparator};
}

This fails with with a default-constructor pq. gcc 10 compiles the default-constructed pq with -std=c++20.

P.S.: consider replacing the File & with std::reference_wrapper, unless you really intend to do what the File & in std::pair will really do.

Thank you, Sam! It works now :) File is a custom file class here, can you briefly mention what reference_wrapper does? I will only read these files later, which one should I use in this case :) — erinc, May 02 '21 at 23:55
See https://stackoverflow.com/questions/26766939/difference-between-stdreference-wrapper-and-simple-pointer — Sam Varshavchik, May 03 '21 at 00:19

Priority Queue With a Custom Comparator No Matching Constructor

1 Answers1