What is the correct way of implementing this custom priority_queue

Question

I want to build a priority queue of an object having three elements having my own comparator. I tried the following code but is showing error .

#include<bits/stdc++.h>
using namespace std;


class triplet {
    public:    
        int data;
        int arr;
        int index;       
};

bool compare( triplet x, triplet y ){

    if(x.data < y.data){
        return true;
    }
    else{
        return false;
    }
}

int main(){

 priority_queue<triplet,vector<triplet>,compare> pq1;

}

getting the following error enter image description here

What error are you getting, and what headers are you including? [Edit] your question to include these details. — 1201ProgramAlarm, Aug 17 '19 at 14:24
Your code doesn't [remotely compile](http://coliru.stacked-crooked.com/a/824f7d6be7a02204). Post a [mcve] as required here please! — πάντα ῥεῖ, Aug 17 '19 at 14:25
Also read up here please: https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h Stop doing this, especially in combination with `using namespace std;`. Who taught you to do so? — πάντα ῥεῖ, Aug 17 '19 at 14:31
Ok I got your point but the problem here is not which header file I am using , can you please explain how the priority_queue can be implemented. — Kundan Kumar, Aug 17 '19 at 14:55
@KundanKumar Not to mention that your question title isn't useful for future research. — πάντα ῥεῖ, Aug 17 '19 at 15:18

john · Accepted Answer · 2019-08-17T15:26:08.100

Comparison routines must return false if the two elements are equal, but your version returns true.

Try this instead

bool compare(triplet x, triplet y) {

    if (x.data < y.data) {
        return true;
    }
    else {
        return false;
    }
}

or to make it a little simpler like this

bool compare(triplet x, triplet y) {    
    return x.data < y.data;
}

But the important point is < not <=.

EDIT

Your code also uses compare incorrectly. compare is not a type, so it's not a valid argument for the priority_queue template.

The type of compare is bool (*)(triplet, triplet) so the right way to do this is to use that type in the template and pass the actual comparison function to the constructor. Like this

priority_queue<triplet, vector<triplet>, bool (*)(triplet, triplet)> pq1(compare);

BTW normally you would do this by creating a comparison functor, not a function. It's a little cleaner that way (and potentially more efficient).

@KundanKumar OK, I missed that error (you hadn't posted the error message when I replied). I'll edit my answer. — john, Aug 17 '19 at 14:54

What is the correct way of implementing this custom priority_queue

1 Answers1