How to use std::sort with pairs and references

Question

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.

Answer 1

If you use a std::reference_wrapper then it works as expected. Available Online.

int N = 5;
typedef std::pair<int, std::reference_wrapper<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]);
}

// Print, just to be sure :)
for (auto &x : v) {
    std::cout << x.first << ',' << x.second << std::endl;
}

std::sort(v.begin(), v.end(),
    [](const Ty &a, const Ty &b) { return a.second < b.second; });

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

Answer 2

It seems that libstdc++ does not use swap even though its availability is required. Anyhow, this appears to be legal. Probably it does something like this:

typename std::iterator_traits<RandomIt>::value_type tmp = a;
a = b;
b = tmp;

The first line involves reference initialization. tmp.second will refer to the same memory location as a.second. Therefore, in the end, b.second will retain its original value rather than being assigned the previous value of a.second.

For comparison, the unused pair swap has more sane behavior:

swap(a.first, b.first);
swap(a.second, b.second);

Note that, even if std::sort did use std::pair<int, int&>::swap, the semantics would be different from the pointer version because the pointer version sorts the pointers themselves and not the external array.