将 STL priority_queue 与 greater_equal 比较器 class 结合使用

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

当您使用带有比较器的 STL 数据结构时，该比较器必须是严格的并且永远不会 return 如果它正在接收相等的对象进行比较。

想象一下比较、交换 2 个相同对象的情况，下一次比较将再次在相同的 2 个对象之间进行。在这种情况下，STL 排序步骤将永远不会停止。

尝试 std::greater 而不是 std::greater_equal

Answer 2

无法重现：

#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 3

您有未定义的行为。您的实现很好，并在检测到时断言。与 std::priority_queue 一起使用的比较器必须满足命名要求 Compare。 std::greater_equal 不会，因为如果传递相等的值，它 returns 为真。

来自相关文档

The type T satisfies Compare if

Given

comp, an object of type T

Requirements

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

将 STL priority_queue 与 greater_equal 比较器 class 结合使用

Using STL priority_queue with greater_equal comparator class

c++

stl

priority-queue