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

Question

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

4

我似乎无法使用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);

- Peter

3

问题在于你不能赋值 C 数组，例如 two_dim[0] = two_dim[1] 是无效的。 - Holt

2

复制整个数组所需的时间与排序相比可以忽略不计，因此复制与否可能并不重要。请注意，如果行很长（不仅仅是大小为2的情况），则在排序过程中每次交换两个元素时避免复制整行，而是在最后将最终排列应用于矩阵可能更有效率。 - Marc Glisse

1

@MarcGlisse，你提到了复制数组所需的时间，这一点很有道理。我希望我的服务需要O(1)的空间，但是一旦我进行完整的复制，情况就不是这样了。此外，我接受了关于嵌套数组内容的观点。 - Peter

相关：c++ - 将C风格数组视为std :: array - Stack Overflow - user202729

注意：std::sort不能保证原地排序。（通常使用introsort实现时会这样做，但如果使用插入排序，则可能会为一个额外的元素分配内存） - user202729

非常相关：算法 - 使用boost或STL在C++中对压缩（锁定）容器进行排序（尽管要排序的确切内容不同，但在两种情况下都可以使用相同的方法--编写一个包装（非符合性）迭代器）。 - user202729

2个回答

3

std::sort() 要求被用来排序的对象是可移动赋值的。

数组不是可移动赋值的（也不能被赋值）。

尝试使用结构体数组或者 std::pair 代替。

- HolyBlackCat

谢谢。除非我愿意将其复制到自己的结构中，否则我无法更改输入。尽管如此，这有助于澄清为什么我无法使其编译，并且我需要付出复制的代价或定义自己的排序函数。 - Peter

看起来 std::qsort 不需要这个。那样行吗？ - Peter

@Peter 是的，qsort应该可以工作，因为它直接移动字节，而不是依赖于operator=。但请注意，如果它作用的对象不是平凡复制构造类型，则将会导致未定义行为。 int和int数组是平凡复制构造类型，但大多数类（例如std::string）不是。在实践中，您可能可以使用qsort对大多数类进行排序（除非它们依赖于operator=来更新其位置的某些外部指针），但仍应谨慎使用它。 - HolyBlackCat

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Geezer · Accepted Answer

也许有一种方法可以在不拷贝的情况下将其转化为std :: array吗？

也许不是直接转换成std :: array，但另一种替代方法可能是将2D C-style arrays 转换为std :: array 的引用，仅用于排序。这样做依赖于标准中说std :: array 在内存中的表示至少以其C-style array等效物开头。请参见此处的[array.overview§2]：

“数组是一个聚合体，可以使用最多N个可转换为T类型的元素进行列表初始化。”

在实践中，以下使用reinterpret_cast的用法很可能是安全的，但请注意，除非标准中有特殊的例外，否则它在形式上将是未定义行为：

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

输出：

有关使用std::qsort()，请注意它可能比std::sort()慢，因为后者允许内联比较，而前者不允许。