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

Question

We know std::priority_queue can be used to make a max heap. If I put a std::pair into it, it should be ordered according to the std::pair definition by comparing the first element and then the next:

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));
    }

However, the following code has strange behavior.

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);

The numbers of Q are not ordered. WHY!? Q is shown in

Answer 1

They are ordered. Your IDE is showing you the order of pairs in the vector that underlies your priority queue. See e.g. Wikipedia on how a heap is usually represented in array form to understand why they appear in this exact order. If you actually pop the elements of your queue one by one the will be returned in the correct order:

#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';
  }
}

Will print:

32, 2
25, 1
13, 0
11, 3