如何在 C++ 中使最大堆充满 std::pair

Question

我们知道std::priority_queue可以用来做最大堆。如果我将 std::pair 放入其中，它应该根据 std::pair 定义通过比较第一个元素然后比较下一个元素来排序：

template<class _Ty1,
    class _Ty2> inline
    constexpr bool operator<(const pair<_Ty1, _Ty2>& _Left,
        const pair<_Ty1, _Ty2>& _Right)
    {   // test if _Left < _Right for pairs
    return (_Left.first < _Right.first ||
        (!(_Right.first < _Left.first) && _Left.second < _Right.second));
    }

但是，下面的代码有奇怪的行为。

vector<int> B{13,25,32,11};
priority_queue<pair<int, int>> Q;
for (int i = 0; i < B.size(); ++i)
    Q.emplace(B[i], i);

Q的数字没有排序。为什么！？ Q显示在

Answer 1

它们是有序的。您的 IDE 向您展示了作为优先级队列基础的向量中对的顺序。参见例如Wikipedia 关于堆通常如何以数组形式表示以了解它们为何以这种确切顺序出现。如果您实际上将队列中的元素一一弹出，将以正确的顺序返回：

#include <iostream>
#include <queue>
#include <vector>

int main() {
  std::vector<int> B{13,25,32,11};
  std::priority_queue<std::pair<int, int>> Q;
  for (int i = 0; i < B.size(); ++i)
    Q.emplace(B[i], i);

  while (!Q.empty()) {
    auto P(Q.top());
    Q.pop();

    std::cout << P.first << ", " << P.second << '\n';
  }
}

将打印：

Answer 2

deduction changed in c++20 - 你可以在 c++17 中编译它，你的代码将工作。您必须根据 cpp20 指南解析您的代码。

如何在 C++ 中使最大堆充满 std::pair

How to make max heap filled with std::pair in C++

c++

priority-queue

std-pair