有人可以解释一下 std::greater 是如何用来实现 priority_queue 的吗

Question

std::priority_queue<int, vector<int>, std::greater<int> > pq;

我无法理解 std::greater 在优先级队列中的工作。我正在用优先级队列替换 minheap。此代码取自 geeksForGeeks implementation of Prims algorithm using STL

Answer 1

std::priority_queue 类型就是所谓的容器适配器。它的工作原理是从一个可用于表示序列的类型开始，然后使用该类型构建优先级队列（具体来说，作为二叉堆）。默认情况下，它使用向量。

为了做到这一点，优先级队列类型必须知道如何以一种确定哪些元素比其他元素“更小”的方式将元素相互比较。默认情况下，它使用小于运算符。

如果你创建一个标准std::priority_queue<int>，你会得到一个

的优先级队列

使用 std::vector 进行存储，
使用小于运算符比较元素。

在很多情况下，这就是您想要的。如果您将元素插入以这种方式创建的优先级队列中，您将从最大到最小读回它们。

不过，在某些情况下，这不是您想要的行为。例如，在 Prim 算法和 Dijkstra 算法中，您希望值以升序顺序返回，而不是降序顺序。为此，您实际上需要通过使用大于运算符而不是小于运算符来颠倒比较顺序。

为此，您需要告诉优先级队列使用不同的比较方法。不幸的是，优先队列类型的设计使得如果你想这样做，你还需要指定你想使用哪个底层容器。我认为这是设计中的一个错误——能够指定比较器而不是比较器和容器真的很好——但这就是生活。语法是

std::priority_queue<int,               // store integers...
                    std::vector<int>,  // ... in a vector ...
                    std::greater<int>> // ... comparing using >

有人可以解释一下 std::greater 是如何用来实现 priority_queue 的吗

Can someone explain how std::greater is used to implement priority_queue

stl

minimum-spanning-tree

prims-algorithm

c++11