如何使用std::sort对pair和引用进行排序。

Question

有没有一种方法可以对其中一个元素为引用的pair集合进行排序？ 我有一段代码，想要对一个std::vector<Ty>进行排序，其中Ty是std::pair<A, B&>，而A和B是类。为了给出一个最小的具体例子，这里是typedef std::pair<int, int&> Ty 的代码。这个代码应该根据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;
  }
}

这将输出：

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

然而，如果我将引用更改为指针，则其工作方式符合我的期望。

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

输出：

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

如果可能的话，我更喜欢使用参考文献; 有没有办法解决这个问题？ 我已经尝试使用调试器进行跟踪，但我看不出为什么排序算法不能正确地复制（也许交换？）这些对。

- Peter Hull

---

如果我注释掉对sort的调用，我会看到预期的（显然是未排序的）项目列表。 - Peter Hull

@TomazCanabrava 我不这么认为，如果我打印引用的地址（&x.second），它与a[]数组中元素的地址匹配。 - Peter Hull

请查看 https://dev59.com/dnNA5IYBdhLWcg3wh-cC#922455 了解为什么不能使用引用。 - nefas

很奇怪，但是在苹果clang 8.1.0上（使用-std=c++11 -stdlib=libc++），void bad()实际上运行良好。因此，错误无法重现。 - Walter

@PeterHull那么，这就引出了一个问题，这些编译器中的哪一个是正确的（如果有的话）？ - Walter

Answer 1

如果您使用 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;
}

- Jonas

---

原始方法不起作用，因为您无法分配引用：您无法执行此操作“int &ref; ref=a”。 - nefas

@PeterHull 我同意你的评论。http://en.cppreference.com 是一个非常棒的网站。 - Walter

@Walter 我认为这里的问题是它不是一个引用向量，而是一个包含引用的对向量。这就是为什么没有编译器错误的原因。但是当你考虑它时，你会发现你不能使用引用（即使是对），因为执行“p1 = p2”与“p1.first = p2.first; p1.second = p2.second”相同，这是被禁止的，因为“p1.second”是一个引用。 - nefas

@PeterHull 我认为编译时错误会更好。个人而言，我通常更喜欢使用http://ideone.com，但由于“彻底”的公司防火墙，我目前无法访问它... - Jonas

cpp.sh有时会执行其他人的代码，这确实让生活变得充满了刺激。 - Passer By

Answer 2

看起来 libstdc++ 没有使用 swap，尽管需要其可用性。无论如何，这似乎是合法的。可能它会做类似于这样的事情：

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

第一行涉及到引用初始化。 tmp.second 将引用与 a.second 相同的内存位置。因此，最终，b.second 会保留其原始值，而不是被赋予 a.second 的先前值。

相比之下，未使用的 pair swap 行为更加合理：

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

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

- Arne Vogel