c++ - 使用 std::sort 对二维 c 数组进行排序

Question

我似乎无法使用 std::sort 对二维 c 数组进行排序。但是，我可以对一维数组进行排序。这是在这样的情况下，我在 C++ 程序中被交给一个 c 数组，我希望在不将它复制到 std::array 的情况下进行排序。也许有某种方法可以将它变成 std​​::array 而无需复制它？这对我来说听起来很可疑，因为任何 std::array 都会在它不拥有的内存上调用析构函数。

排序一维 c 样式数组工作得很好:

int len = 5;
auto one_dim_less = [](int a, int b){
  return a < b;
};
int one_dim[] = {4, 0, 3, 1, 2};
std::sort(one_dim, one_dim + len, one_dim_less);

尝试按第二个数字对二维 c 样式数组进行排序不会编译:

int len = 5;
auto two_dim_less = [](int a[2], int b[2]){
  return a[1] < b[1];
};
int two_dim[][2] = {{1,8}, {2,4}, {3,10}, {4,40}, {5,1}};
std::sort(two_dim, two_dim + len, two_dim_less);

Answer 1

Maybe there is some way to turn it into a std::array without copying it?

也许本身不会变成 std::array，但另一种方法可能是 cast 二维 C 风格数组进入一个 std::array reference 只是为了排序。这样做依赖于标准，即内存中的 std::array 表示至少以其等效的 C 样式数组 开始。请参阅此处 [array.overview§2] :

An array is an aggregate that can be list-initialized with up to N elements whose types are convertible to T.

在实践中，reinterpret_cast 的以下用法很可能是安全的，但请注意，除非在标准中某处有特殊异常(exception)，否则它在形式上是未定义的行为:

#include <algorithm>
#include <array>
#include <iostream>

int main() {
  auto two_dim_less = [](std::array<int, 2>& a, std::array<int, 2>& b) {
      return a[1] < b[1]; };

  int two_dim[][2] = {{1, 8}, {2, 4}, {3, 10}, {4, 40}, {5, 1}};

  std::array<std::array<int, 2>, 5>& arr =
    *reinterpret_cast<std::array<std::array<int, 2>, 5>*>(&two_dim);

  std::sort(arr.begin(), arr.end(), two_dim_less);

  for (int i = 0; i < 5; i++)
    std::cout << two_dim[i][0] << ", " << two_dim[i][1] << '\n';

  return 0;
}

输出:

5, 1
2, 4
1, 8
3, 10
4, 40

---

关于 std::qsort() 的使用，注意 it is potentially slower than std::sort()由于后者允许内联比较，而前者不允许。