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

Question

为什么当priority_queue与单个数据类型（如'int'）一起使用时，我们像这样初始化它：priority_queue<int>;但是，当用一对初始化时，我们添加了第二个参数，类型为vector 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);

我的问题

1. 为什么priority_queue的第二个参数是向量？这是什么意思，什么时候需要指定第二个参数？
2. 在方法2中，为什么此lambda需要decltype？
3. 在方法2中，为什么需要使用(myComp)初始化对象LeaderBoard
4. 在方法2中，为什么不能直接将我的lambda指定为第三个参数？
5. A.second > B.second和A.second < B.second有什么区别？您如何记住哪一个是升序，哪个是降序？

谢谢！

Answer 1

为什么当priority_queue与单一数据类型（如'int'）一起使用时，我们像这样初始化它：priority_queue<int> [...]？

因为std::priority_queue是如下定义的类模板：

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

如您所见，您可以仅提供T来实例化此类，因为其余类型将被默认设置。您可以阅读有关template default arguments here的更多信息。

但是，当用一对初始化时，我们添加了第二个参数，类型为向量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>>）。

1. 为什么priority_queue的第二个参数是向量？这是什么意思，什么时候需要指定第二个参数？

我们不需要明确地]指定它。第二个模板参数是用于内部表示数据的类型。 std::priority_queue是container Adaptor，这意味着它本身不是容器-它使用其他容器，并使用某些实用程序对其进行[[wraps。

在方法2中，为什么此lambda需要decltype？

因为您需要提供一个

type。 myCompare是struct，因此它是类型的名称。 myComp不是类型，而是变量。您希望得到它的declared type吗？使用decltype。

在方法2中，为什么需要使用(myComp)初始化对象LeaderBoard？

因为您无法默认给定lambda的decltype来构造对象。您需要使用以下构造函数：

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

期望有一个可调用对象（在这种情况下为lambda）将用作比较器。

在方法2中，为什么不能直接将我的lambda指定为第三个参数？

[您的意思是第三个template自变量？因为截至目前，lambda不能在未评估的上下文中使用，为模板提供类型就是其中之一。

5.1。 A.second > B.second和A.second < B.second有什么区别？

区别很明显。一个检查A.second是否大于第二个参数，另一个检查相反。

5.2您如何记住哪个代表升序，哪个代表降序？

非常简单-C++的概念是在

left

]手侧参数和right手侧参数之间使用<，如下所示：[ C0]。

在方法2中，为什么需要初始化对象LeaderBoard与（myComp）

取决于您使用的C ++标准。在C ++ 20之前，您需要将由lambda表达式创建的函子传递给left_hand_side < right_hand_side构造函数，因为直到C ++ 20都无法默认构造lambda。

自C ++ 20起，您可以编写：

priority_queue

因为编译器知道lambda的类型-由priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(myComp)> leaderBoard;
指定，并且可以调用其默认ctor，所以可以正常工作。
在方法2中，为什么不能将我的lambda指定为第三个参数直接吗？

是，可以，但是您仍然需要使用decltype(myComp)来获得比较器类型：

decltype

为什么priority_queue的第二个参数是向量？
您可以使用满足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;
的任何容器。 certain requirements是合理的默认选择。
这是什么意思，什么时候需要指定第二个参数？
如果要更改其默认值，或者要指定第三个值。 vector是有效类型，未指定第二个参数。
在方法2中，为什么此lambda需要decltype？
如果要使用自定义比较器，则必须将其类型指定为第三个模板参数。每个lambda都有其自己的唯一类型，唯一的获取方法是通过std::priority_queue<std::pair<int,int>>。
在方法2中，为什么需要使用（myComp）初始化对象LeaderBoard
因为可以默认构造基于decltype的比较器，但是不能构造基于lambda的比较器。相关的构造函数是
struct
如果不提供priority_queue() : priority_queue(Compare(), Container()) { }
priority_queue(const Compare& compare) : priority_queue(compare, Container()) { }
，则使用compare。 Compare()是有效值，而myCompare()不是有效值。
在方法2中，为什么不能直接将我的lambda指定为第三个参数？
不清楚您的意思。您需要一个类型，而不是该类型的值。
A.second> B.second和A.second 
交换参数的顺序会将最小堆转换为最大堆，反之亦然，即该顺序确定将由decltype(myComp)()（最小还是最大）返回哪个元素。

Answer 2

在方法2中，为什么需要初始化对象LeaderBoard与（myComp）

Answer 3

为什么priority_queue的第二个参数是向量？