Search code examples
c++lambdapriority-queuedecltype

c++: priority_queue of struct and decltype comparator

class Solution {

    struct tree{
        int x;
        int y;
        int height;
    }; 



public:
    int cutOffTree(vector<vector<int>>& forest) {

         auto lambda1 =  [](tree &t1, tree &t2){return t1.height < t2.height;};

         priority_queue<tree, vector<tree>, decltype(lambda1)> pq1;

        return 0;
    }
};

but got the error:

enter image description here

Any idea what I did wrong? Thanks!

Solution

  • priority_queue requires an instance of the Compare type which is used for comparison.

    The default constructor of priority_queue tries to construct the instance as Compare(). Since Compare here is a closure type it will fail, because closure types are not default-constructible.

    You need to provide the instance to the constructor. It will save a copy of it for later use:

    priority_queue<tree, vector<tree>, decltype(lambda1)> pq1{lambda1};

    As it stands currently, this will not be necessary anymore in C++20 for lambdas without capture such as here, because they will be made default-constructible. You may try this out with the experimental C++20 support in compilers with e.g. the -std=c++2a or /std:c++latest flags to your compiler.

    Since C++17 you can also use class template argument deduction to avoid naming the lambda and the value type twice:

    priority_queue pq1{lambda1, vector<tree>};