c++ - 为什么 Vector 被用作 Priority Queue 的第二个参数？

Question

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

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

方法一 - 结构

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;

方法二 - 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中，为什么decltype需要这个 lambda 吗？

方法二中，为什么对象leaderBoard需要用 (myComp) 初始化

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

A.second > B.second有什么区别和 A.second < B.second ?你怎么记得哪个是升序，哪个是降序？

Answer 1

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是一个定义如下的类模板:

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

如您所见，您可以仅提供 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>> ) 将默认存在。

1. 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是一个容器适配器，这意味着它本身不是一个容器——它使用其他一些容器并用某种实用程序包装它。

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

因为你需要提供一个类型。 myCompare是 struct ，所以它是一个类型的名称。 myComp不是一个类型，它是一个变量。你想得到它声明的类型吗？使用 decltype .

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

因为你不能默认构造一个给定 decltype 的对象一个 lambda ( this got relaxed in C++20 )。您需要使用以下构造函数:

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

它需要一个可调用的(在这种情况下是 lambda)作为比较器。

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

你的意思是第三个 template争论？因为就目前而言，lambdas 不能在未评估的上下文中使用，为模板提供类型就是其中之一。

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_hand_side < right_hand_side .