CODEWITHSUNDEEP
c++stlpriority-queue
ardillapaga
ardillapaga

Reputation: 3

Using STL priority_queue with greater_equal comparator class

Running the following example I receive a debug assertion in the marked line. 

std::priority_queue<int, std::vector<int>, std::greater_equal<int>> queue_int;
queue_int.push(1);
queue_int.push(2);
queue_int.push(1); // Debug Assertion Failed: Expression invalid comparator

Any hints? Help much appreciated!

Upvotes: 0

Views: 257

Answers (3)

Radu Muntean
Radu Muntean

Reputation: 56

All the time when you are using a STL data structure with a comparator, that comparator needs to be strict and never return true if it is receiving equal object to compare.

Imagine the case when 2 equal objects are compared, swapped and the next comparation will be again between the same 2 objects. In this case the STL sort step will never stop.

Try std::greater instead of std::greater_equal

Upvotes: 4

Caleth
Caleth

Reputation: 62576

You have undefined behaviour. Your implementation is nice, and asserts when it detects that. The comparator used with std::priority_queue must meet the named requirement Compare. std::greater_equal does not, because it returns true if you pass it equal values.

From the relevant documentation

The type T satisfies Compare if

Given

  • comp, an object of type T

Requirements

  • For all a, comp(a,a)==false

Upvotes: 1

OrenIshShalom
OrenIshShalom

Reputation: 7102

Can not reproduce with:

#include <stdio.h>
#include <vector>
#include <queue>

int main(int argc, char **argv)
{
    std::priority_queue<int, std::vector<int>, std::greater_equal<int>> queue_int;
    queue_int.push(1);
    queue_int.push(2);
    queue_int.push(1); // Debug Assertion Failed: Expression invalid comparator
    return 0;
}

And compilation line:

$ g++ -std=c++17 -o main main.cpp

Please specify exact compilation flags used

Upvotes: -2

Related Questions