如何使用std::排序对和引用

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.

是否有一种方法可以在一个元素是引用的情况下使用对的集合进行排序?我已经编写了要对std::vector 排序的代码，其中Ty是std::对< a, b&>， a和B是类。为了给出一个最小的、具体的示例，这里是typedef std::pair Ty的代码。 ,>

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 个解决方案

#1

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

如果您使用std:::reference_wrapper，那么它会像预期的那样工作。网上。

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

#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:

似乎libstdc++不使用交换，尽管它的可用性是必需的。无论如何，这似乎是合法的。可能是这样的:

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.

第一行涉及引用初始化。tmp。第二步是指相同的内存位置。因此，最后，b。第二，保留原有的价值，而不是被赋予先前的价值。

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.

注意，即使std::sort使用了std::pair :::swap，语义也与指针版本不同，因为指针版本对指针本身进行排序，而不是外部数组进行排序。 ,>

#1