问dijkstra算法的优先级队列

EN

C++优先级队列为：

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

在这里：

T是要存储在队列中的类型；希望这足够简单。

Container是队列中的底层存储。正如声明所示，这是默认的std::vector<T>，通常可以忽略它。

Compare' is the method for determining the ordering in the queue. Again, it has a default and can often be ignored.Compare`是一种支持函数调用的类型，它可以比较队列中的两个元素并确定它们的顺序。

less是默认的，只是应用了普通的<运算符。

当需要一个不同于<定义的排序时，可以定义一个提供所需比较的类型。正如您所拥有的：

struct comp {
  bool operator() (const pii &a, const pii &b) {
    return a.second > b.second;
  }
};

注意，这是如何获取两个pii并使用>操作符进行比较的；这与队列中的默认顺序相反。

然后将此comp类型指定为模板的第三个参数。

在指定了第三个参数之后，对于模板和函数，也必须指定第二个参数，即使我们只想要与默认参数std::vector<pii>相同的参数。

为什么是底层容器的规范？这是container adaptor模式。其思想是，优先级队列的语义不一定意味着存储数据的底层方式。此外，该标准还提供了一些专门针对存储的数据结构。因此，为什么不让priority_queue允许选择底层存储呢？这就是适配器的概念。

Check this

还可以检查这个dijkstra's algorithm - in c++?

如果您阅读priority_queue的引用，您可以看到第一个参数是类型，第二个参数是容器，第三个参数是比较类。此外，据我所知，在C++标准中只有一个优先级队列，我已经使用二进制搜索树实现了我自己的自定义队列，这是我推荐的一个非常有用的练习。

在zobayer博客上的Dijkstra算法的例子中，由于在代码中使用了宏，这一切都有点模糊。遗憾的是，这段代码如此模糊，因为它使代码更难理解。

comp类(默认情况下，struct是具有所有成员的类)操作符()简单地获取pii对中的第二项，并将其与另一个pii进行比较。您可以根据优先级队列中的任何类型对其进行自定义。