使用std :: sort对C风格的2D数组进行部分排序 [英] Partially sort a C-style 2D array with std::sort

问题描述

我遇到了这个问题，该问题涉及对整数数组的前2行进行排序，这显然是一种我的想法是使用std::sort，所以我提出了一个解决方案，例如:

I came across this question regarding sorting the first 2 lines of an array of integers, the obvious way that came to mind was to use std::sort so I proposed a solution like:

int mat[][3] = { {4, 5, 3},
                 {6, 8, 7},
                 {9, 5, 4},
                 {2, 1, 3} }; 


std::sort(std::begin(mat[0]), std::end(mat[1])); //sprting the first two rows

您可以请参见此处，它可以正常工作而不会出现错误或警告.

As you can see here it works without errors or warnings.

同时 @ Jarod42指出，这是行为学上不确定的行为，因为它们是两个不同数组的指针.

Meanwhile @Jarod42 pointed out that this is pedantically undefined behaviour in C++ because these are pointers of two different arrays.

我倾向于这种做法，因为在C语言中，这将是一种很好的方式(当然没有std::sort，std::begin和std::end)，使用一种类似的方法来访问数组，给出了将2D数组存储在C中的方式.

I inclined towards this given that in C this would be a good way to do it, (without the std::sort, std::begin and std::end of course), using a similar method of accessing the array in line, given the way 2D arrays are stored in C.

我们同意这将是不确定的行为，

We agreed that it would be undefined behaviour, but as @SergeBallesta remebered, pretty much all compilers accept this method, so should it be used?

如果使用一个int(*mat)[3]指向数组的指针又会怎么样呢? UB这样使用std::sort吗?

And what about if one uses a int(*mat)[3] pointer to array, would it still be pedantic UB to use std::sort this way?

//...
srand(time(0));

int(*mat)[3] = (int(*)[3])malloc(sizeof(int) * 4 * 3);
//or int(*mat)[3] = new int[4][3];

for(int i = 0; i < 4 ; i++)
    for(int j = 0; j < 3; j++)
        mat[i][j] = rand() % 9 + 1;

std::sort(std::begin(mat[0]), std::end(mat[1])); //sorting the first two rows
//...

推荐答案

问题出在标准定义数组类型(8.3.4 [dcl.array])的方式上:

The problem comes from the way the standard defines an array type (8.3.4 [dcl.array]):

一个数组类型的对象包含一个连续分配的N类型的N个子对象的非空集合.

An object of array type contains a contiguously allocated non-empty set of N subobjects of type T.

但它没有明确表示可以将连续分配的相同类型的对象集用作数组.

but it does not explicitely says that a contiguous allocated set of objects of the same type can be used as an array.

出于兼容性的原因，我认识的所有编译器都接受这种互惠性，但是从理论的角度来看，它在标准中并未明确定义，并且是未定义的行为.

For compatibility reasons all compilers I know accept that reciprocity, but on a pedantical point of view, it is not explicitely defined in the standard and is Undefined Behaviour.

非互惠背后的理由是，程序应该代表模型.并且在模型中，对象没有理由同时成为成员或一个以上数组.因此，该标准不允许这样做.实际上，我在处理2D数组时遇到的所有(实际)用例就好像是1D数组一样，都是低级优化的原因.而且在现代C ++中，程序员不应在意低级优化，而应由编译器来处理它.

The rationale behind the non reciprocity is that a program is expected to represent a model. And in the model, an object has no reason to be member or more than one array at the same time. So the standard does not allow it. In fact all the (real world) use cases I have ever encountered for handling a 2D array as if it was a 1D one were just low level optimization reasons. And in modern C++, the programmer should not care for low level optimization but let the compiler handle it.

以下只是我的看法.

当您发现自己像处理2D数组一样处理2D数组时，应该问问自己原因.如果您使用的是旧版代码，请不必担心:编译器目前接受它，即使将来以特殊选项为代价，它甚至可能会继续使用.

When you find yourself processing a 2D array as if it was a 1D one, you should ask yourself for the reason. If you are using a legacy code, do not worry about it: compilers currently accept it, and even in the future will probably continue, even at the price of special options.

但是，如果您要编写新代码，则应该尝试将代码向上或向后移动一步，并想知道它在模型级别上代表什么.大多数情况下，您会发现数组本质上是1D或2D，但不是全部都是1D或2D.完成此操作后，如果性能不是很关键，请尝试始终以一致的方式处理它.甚至更好，请尝试使用标准库中的容器而不是原始数组.

But if you are writing new code, you should try to move one step higher (or back) and wonder what it represents at the model level. Most of the time, you will find the the array is intrisically 1D or 2D but not both. Once this is done, if performance is not critical try to always handle it the conformant way. Or even better, try to use containers from the standard library instead of raw arrays.

如果您在性能至关重要的代码中说任何连续分配的对象集都是一个数组，则可以带来很大的好处，请这样做并为以后的维护者记录下来.但是只有在分析之后才能这样做...

If you are in a performance critical code where saying that any contiguous allocated set of objects is an array provides an important benefit, do it and document it for future maintainers. But only do that after profiling...

这篇关于使用std :: sort对C风格的2D数组进行部分排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！