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.

Are you sure that the issue come from the sort function and not reference initialisation ? — nefas, May 24 '17 at 08:43
I can see a problem here: for (int i = 0; i < N; ++i) { v.emplace_back(i, a[i]); } Is this getting the reference of the variable a[i] or the value of the variable a[i] and you are holding the reference of a temporary? — Tomaz Canabrava, May 24 '17 at 08:45
@nefas If I comment out the call to sort, I see the expected (unsorted, obviously) list of items. — Peter Hull, May 24 '17 at 08:47
the ``operator[]`` for the ``vector`` return a reference (``const`` or not) of the element. Temporaries are (IMHO) not an issue. — nefas, May 24 '17 at 08:47
@TomazCanabrava I don't think so, if I print the address of the reference (&x.second) it matches with the address of the elements in the a[] array. — Peter Hull, May 24 '17 at 08:52
check out https://stackoverflow.com/a/922455/4534275 to see why you can't use the reference — nefas, May 24 '17 at 08:53
Strange enough, but the `void bad()` actually works fine on Apple clang 8.1.0 (using `-std=c++11 -stdlib=libc++`). Thus, the error is **not reproducible**. — Walter, May 24 '17 at 08:57
@Walter I'm glad you mentioned this; my original code came from OSX and I thought I must just have messed something up somewhere (don't have the Mac here to test) I checked and it fails on both g++ (5.4) and MSVC (VS2017) — Peter Hull, May 24 '17 at 09:04
@PeterHull So that open the question which of these compilers is correct, if any? — Walter, May 24 '17 at 09:09
@Walter I think it depends on the compiler option (C++11 or higher vs C++03 or lower). With C++11 (and higher) ``std::sort`` can use move assignment (which I think is legal for references) instead of swap (and copy which is illegal for reference) when moving the objects inside the vector. — nefas, May 24 '17 at 09:14
@nefas the code uses `auto`, `emplace_back()`, and a lambda. This must be C++11 or higher. — Walter, May 24 '17 at 09:23
My theory seemed to work so I didn't re-check the code ... Excepted the move vs copy theory or the fact that the code is may be UB, I don't see a reason why it work with some compiler and not with other. — nefas, May 24 '17 at 09:32
I should note that when compiling with Apple clang 8.1.1, the `vector` came out sorted in `Ty::second`, but the array `a[N]` was also sorted, which was not intended/expected. Note also that if you replace `int&` with `const int&` in the definition of `Ty`, the code will not compile. This is because it tries to assign to a `const int&` in (when sorting). Assign to a `int&` works, but does not what `sort` wants: it does not assign the reference, but the value referred to! — Walter, May 24 '17 at 09:43
Likewise on my compiler the a[N] array is corrupted (certainly not what I intended). So the difference between Apple clang and the others is probably in the implementation of std::sort rather than language fundamentals. This still leaves us with question of who's right. Does anyone know who would be the appropriate expert (I've filed radars with Apple before and it's not a particularly fulfilling experience..) — Peter Hull, May 24 '17 at 09:56

Jonas · Accepted Answer · 2017-05-24T08:56:57.743

5

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

edited May 24 '17 at 08:56

answered May 24 '17 at 08:50

Jonas

6,915
8
35
53

2

The original approach didn't work because you can't assign a reference: you can't do this ``int &ref; ref=a`` – nefas May 24 '17 at 08:55
@nefas That makes no sense, because in this case you should get a compiler error. – Walter May 24 '17 at 08:59
OK. I see - it's because references aren't CopyAssignable (e.g. https://stackoverflow.com/questions/922360/why-cant-i-make-a-vector-of-references) which I did know, in retrospect. However the compiler won't allow vector whereas it compiles my 'bad' code without error. Also thanks for the link to cpp.sh, never heard of that site before. – Peter Hull May 24 '17 at 09:00
@PeterHull I agree with your comment. http://en.cppreference.com is a fantastic website. – Walter May 24 '17 at 09:06
@Walter I think the issue here is that it is not a vector of reference but a vector of pair containing a reference. That's why there is no compiler error. But when you think about it it makes sense that you can't use reference (even if the pair) since doing ``p1 = p2`` is the same as ``p1.first = p2.first; p1.second = p2.second`` which is forbidden since ``p1.second`` is a reference – nefas May 24 '17 at 09:06
@nefas, still it should not compile. Btw, the code did compile and work as expected (i.e. w/o the error reported in the post) with Apple clang 8.1.1. – Walter May 24 '17 at 09:07
Did you compile with C++11 or higher ? If you did, the compiler used move assignment (which I think is allowed for reference). – nefas May 24 '17 at 09:11
@PeterHull I think a compile time error would have been nice. Personally I normally prefer http://ideone.com, but I can't reach it currently because of a "thorough" corporate firewall... – Jonas May 24 '17 at 09:30
1

cpp.sh has the bonus of executing other people's code once in a while, sure makes life exciting – Passer By May 24 '17 at 11:20

score 1 · Answer 2 · answered May 24 '17 at 19:39

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.

How to use std::sort with pairs and references

2 Answers2