优先队列实现说明 [英] priority queue implementation explanation

问题描述

我正在从《竞争编程》一书中阅读Dijkstra的算法。在实现程序中，他们写了这样的东西：

I was reading Dijkstra's algorithm from the book competitive programming 1.In the implementation program they have written something like this :

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

如果我们使用整数s作为源，则实现将显示对（成本，源）这样（节点从1到n编号）：

If we are taking an integer s as a source,the implementation shows to push pair (cost,source) like this (nodes are numbered from 1 to n) :

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

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

My question is we are pushing a pair of cost and node in the priority queue. But what the two other parameters (namely vector and greater ) are doing in the priority_queue declaration ?

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

我尝试声明以下内容：

priority_queue< ii > pq ;

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

And the code works (on those testcases I have tried) .

谁能告诉我该声明的含义：

Can anyone tell me what they meant by the declaration :

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

上方声明和

priority_queue< ii > pq ;

声明？

推荐答案

因此模板类的声明是这样的：

So the declaration of the template class is something like this:


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


应该有三个模板参数。第一个 T是元素的类型（在您的情况下为ii）。第二个参数是我所谓的基础容器。您会看到，priority_queue是一个适配器，即它在向您提供另一组操作的同时秘密使用了其他容器。 （您可能希望在Wikipedia上查找适配器模式。）出于性能方面的考虑，可以告诉编译器应在下面使用哪个容器。可以使用标准库中的 deque 和 vector 类。有关容器类的要求，请参见此处。

There are supposed to be three template parameters. The first one, "T", is the type of the elements (ii in your case). The second parameter is what I called "underlying container". You see, priority_queue is an adaptor, i.e. it uses other containers in secret while presenting to you another set of operations. (You might want to look up "adaptor pattern" on wikipedia.) For performance considerations, you can tell the compiler what container it should use underneath. The classes, deque and vector from the standard library can be used. See here for the requirements for the container class.

现在，比较器是用来定义元素顺序的工具。它可以是函数指针，也可以是带有括号运算符的类。它接受您元素类型的两个参数，如果第一个元素应出现在队列中的第二个之后，则返回（布尔） true。当您要更改默认顺序或使用某些特殊方式对元素进行排序时，此功能很有用。

Now, the comparator is something you use to define the ordering of your elements. It can either be a function pointer or a class with the bracket operator overloaded. It takes two arguments of your element type, and returns (bool) "true" if the first element should appear after the second in the queue. It's useful when you want to change the default order, or use some exotic ways to order your elements.

例如参见下面的简单示例

e.g. see below for a trivial example

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 -满是根据发动机排量分类的汽车。

the queue should then hold a std::vector-ful of cars sorted by engine displacement.

当模板参数列表中出现诸如 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> ，因此，现在队列将把具有最大粗

When there's something like class Container = vector<T> in the list of template arguments, the compiler filles in std::vector<T> for you when you don't say what your underlying container type is. That's why you can just say priority_queue<ii>; the compiler extends it to priority_queue<ii,vector<ii>,less<ii>>. In your example, the author of the book is explicitly using greater<ii>, so the queue should put the least element in front. It makes sense since in Dijkstra's algorithm, you're interested in the path that has the least cost. priority_queue<ii> uses less<ii> by default, so now the queue would put the path with the largest cose in front, which doesn't make sense.

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

As a side note, you might find that the code is actually typedef pair<int,int> ii. The #define directive tells the preprocessor to replace every pair<int,int> with "ii", which doesn't help at all. Typedef tells the compiler "ii" means pait<int,int>.

这篇关于优先队列实现说明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！