优先队列的语法

Question

为什么我们需要 3 个参数来创建具有用户定义比较的优先级队列。

priority_queue<Node*, vector<Node*>, comp> pq;

为什么我们不能写像

priority_queue<Node*, comp> pq;

（删除向量）这样的东西来创建我们自己的比较运算符。 vector 的目的是什么？

还有元素是怎么拿去比较的，比较完之后压入队列。

这里怎么会出现超载

Answer 1

如果你看到

std::priority_queue

选择，你可以看到第二个和第三个模板参数在

std

实现中是默认的。

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

当你做

priority_queue<Node*, com>

所以这里

com

是第二个参数，但在声明中它是第三个。所以要将它设置到第三个位置，我们还需要添加第二个参数，就像我们必须在函数参数列表右侧添加默认参数的函数一样。

这就是

std::priority_queue

的设计方式，因为

std::vector

被用作默认容器，所以将它添加到第二个位置使我们可以灵活地使用我们自己的容器而不是

std::vector

。由于它恰好在其他默认参数列表的中间，因此要设置最正确的默认参数，必须同时设置其出现的默认参数。这是语言要求。

如果您了解优先队列，它会使用

heap

根据您提供的比较器以这样的顺序存储您的数据，以便（可以说）最大元素在顶部，优先队列，插入和提取数据使用那个比较器。默认情况下是

std::less

，它要求您为您尝试放入

<

的类型的

prirotiy_queue

运算符提供重载，在您的情况下它是

Node

。如果你想设置自己的优先级标准，你可以提供这样的重载。

Answer 2

为什么我们不能写类似 priority_queue pq;（删除向量）的东西来创建我们自己的比较运算符。

通过给感兴趣的特定类型起别名（以 vector 作为容器类型的优先级队列）来定义你想要的快捷方式是没有问题的：

template<typename T, typename Cmp = std::less<typename std::vector<T>::value_type>>
using vector_priority_queue = std::priority_queue<T, std::vector<T>, Cmp>;

vector_priority_queue<int> pq;
vector_priority_queue<int, comp> pq2;