CODEWITHSUNDEEP
c++stlpriority-queue
RATHI
RATHI

Reputation: 5289

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

I am learning how to use STL in C++. I am trying to implement a heap using std::priority_queue. Here is my attempt:

#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();
    }       
}

When I run this code on visual studio 2012. it crashes while pushing the second element. Error is below:

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

but when I run the same code in ideone, it works but the output is wrong. Ideone link

1.Can someone please point out where I am going wrong?

adding one more question in this same question:

2.How to write the lambda expression of this rather using the compare function?

Upvotes: 1

Views: 3145

Answers (2)

bogdan
bogdan

Reputation: 9317

You shouldn't ignore warnings issued by the compiler:

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

That's because else false; doesn't return anything, it just evaluates the expression false and discards the result. It should be else return false;.

Of course, the simpler alternative would be to just say return a.first < b.first;.

In reply to your updated question:

Using a lambda here won't buy you that much, since you need to specify both the type of the functor as a template argument to std::priority_queue, and the functor itself as an argument to the constructor when initializing heap (in the version using compare, the functor was default-constructed; lambdas are not default-constructible).

But, since you asked, here it is:

#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();
   }
}

I've made several modifications to your original code; take them as suggestions for improvement, in terms of both correctness (const) and efficiency.

Upvotes: 4

Phil
Phil

Reputation: 6164

Your compare function is missing a return before the false. This should work:

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

VS gives a compilation warning but not an error. As Barry points out, this is not an error. See this SO answer, https://stackoverflow.com/a/1610454/3154588, for more details. (I still contend this should be a compilation error, as having a code path that does not return a value, would always be wrong--at least for all of the code I have written!)

Upvotes: 2

Related Questions