приоритетная очередь в C++ с пользовательским классом и выражением лямбда

Question

Я изучаю, как использовать STL в C++. Я пытаюсь реализовать кучу, используя 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(); 
    }  
} 

Когда я запускаю этот код на визуально студии 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. Как написать лямбда-выражение этого, а с помощью функции сравнения?

Answer 1

Вы не должны игнорировать предупреждения, выданные компилятором:

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

Это потому, что else false; не возвращает ничего, он просто оценивает выражение false и отбрасывает результат. Он должен быть else return false;.

---

Конечно, проще альтернативы можно было бы просто сказать return a.first < b.first;.

---

В ответ на ваш обновленный вопрос:

Использование лямбда здесь не будет покупать вам, что много, так как вам нужно указать и тип функтора в качестве аргумента шаблона для std::priority_queue и functor сам по себе как аргумент конструктору при инициализации heap (в версии с использованием compare функтор был сконфигурирован по умолчанию, lambdas не являются стандартными по умолчанию).

Но, так как вы просили, вот оно:

#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

Ваша функция сравнения отсутствует return до false. Это должно работать:

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

VS дает предупреждение о компиляции, но не является ошибкой. Как отмечает Барри, это не ошибка. См. Этот ответ SO, https://stackoverflow.com/a/1610454/3154588, для более подробной информации. (Я все еще утверждаю, что это должна быть ошибка компиляции, поскольку наличие кода, который не возвращает значение, всегда будет неправильным - по крайней мере, для всего кода, который я написал!)