How to use std::sort with pairs and references

Viewed 937

Is there a way to get sort working with collections of pairs where one element is a reference? I've code where I want to sort a std::vector<Ty>, where Ty is std::pair<A, B&> and A and B are classes. To give a minimal, concrete example, here is code for typedef std::pair<int, int&> Ty. This is supposed to sort the vector according to the second element of the pair.

void bad() {
  typedef std::pair<int, int &> Ty;
  int a[N] = {17, 4, 8, 10, 0};
  std::vector<Ty> v;
  for (int i = 0; i < N; ++i) {
    v.emplace_back(i, a[i]);
  }
  std::sort(v.begin(), v.end(),
            [](const Ty &a, const Ty &b) { return a.second < b.second; });

  std::cout << "With reference (bad):" << std::endl;
  for (auto &x : v) {
    std::cout << x.first << ',' << x.second << std::endl;
  }
}

This outputs:

With reference (bad):
4,17
3,17
2,17
1,17
0,17

However if I change the reference to a pointer, it works as I would expect

void good() {
  typedef std::pair<int, int *> Ty;
  std::vector<Ty> v;
  int a[N] = {17, 4, 8, 10, 0};
  for (int i = 0; i < N; ++i) {
    v.emplace_back(i, &a[i]);
  }
  std::sort(v.begin(), v.end(),
            [](const Ty &a, const Ty &b) { return *a.second < *b.second; });
  std::cout << "With pointer (good):" << std::endl;
  for (auto &x : v) {
    std::cout << x.first << ',' << *x.second << std::endl;
  }
}

Output:

With pointer (good):
4,0
1,4
2,8
3,10
0,17

I'd prefer to use references if possible; is there any way to fix this? I have tried tracing through with the debugger and I can't see why the pairs are not being copied (maybe swapped?) correctly by the sort algorithm.

2 Answers
Related