Использование STL priority_queue с классом компаратора more_equal

Question

Запустив следующий пример, я получаю отладочное утверждение в отмеченной строке.

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

Есть подсказки?Помощь очень ценится!

Answer 1

Невозможно воспроизвести с:

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

И строкой компиляции:

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

Пожалуйста, укажите точные флаги компиляции

Answer 2

У вас неопределенное поведение.Ваша реализация хороша и утверждает, когда обнаруживает это.Компаратор, используемый с std::priority_queue, должен соответствовать названному требованию Сравните .std::greater_equal нет, потому что он возвращает true, если вы передаете ему равные значения.

Из соответствующей документации

Тип T удовлетворяет Сравните , если

Дано

• comp, объект типа T

Требования

• Для всех a, comp(a,a)==false

Answer 3

Все время, когда вы используете структуру данных STL с компаратором, этот компаратор должен быть строгим и никогда не возвращать true, если он получает равный объект для сравнения.

Представьте себе случай, когда 2 равных объектасравниваются, меняются местами, и следующее сравнение будет снова между теми же двумя объектами.В этом случае шаг сортировки STL никогда не остановится.

Попробуйте std::greater вместо std::greater_equal