CODEWITHSUNDEEP
c++priority-queue
angryInsomniac
angryInsomniac

Reputation: 859

Reversing order of elements in a priority Queue

I am pushing stuff into a priority Queue and I've made a comparison method for elements that go in there , when I checked the order , I realized I wanted elements to go in the other way around , so I went and changed all the boolean returns from my comparison method to be opposite of what they originally were and now it gives me a million assertion failures. If I ignore them , the program still works as expected , but why the assert fails ? Why should the program care ? 

 bool operator()(charElement &operand1,charElement &operand2)
{
    // If the frequency of op1 < op2 then return true
    if(operand1.i_frequency < operand2.i_frequency) return true; //change to false

    // If the frequency of op1 > op2 then return false
    if(operand1.i_frequency > operand2.i_frequency)return false; //change to true

    // If the frequency of op1 == op2 then return true (that is priority is indicated to be less even though frequencies are equal)
    if(operand1.i_frequency == operand2.i_frequency)return true; //change to false

    // By default , return true (that is priority is indicated to be less)
    return true; //change to false
}

By the way, why was my query downvoted ? I try to ask sane questions and I believe this is one of them.

Specifics : I changed the operator definition to what @sehe suggested. Now if I add a not operator to the return value, it gives me assertion failures (invalid operator<) inside the include file , line number 2457. I checked the file , it seems that the error is in an inline method called Push_heap_0 , but I am stumped as to what that code does

Upvotes: 0

Views: 1376

Answers (2)

fredoverflow
fredoverflow

Reputation: 263098

Can't you simply reverse the order of the parameters? That is, replace:

bool operator()(charElement &operand1,charElement &operand2)

with:

bool operator()(charElement &operand2,charElement &operand1)

Then you can leave the body of the function as it is.

On a side note, comparisons are read-only operations, and we should always respect const correctness:

bool operator()(const charElement& operand2, const charElement& operand1)

Also, you are not allowed to return true if the elements are equal:

if(operand1.i_frequency == operand2.i_frequency)return true;   // HUGE PROBLEM!

You must always return false in that case, no matter if you want "normal" or "backwards" order.

The opposite of < is not >, but >=. This seems to be hard for programmers to grasp.

Upvotes: 4

sehe
sehe

Reputation: 392893

The problem could be many things

  • what is the type of charElement.i_frequency?
  • how are you using the dequeue (type && constructor && algorithms invoked)

That said, it looks like you can greatly simplify your comparator. My preferred idiom for this

bool operator()(charElement &operand1,charElement &operand2)
{
    return operand1.i_frequency < operand2.i_frequency;
}

or for reverse logic:

bool operator()(charElement &operand1,charElement &operand2)
{
    return operand1.i_frequency > operand2.i_frequency;
}

If it is actually a compound and a little more complex:

bool operator()(charElement &operand1,charElement &operand2)
{
    return std::tie(operand1.i_frequency, operand1.otherfield) < 
               std::tie(operand2.i_frequency, operand2.otherfield);
}

Upvotes: 1

Related Questions