c++ - 优先队列实现解释

Question

我正在阅读竞争性编程一书中的 Dijkstra 算法。在实现程序中，他们编写了如下内容:

#define pair<int,int> ii;
priority_queue< ii,vector<ii>,greater<ii> > pq ;

如果我们将整数 s 作为源，实现显示像这样推送对 (cost,source)(节点从 1 到 n 编号):

pq.push(ii(0,s)) ;

我的问题是我们在优先级队列中推送一对成本和节点。但是其他两个参数(即 vector 和 greater )在 priority_queue 声明中做了什么？

priority_queue< ii,vector<ii>,greater<ii> > pq ;

我尝试声明如下内容:

priority_queue< ii > pq ;

并且代码有效(在我尝试过的那些测试用例上)。

谁能告诉我声明的含义:

priority_queue< ii,vector<ii>,greater<ii> > pq ;

以及上层声明和

有什么区别

priority_queue< ii > pq ;

声明？

Answer 1

所以模板类的声明是这样的:


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


应该有三个模板参数。第一个“T”是元素的类型(在您的情况下为 ii)。第二个参数就是我所说的“底层容器”。你看，priority_queue 是一个适配器，即它在向你呈现另一组操作时 secret 地使用其他容器。 (您可能想在维基百科上查找“适配器模式”。)出于性能考虑，您可以告诉编译器它应该在下面使用什么容器。类(class)，deque和 vector可以使用标准库中的。参见 here对于容器类的要求。

现在，比较器是您用来定义元素顺序的东西。它可以是函数指针，也可以是重载了括号运算符的类。它接受您的元素类型的两个参数，如果第一个元素出现在队列中的第二个元素之后，则返回 (bool) "true"。当您想更改默认顺序或使用一些奇特的方式对元素进行排序时，它会很有用。

例如请参阅下面的一个简单示例

struct car{
    car(double engine_displ):_engine_displ(engine_displ) {} 
    double _engine_displ;
};
bool cmp_cars(car one, car other){
    return one._engine_displ < other._engine_displ;
}
//..somewhere else
std::priority_queue<car, std::vector<car>, cmp_cars> pq;

然后队列应该持有一个std::vector - 按发动机排量分类的大量汽车。

当出现类似 class Container = vector<T> 的内容时在模板参数列表中，编译器填写 std::vector<T>当你不说你的底层容器类型是什么时。这就是为什么你可以说 priority_queue<ii> ;编译器将其扩展为 priority_queue<ii,vector<ii>,less<ii>> .在您的示例中，本书的作者明确使用了 greater<ii> ，所以队列应该把最少的元素放在前面。这是有道理的，因为在 Dijkstra 算法中，您对成本最低的路径感兴趣。 priority_queue<ii>使用 less<ii>默认情况下，现在队列会将具有最大 cose 的路径放在前面，这是没有意义的。

作为旁注，您可能会发现代码实际上是 typedef pair<int,int> ii . #define指令告诉预处理器替换每个 pair<int,int>用“ii”，这根本没有帮助。 Typedef 告诉编译器“ii”表示 pait<int,int> .