Sorting a multidimensional array in C++

Question

Is it safe to sort a 2D array as shown in the code below?

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

And can we generalize this way for any multidimensional array?

I think it s pedantically UB. `a[0]` is only an array of 3 elements... `a[0][0] + 9` doesn't belong to its array. — Jarod42, Apr 16 '20 at 12:22
@Jarod42 `std::sort` sorts the elements in the range [first,last). So, what's wrong with that? — catfour, Apr 16 '20 at 12:30
I am not sure it is a valid range, as the 2 pointers belongs to different arrays. standard has specific rule with pointer arithmetic. `int [3][3]` is not `int [9]` even if they have same layout. — Jarod42, Apr 16 '20 at 12:47
@Jarod42 According to your comment, the posted answer is not safe. — catfour, Apr 16 '20 at 12:52
Does this answer your question? [Treating 2D array as 1D array](https://stackoverflow.com/questions/50795498/treating-2d-array-as-1d-array) — cigien, Apr 16 '20 at 13:19
@cigien Thank you for your comment, but I'm asking about a specific way if safe or not. — catfour, Apr 16 '20 at 13:30
@Jarod42 It's not a duplicated question! I'm not asking "How to sort a 2D array?". I know that we can treat it as a 1D array. Thank you. — catfour, Apr 16 '20 at 13:34
Duplicate ask if it is legal, whereas you ask for safety. it even happens that both of you use `std::sort` as example. You can use sort like that only if you can treat 2D-array as 1D array, which seems not be the case pedantically according to duplicates. — Jarod42, Apr 16 '20 at 14:13

score 1 · Answer 1 · 2020-04-17T08:53:38.857

1

Is it safe to sort a 2D array as shown in the code below?

My insight into corner cases isn't good, but this seems safe as long as your not accessing illegal indices.

The allotted 2D array locations are contiguous in memory, such for 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]

Since std::sort uses the [first,last) range, applying it over that range from a[0][0] to a[2][2]+1 makes sense, i.e.:

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

or considering from the base address instead of the end location:

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

gives the correct answer, although at the first sight it may seem to be undefined behaviour as &array[0][0]+(dim1*dim2) seems to be out of range. But it never accesses illegal indices, as the pointer (following pointer arithmetic) would only go from a[0][0] to a[2][2], following increments of the size of an integer, for an int 2D array. Uptil this point it seems correct or safe.

However, what Jarod wants to convey holds true as well - that we have two arrays in context, and a[0][0]..a[2][2] isn't the same as a[0]..a[9], as the type of the former would still pertain to int(*)[3], considering our array a[3][3] passed to std::sort.

Elaborating on what he said:

Passing from (&a[0][2]) + 1 is one past the end of array a[0]. &a[1][0], which is at same location belongs to another array:

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

If it were to be still correct (if you assume) then it would only make sense if ((&a[0][2]) + 1) - &a[1][0] would equal to 0. But its proven to show undefined behaviour and not 0, as demonstrated by Jarod in his demo here, with a corresponding example between (&a[0][0] + 3) and &a[1][0]. (Clang shows an error which can be used to justify the UB case)

And can we generalize this way for any multidimensional array?

Yes, why not?

Here's one for a three dimensional one:

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

edited Apr 17 '20 at 08:53

answered Apr 16 '20 at 12:09

This is correct because your array is stored in the memory as `a[0][0][0] a[0][0][1] a[0][1][0] ... etc.`, right? – catfour Apr 16 '20 at 12:19
@catfour Yes, uptil `a[1][1][1]` – Apr 16 '20 at 12:24
1

@catfour Do you intend to achieve something with this approach or did you ask this for curiosity? (I think this is a safe way.) Its sad that your question got flagged as a dupe, but if you wanted to work something out using that logic than I can edit my answer here – Apr 16 '20 at 14:28
Yes please, I want to know if this way is always safe or not because I see many people use complex ways to sort multidimensional arrays using `std::sort` instead of this way, and it seems that @Jarod42 disagrees with this way in the comments. Thank you. – catfour Apr 16 '20 at 14:37
@catfour This looks safe, or atleast I can't think of a situation where it would fail, with no illegal access to any index and the output working as expected. However, I do recommend you to use other options such an `std::array` or a `std::vector` with corresponding combinations, if your going for `std::sort` in two-dimensions. I'll include one example using an `std::array`, which is a better approach, atleast in comparison to C-style arrays. – Apr 16 '20 at 14:54
@Anirban166: issue is not in layout, but the standard rules about pointer arithmetic: `a[0][4]` is a out of bound access as `a[0]` has type `int(&)[3]`, even if there is ant `int` at that memory. – Jarod42 Apr 16 '20 at 19:07
@Anirban166 Your new example does not sort a 2D array (check it), you are sorting an array of three containers! – catfour Apr 16 '20 at 20:05
I mean you cannot sort each row separately and then sort the rows (e.g. 1, 4; 2, 3). – catfour Apr 16 '20 at 20:13
@Jarod42 But when would `a[0][4]` be accessed anyway? We would only go uptil `a[0][2]` (for an array of `[3][3]`) – Apr 17 '20 at 03:00
@catfour Right, I got the difference. If you want to sort elements both row-wise and column-wise, then your only bet would be to extract the elements in a linear fashion and use `std::sort`. (for which your approach does seem correct) – Apr 17 '20 at 03:04
`a[0][0]` belong to an array of 3 `int`s, `&a[0][0] + 9` is out of bound, You are limited to `&a[0][0] + 4`, which is `std::end(a[0])`. In the same way `struct{int a; int b; } s; *(&s.a + 1) = 42;` to set `s.b` is illegal. – Jarod42 Apr 17 '20 at 05:46
@Anirban166 +1 for your details. Again, `sort(&a[0][0], &a[2][2]);` should be `sort(&a[0][0], &a[2][2] + 1);` because `std::sort` sorts the elements in the range [first,last) (e.g. 4, 3; 2, 1). However, why does it produce different results in comparison to `sort(&a[0][0], &a[0][0]+(3*3));`?! – catfour Apr 17 '20 at 07:37
@catfour My bad, your right about the range. It doesn't produce different results, I didn't follow [first,last) - thanks for correcting :) – Apr 17 '20 at 07:46
@Jarod42 Got your example! But while that may be true, here `std::end(a)` for `std::sort` is equivalent to the last position in the 2D array. (Following the link that has been tagged as duplicate, I understand the same approach is used and the OP classified it as UB in his own answer, however it involves casts and its never mentioned to be unsafe, following the fact that it never touches any index out of bound) – Apr 17 '20 at 07:49
If UB, it cannot be safe :-) `std::end(a)` is `a + 3` which has type `int(*)[3]`. Issue is still type. Passing from `(&a[0][2]) + 1` is one past end array of `a[0]`. `&a[1][0]` (which is at same location) belongs to another array, so `((&a[0][2]) + 1) - &a[1][0]` is UB and not 0. – Jarod42 Apr 17 '20 at 08:19
We can mostly rely on constexpr to detect UB, and gcc/clang/msvc reject `&a[0][0] - 9` [Demo](https://godbolt.org/z/4VQ4n7). – Jarod42 Apr 17 '20 at 08:21
Only clang detects that `&a[0][0] + 3` and `a[1][0]` belongs to different array though [Demo](https://godbolt.org/z/xCAcDF). – Jarod42 Apr 17 '20 at 08:27
@Jarod42 Thats a good example, now I understand better :) Thanks for correcting me - Edited! – Apr 17 '20 at 08:49

Sorting a multidimensional array in C++

1 Answers1