优先级队列自定义比较器的 return 值表示什么？

Question

根据我能收集到的有关以下结构的优先级队列的自定义比较器的信息，它看起来像这样

struct event
{
    int index, arrival, duration, type, end;
};

struct compare
{
    bool operator() (event a, event b)
    {
        if (a.arrival < b.arrival) return true; // which one gets pushed first?
        else return false;
    }
};
...
priority_queue < event, vector <event>, compare > pq;

我不明白的是returning true或false的意思。如果我 return true，哪个元素首先被推入队列，如果我 return false?

Answer 1

std::priority_queue 是一个 max 堆，它默认使用 std::less（这是一个使用 operator< 的函数对象）。这意味着如果比较 returns false，第一个参数更接近顶部。来自 cppreference:

A priority queue is a container adaptor that provides constant time lookup of the largest (by default) element, at the expense of logarithmic insertion and extraction.

A user-provided Compare can be supplied to change the ordering, e.g. using std::greater<T> would cause the smallest element to appear as the top().

标准参考是[alg.heap.operations]。

旁注 #1：避免写 if (expr) return true; else return false; 而只写 return expr;

旁注 #2：您的 operator() 应该是一个 const 成员函数，并通过引用 const 来获取其参数以避免不必要的复制。

优先级队列自定义比较器的 return 值表示什么？

What does the return value of a priority queue custom comparator signify?

c++

priority-queue

comparator