带有 lambda 比较器错误的 C++ priority_queue

C++ priority_queue with lambda comparator error

提问by ameer

I have the following erroneous code which I am trying to compile in VC2010, but I'm getting the error C2974this only occurs when I include the lambda expression, so I'm guessing it has something to do with that.

我有以下错误代码，我试图在 VC2010 中编译，但我收到错误C2974，这仅在我包含 lambda 表达式时发生，所以我猜它与此有关。

typedef pair<pair<int, int>, int> adjlist_edge;
priority_queue< adjlist_edge , vector<adjlist_edge>,
    [](adjlist_edge a, adjlist_edge b) -> bool {
        if(a.second > b.second){ return true; } else { return false; }
    }> adjlist_pq;

I know the form of the template definition is correct as

我知道模板定义的形式是正确的

priority_queue<int , vector<int>, greater<int>> pq;

Works as expected. Any ideas what I'm doing wrong? Is there something obviously wrong with the lambda that looks wrong that I might be overlooking? Thanks for reading!

按预期工作。任何想法我做错了什么？lambda 是否有明显的错误，看起来我可能忽略了？谢谢阅读！

回答by Potatoswatter

First define the lambda object, then pass it to the template's type using decltypeand also pass it directly to the constructor.

首先定义 lambda 对象，然后将其传递给模板的类型 usingdecltype并直接将其传递给构造函数。

auto comp = []( adjist a, adjlist b ) { return a.second > b.second; };
priority_queue< adjlist_edge , vector<adjlist_edge>, decltype( comp ) >
     adjlist_pq( comp );

回答by Marc Mutz - mmutz

priority_queuetakes the comparator as a template argument. Lambda functions are objects, and thus can't be used as template arguments (only very few types can be, among them integral types).

priority_queue将比较器作为模板参数。Lambda 函数是对象，因此不能用作模板参数（只有极少数类型可以，其中包括整型）。

You can try using decltypethere:

您可以尝试decltype在那里使用：

priority_queue< adjlist_edge , vector<adjlist_edge>,
               decltype( [](adjlist_edge a, adjlist_edge b) -> bool {
                if(a.second > b.second){ return true; } else { return false; }
               })>
adjlist_pq( [](adjlist_edge a, adjlist_edge b) -> bool {
                if(a.second > b.second){ return true; } else { return false; }
             } );

Failing that (and it will), you can use function<>:

如果失败（它会），您可以使用function<>：

priority_queue< adjlist_edge , vector<adjlist_edge>,
                function<bool(adjlist_edge,adjlist_edge)> >
adjlist_pq( [](adjlist_edge a, adjlist_edge b) -> bool {
                if(a.second > b.second){ return true; } else { return false; }
            } );

回答by kz28

The accepted answer answered howto define a priority_queue with lambda expression as a custom Compare object. I would address another aspect of the question: whyit fails when define a pq in your way:

接受的答案回答了如何使用 lambda 表达式将 priority_queue 定义为自定义比较对象。我将解决问题的另一个方面：为什么在以您的方式定义 pq 时它会失败：

typedef pair<pair<int, int>, int> adjlist_edge;
priority_queue< adjlist_edge , vector<adjlist_edge>,
    [](adjlist_edge a, adjlist_edge b) -> bool {
        if(a.second > b.second){ return true; } else { return false; }}> adjlist_pq;

Why we MUST pass the lambda as a parameter when constructing the priority queue? The reason lies in that lambda expression does not have a default constructor. So if you does not provide it when constructing the priority queue, the "supposed existing default constructor" of the lambda expression will be called. Clearly, it would fail.

为什么我们在构造优先级队列时必须将 lambda 作为参数传递？原因在于lambda 表达式没有默认构造函数。所以如果你在构造优先级队列时没有提供它，就会调用 lambda 表达式的“假定存在的默认构造函数”。显然，它会失败。

With regard to your question: it is whether the Compare object(lambda or function object) has a default constructor makes the difference.

关于您的问题：比较对象（lambda 或函数对象）是否具有默认构造函数会有所不同。

回答by Steffi Keran Rani J

Following is an example for building a minheap using priority queue. I have used a lambda to define the comparator, given linked lists defined by vector<ListNode *> &lists

以下是使用优先级队列构建 minheap 的示例。我使用 lambda 来定义比较器，给定由以下定义的链表vector<ListNode *> &lists

// This comparator will be used to build minheap.
auto comp = [&](ListNode *a, ListNode *b) {
    return a->val > b->val;
};

// This priority queue is the min heap
priority_queue<ListNode *, vector<ListNode *>, decltype(comp)> pq(comp);