使用自定义 class 和 lambda 表达式的 C++ 中的优先级队列

Question

我正在学习如何在 C++ 中使用 STL。我正在尝试使用 std::priority_queue 实现一个堆。这是我的尝试：

#include<vector>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<functional>
using namespace std;

struct data {
    int first;
    int second;
};

class compare {
public:
    bool operator()(data &a ,data &b)
    {
         if(a.first < b.first) return true;
         else false;
    }
};

int main()
{   
    priority_queue <data , vector<data>, compare> heap;
    data temp2[] = { {5,19},{2,7},{90,9},{12,6} };

    for(int i = 0; i < 4; ++i)
    {       
       heap.push(temp2[i]);
    }

    while(heap.empty() == false)
    {
        cout << heap.top().first << endl;;
        heap.pop();
    }       
}

当我在 visual studio 2012 年运行这段代码时。它在推动第二个元素时崩溃。错误如下：

Program: C:\WINDOWS\system32\MSVCP110D.dll
File: c:\program files (x86)\microsoft visual studio 11.0\vc\include\algorithm
Line: 2463
Expression: invalid operator<

但是当我运行在 ideone 中使用相同的代码时，它可以工作，但输出是错误的。 Ideone link

1.谁能指出我哪里错了？

在同一问题中再添加一个问题：

2.如何写这个lambda表达式而不是使用比较函数？

Answer 1

您不应忽略编译器发出的警告：

warning C4715: 'compare::operator()' : not all control paths return a value

那是因为 else false; 没有 return 任何东西，它只是计算表达式 false 并丢弃结果。应该是 else return false;.

当然，更简单的选择是只说 return a.first < b.first;。

回复您更新的问题：

在这里使用 lambda 不会给你带来太多好处，因为你需要将仿函数的类型指定为 std::priority_queue 的模板参数，并将仿函数本身指定为构造函数的参数初始化 heap（在使用 compare 的版本中，仿函数是默认构造的；lambda 不是默认构造的）。

但是，既然你问了，那就是：

#include <iostream>
#include <queue>
#include <vector>

struct data
{
   int first;
   int second;
};

int main()
{
   auto cmp = [](const data& a, const data& b) { return a.first < b.first; };

   // For Visual C++ 2013 and beyond:
   // std::vector<data> temp = {{5, 19}, {2, 7}, {90, 9}, {12, 6}};
   // std::priority_queue<data, std::vector<data>, decltype(cmp)> heap{cmp, std::move(temp)};

   // For Visual C++ 2012 (doesn't support list-initialization for non-aggregates):
   data temp[] = {{5, 19}, {2, 7}, {90, 9}, {12, 6}};
   std::priority_queue<data, std::vector<data>, decltype(cmp)> heap(std::begin(temp), std::end(temp), cmp);

   while(!heap.empty())
   {
      std::cout << heap.top().first << '\n';
      heap.pop();
   }
}

我对您的原始代码进行了多次修改；将它们作为改进的建议，在正确性（const）和效率方面。

Answer 2

您的比较函数在 false 之前缺少 return。这应该有效：

class compare{
public:
    bool operator()(data &a, data &b)
    {
        if (a.first < b.first) 
            return true;
        else 
            return false;
    }
};

VS给出编译警告但不报错。正如 Barry 所指出的，这不是一个错误。有关更多详细信息，请参阅此 SO 答案。（我仍然认为这应该是一个编译错误，因为没有 return 值的代码路径总是错误的——至少对于我编写的所有代码而言！）

使用自定义 class 和 lambda 表达式的 C++ 中的优先级队列

priority queue in C++ with custom class and lambda expression

c++

stl

priority-queue