为什么 Vector 用作 Priority Queue 的第二个参数？

Question

为什么当priority_queue与单一数据类型一起使用时，如'int'，我们这样初始化它：priority_queue<int>；但是，当它用一对初始化时，我们添加了向量类型的第二个参数 priority_queue<pair<int,int>, vector<pair<int,int>>>?

另外，我注意到有几种方法可以添加指定顺序的第三个参数。

方法 1 - 结构

struct myCompare {
   bool operator()(const pair<int, int>& A, const pair<int, int>& B) {
       return A.second < B.second;
   }
};

priority_queue<pair<int, int>, vector<pair<int, int>>, myCompare> leaderBoard;

方法 2 - Lambda

auto myComp = [](const pair<int, int>& A, const pair<int, int>& B) 
              {return A.second < B.second;};

priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(myComp)> leaderBoard(myComp);

我的问题

为什么priority_queue的第二个参数是vector？这是什么意思，什么时候需要指定第二个参数？
在方法 2 中，为什么这个 lambda 需要 decltype？
在方法二中，为什么对象leaderBoard需要用(myComp)初始化
在方法2中，为什么我不能直接将我的lambda指定为第三个参数？
A.second > B.second 和 A.second < B.second 有什么区别？你怎么记住哪个是升序，哪个是降序？

Answer 1

Why is the second parameter of priority_queue a vector?

您可以使用任何满足 certain requirements 的容器。 vector 是一个合理的默认选择。

What does this mean and when does this second parameter need to be specified?

如果你想改变它的默认值，或者你想指定第三个。 std::priority_queue<std::pair<int,int>> 是不指定第二个参数的有效类型。

In method 2, why is decltype needed with this lambda?

如果要使用自定义比较器，则必须将其类型指定为第三个模板参数。每个 lambda 都有自己独特的类型，获得它的唯一方法是通过 decltype.

In method 2, why does the object leaderBoard need to be initialised with (myComp)

因为基于struct的比较器可以默认构造，但基于lambda的比较器不能。相关的构造函数是

priority_queue() : priority_queue(Compare(), Container()) { }
priority_queue(const Compare& compare) : priority_queue(compare, Container()) { }

如果您不提供 compare，则使用 Compare()。 myCompare() 是有效值，而 decltype(myComp)() 不是。

In method 2, why can I not specify my lambda as the third argument directly?

您需要的是类型，而不是该类型的值。

What is the difference between A.second > B.second and A.second < B.second?

交换参数的顺序（或者，等价地，< 和 >）将最小堆变成最大堆，反之亦然，即该顺序决定将返回哪个元素按 .top()，最小或最大。

Answer 2

Why is it that when priority_queue is used with a single data type, like 'int', we initialise it like this: priority_queue<int> [...] ?

因为std::priority_queue是一个class模板，定义如下：

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

如您所见，您可以实例化此 class 仅提供 T，因为其余类型将被默认。您可以阅读有关 template default arguments here.

的更多信息

but, when it's initialized with a pair we add a second parameter of type vector priority_queue<pair<int,int>, vector<pair<int,int>>>?

因为有人想说清楚。 priority_queue<pair<int, int>> 等同于 priority_queue<pair<int,int>, vector<pair<int,int>>>，因为默认情况下会出现第二个模板类型 (vector<pair<int, int>>)。

Why is the second parameter of priority_queue a vector? What does this mean and when does this second parameter need to be specified?

我们不需要显式指定它。第二个模板参数是用于数据内部表示的类型。 std::priority_queue 是一个 容器适配器 ，这意味着它本身不是一个容器 - 它使用其他容器并 wraps 它具有一定的实用程序的种类。

In method 2, why is decltype needed with this lambda?

因为你需要提供一个类型。 myCompare 是一个 struct，所以它是一个类型的名称。 myComp 不是类型，而是变量。您希望获得其声明的类型？使用 decltype.

In method 2, why does the object leaderBoard need to be initialised with (myComp)?

因为给定 lambda () 的 decltype，您不能默认构造一个对象。您需要使用以下构造函数：

explicit priority_queue(const Compare& compare)
    : priority_queue(compare, Container()) { }

需要一个可调用对象（在本例中为 lambda）作为比较器。

In method 2, why can I not specify my lambda as the third argument directly?

你是说第三个 template 参数？因为截至目前，lambda 不能用于未计算的上下文中，为模板提供类型就是其中之一。

5.1. What is the difference between A.second > B.second and A.second < B.second?

差异非常明显。一个检查 A.second 是否大于第二个参数，另一个则相反。它通常用于排序（用于比较元素）。

5.2 How do you remember which one means ascending order, and which one is descending order?

这很简单 - C++ 的概念是在 left 手边参数之间使用 <和 right 手边参数，像这样：left_hand_side < right_hand_side.

Answer 3

In method 2, why does the object leaderBoard need to be initialised with (myComp)

这取决于您使用的 C++ 标准。在 C++20 之前，您需要将 lambda 表达式创建的仿函数传递给 priority_queue 构造函数，因为在 C++20 之前的 lambda 不是默认可构造的。

从 C++20 开始你可以写：

priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(myComp)> leaderBoard;

它将正常工作，因为编译器知道 lambda 的类型 - 由 decltype(myComp) 指定，并且它可以调用其默认构造函数。

In method 2, why can I not specify my lambda as the third argument directly?

是的，你可以，但你仍然需要使用 decltype 来获取比较器类型：

priority_queue<pair<int, int>, vector<pair<int, int>>, 
     decltype( [](const pair<int, int>& A, const pair<int, int>& B) 
              {return A.second < B.second;} ) > leaderBoard;

为什么 Vector 用作 Priority Queue 的第二个参数？

Why is Vector used as a second argument to Priority Queue?

c++

lambda

vector

priority-queue

decltype