时间戳

首页 > 解决方案 > 在 C++ 中对多维数组进行排序

c++ - 在 C++ 中对多维数组进行排序

问题描述

如下代码所示对二维数组进行排序是否安全？

int a[3][3];
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        cin >> a[i][j];
    }
}
sort(&a[0][0], &a[0][0] + 3 * 3); // the built-in sort function
for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
        cout << a[i][j] << ' ';
    }
    cout << '\n';
}

我们可以将这种方式推广到任何多维数组吗？

标签： c++arrayssorting

解决方案

如下代码所示对二维数组进行排序是否安全？

我对极端情况的洞察力并不好，但只要您不访问非法索引，这似乎是安全的。

分配的二维数组位置在内存中是连续的，例如a[3][3]：

a[0][0]..a[0][1]..a[0][2]..a[1][0]..a[1][1]..a[1][2]..a[2][0]..a[2][1]..a[2][2]

由于std::sort使用 [first,last) 范围，因此将其应用于该范围 from a[0][0]toa[2][2]+1是有意义的，即：

sort(&a[0][0], &a[2][2]+1);

或从基地址而不是结束位置考虑：

sort(&a[0][0], &a[0][0]+(3*3));

给出了正确的答案，尽管乍一看它似乎是未定义的行为，&array[0][0]+(dim1*dim2)似乎超出了范围。但它从不访问非法索引，因为对于2D 数组，指针（跟随指针算术）只会从a[0][0]到a[2][2]，跟随整数大小的增量。int到目前为止，它似乎是正确或安全的。

然而，Jarod 想要传达的也是正确的——我们在上下文中有两个数组，并且a[0][0]..a[2][2]与 不同a[0]..a[9]，因为前者的类型仍然属于int(*)[3]，考虑到我们的数组a[3][3]传递给std::sort。

详细解释他所说的：

传递 from(&a[0][2]) + 1是数组末尾的一个过去a[0]。&a[1][0]，在同一位置属于另一个数组：

a[0][0]..a[0][1]..a[0][2] -> Array 1 
// a[0][2] + 1 -> exceeds index of the first array among the three arrays of the array which forms a[3][3]
a[1][0]..a[1][1]..a[1][2] -> Array 2
a[2][0]..a[2][1]..a[2][2] -> Array 3

如果它仍然是正确的（如果你假设）那么它只有((&a[0][2]) + 1) - &a[1][0]等于 0 才有意义。但它被证明显示未定义的行为而不是 0，正如 Jarod 在他的演示中所证明的那样，在(&a[0][0] + 3)和之间有一个相应的例子&a[1][0]. （Clang 显示一个错误，可用于证明 UB 案例的合理性）

我们可以将这种方式推广到任何多维数组吗？

是的，为什么不？

这是一个三维的：

#include <iostream>
#include <algorithm>

int main() 
{
  int a[2][2][2];
  for (int i = 0; i < 2; i++) 
      for (int j = 0; j < 2; j++) 
          for (int k = 0; k < 2; k++)
              std::cin >> a[i][j][k];

  std::sort(&a[0][0][0], &a[0][0][0] + 2 * 2 * 2); 

  for (int i = 0; i < 2; i++) {
      for (int j = 0; j < 2; j++) {
          for (int k = 0; k < 2; k++)
              std::cout << a[i][j][k] << " ";
          std::cout << "\n";
      }
   }
}

推荐阅读