使用自定义比较器实例化 int 对的priority_queue 时在 C++ 中键入错误（以实现最小堆）

Question

目前正在解决一个 leetcode 问题，我需要最小堆对。
我正在尝试将

priority_queue

与

int

pair

和自定义比较类型一起使用。
尝试实施相同的方法失败，并出现以下错误：

在 prog_joined.cpp:1 包含的文件中： 在 ./precompiled/headers.h:55 包含的文件中： 在 /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/queue:64 包含的文件中： /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_queue.h:467:7：错误： static_assert 由于要求“is_same>::value”而失败“value_type 必须与底层容器相同” static_assert(is_same<_Tp, typename _Sequence::value_type>::值， ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ~~ 第 9 行：字符 67：注意：在此处请求的模板类 'std::priority_queue、std::allocator>>、std::greater>' 的实例化中 priority_queue>，更大> pq;

这是我尝试实现堆的代码：

#include <queue>
#include <utility>
using namespace std;
//...
priority_queue<int, pair<int, int>, greater<int>> pq;

Answer 1

正如您在

std::priority_queue

文档中看到的那样：

• 第 1st 模板参数是 data 类型（在您的情况下应该是 pair<int,int>

  ）。

第 2nd
• 模板参数应该是用于队列的底层容器类型。 第
3rd
• 应该是 compare 类型。

例如

，如果您想要使用 priority_queue 作为容器的

int

pair

std::vector

，

您需要：

std::priority_queue<std::pair<int, int>,                  // data type
                    std::vector<std::pair<int,int>>,      // container type
                    std::greater<std::pair<int,int>>> pq; // compare type

注意：

正如您在here所看到的，std::pair使用的比较运算符的

std::greater

实现是：

按运算符按字典顺序比较左侧和右侧

<, that is, compares the first elements and only if they are equivalent, compares the second elements.

如果这不是您所需要的，您可以为

std::pair<int,int>

实现您自己的比较类型。

旁注：

最好避免using namespace std。请参阅此处：

为什么是“using namespace std;”被认为是不好的做法吗？

.

Answer 2

priority_queue

，向量

>，更大>>pq;