Sort 2 dimensional c array with std::sort

Question

I cannot seem to sort a 2 dimensional c array with std::sort. I can however sort a one dimensional array. This is in a case where I am being handed a c array in a c++ program and am hoping to sort without copying it over to a std::array. Maybe there is some way to turn it into a std::array without copying it? That sounds doubtful to me as any std::array would then call a destructor on memory that it does not own.

Sorting One dimensional c style array works just fine:

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);

Attempting to sort two dimensional c style array by second number does not compile:

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);

The problem is that you cannot assign C-array, e.g., `two_dim[0] = two_dim[1]` is invalid. — Holt, Sep 15 '18 at 17:50
Copying the whole array takes a rather negligible amount of time compared to sorting, so it may not matter whether you copy or not. Note that if the rows were long (not just size 2 like here), it could be more efficient to sort the keys on the side and apply the final permutation to the matrix at the end, to avoid copying whole rows every time sorting swaps 2 elements. — Marc Glisse, Sep 16 '18 at 12:50
@MarcGlisse You make a good point about the time to copy the array. I was wanting my service to require O(1) space, which is not the case as soon as I make a full copy. Also, point taken regarding the contents of the nested array. — Peter, Sep 17 '18 at 13:13
Related: [c++ - Treat C cstyle array as std::array - Stack Overflow](https://stackoverflow.com/questions/11205186/treat-c-cstyle-array-as-stdarray) — user202729, Dec 30 '20 at 07:22
Note: std::sort is not guaranteed to sort in-place. (usually with the introsort implementation it does, but if insertion sort is used it might [allocate memory for one additional element](https://stackoverflow.com/questions/14212701/stdsort-does-not-always-call-stdswap)) — user202729, Dec 30 '20 at 14:48
Very related: [algorithm - Sorting zipped (locked) containers in C++ using boost or the STL - Stack Overflow](https://stackoverflow.com/questions/13840998/sorting-zipped-locked-containers-in-c-using-boost-or-the-stl) (although the exact thing to sort is different, the same approach work in both cases -- write a wrapper (non-conforming) iterator) — user202729, Jan 01 '21 at 08:04

score 3 · Answer 1 · answered Sep 15 '18 at 17:53

3

std::sort() requires the objects it's used to sort to be MoveAssginable.

Arrays are not MoveAssginable (nor assignable at all).

Try using an array of structures or std::pairs instead.

answered Sep 15 '18 at 17:53

HolyBlackCat

78,603
9
131
207

Thanks. I cannot change the input unless I am willing to copy it to my own structure. This helps though in that it clarifies why I could not get it to compile and that I either need to pay the price of copying or define my own sort function. – Peter Sep 15 '18 at 18:27
It looks like std::qsort does not require this. Would that work? – Peter Sep 15 '18 at 18:30
@Peter Yes, `qsort` should work since it moves the bytes directly, rather than relying on `operator=`. But note that it will result in undefined behvaiour if the objects it's used on are not [*trivially copyable*](https://en.cppreference.com/w/cpp/named_req/TriviallyCopyable). `int`s and arrays of `int`s *are* trivially copyable, but most classes (like `std::string`s) are not. In practice you can probably get away with `qsort`ing most classes (unless they e.g. rely on `operator=` to update some external pointer to their location), but you should still use it carefully. – HolyBlackCat Sep 15 '18 at 18:39

Geezer · Accepted Answer · 2018-09-16T12:38:54.313

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

Perhaps not turning into a std::array per se, but an alternative approach might be to cast the 2D C-style arrays into a std::array reference just for the sorting. Doing so in reliance on the standard saying an std::array representation in memory at least begins with its C-style array equivalent. See here under [array.overview§2]:

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

In practice, the following usage of reinterpret_cast is most probably safe, but do note that unless there is a special exception for it somewhere in the standard, it would formally be undefined behaviour:

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

Output:

Regarding the use of std::qsort(), note that it is potentially slower than std::sort() due to the latter allowing to inline the comparisons while the former doesn't.

An excellent answer! The only issue for my use is that the function that I am working with is passed arrays of any length along with a length variable and std::array has to have length at compile time. I do not think that there is any way around that with this approach, but this really taught me something. — Peter, Sep 15 '18 at 19:45
I thought about it and realized that I could use your approach for functions that take any size c array as follows: `auto& arrr = *reinterpret_cast **>(&arr2); std::sort(arrr, arrr + rows, two_dim_less);` — Peter, Sep 17 '18 at 18:24

Sort 2 dimensional c array with std::sort

2 Answers2

Linked

Related