Sorting a C 2D array via std::sort

Question

I have a 2D array a[][40]. I'm trying to sort it by calling std::sort, and I have written the Compare function. However, C++ wants me to have a std::vector to be sorted, not a simple array and I want the sorted array to be a itself, I don't want to create another array and save the sorting result there. It seems there are a lot of ways to achieve that. I could think of five ways, but none of them seems to be efficient and working.

1)

Directly use std::sort(std::begin(a), std::begin(a) + something, cmp);

It doesn't work, because std::begin doesn't know how to point to the beginning of a 2D array. Furthermore, it'd sort incorrectly even if it compiled, since a 2D array is not an array of references to arrays, but consecutive arrays (unlike Java)

Playground: https://godbolt.org/g/1tu3TF

2)

std::vector<unsigned char[40]> k(a, a + x);
std::sort(k.begin(), k.end(), cmp);

Then copy everything back to a

It doesn't work, because it's a 2D array, and it can't be sorted this way, using std::sort. In contrast to the first trial, this one uses twice as much as memory, and copies everything twice (if it worked)!

Playground: https://godbolt.org/g/TgCT6Z

3)

std::vector<int> k(x);
for (int i = 0; i < x; k[i] = i, i++);
std::sort(k.begin(), k.end(), cmp2);

Then change the order of a to be the same of k;

The idea is simple, create a vector of representative "pointers", sort them (as the cmp2 function secretly accesses a and compares the values), then make a have the same order with k.

In the end, the re-ordering loop will be very complex, will require a large, temporary variable. Besides, for cmp2 to access the values of a, a global variable-pointer that points to a must be created, which is "bad" code.

Playground: https://godbolt.org/g/EjdMo7

4)

For all unsigned char[40], a struct can be created and their values can be copied to structs. Comparison and = operators will need to be declared. After sorted, they can be copied back to a.

It'd be a great solution if the arrays didn't have to be copied to structs to use struct's operators, but they need to be copied, so all values will be copied twice, and twice-as-needed memory will be used.

5)

For all unsigned char[40], a struct that has a pointer to them can be created. They can be sorted by the pointed values, and the result can be saved to a pointer array.

It's probably the best option, although the result is a pointer array instead a. Another reason on why it's good is it doesn't move the arrays, but the pointers.

To sum up, I need to sort the 2D array a[][40] via std::sort, but I haven't decided on the best way. It seems there's a "best way to do that" which I can't think of. Could you please help me?

EDIT: To clarify, I want {{3,2}{1,4}} to become {{1,4}{3,2}}

Answer 1

The problem is not in iterating a 2D array. Provided the columns size is a constexpr value, pointers to arrays are nice iterators.

But all C++ sort (or mutating) algorithms require the underlying type to be move constructible and move assignable and an array is not assignable. But wrapping the underlying arrays can be enough:

template <class T, int sz>
class wrapper {
    T* base;
    bool own;            // a trick to allow temporaries: only them have own == true
public:
    // constructor using a existing array
    wrapper(T* arr): base(arr), own(false) {}

    ~wrapper() {              // destructor
        if (own) {
            delete[] base;    // destruct array for a temporary wrapper
        }
    }
    // move constructor - in fact copy to a temporary array
    wrapper(wrapper<T, sz>&& src): base(new T[sz]), own(true) {
        for(int i=0; i<sz; i++) {
            base[i] = src.base[i];
        }
    }
    // move assignment operator - in fact also copy
    wrapper<T, sz>& operator = (wrapper<T, sz>&& src) {
        for(int i=0; i<sz; i++) {
            base[i] = src.base[i];
        }
        return *this;
    }
    // native ordering based on lexicographic string order
    bool operator < (const wrapper<T, sz>& other) const {
        return std::char_traits<char>::compare(base, other.base, sz) < 0;
    }
    const T* value() const {    // access to the underlying string for tests
        return base;
    }
};

Then, you can sort a C compatible 2D array with any C++ sort algo:

std::vector<wrapper<char, 40> > v { &arr[0], &arr[sz] };  // pointer are iterators...
std::sort(v.begin(), v.end());                            // and that's all!

for (int i=0; i<sz; i++) {                                // control
    std::cout << arr[i] << std::endl;
}

The overhead is a vector of structures containing a pointer and a bool, but what is sorted is actually the original 2D array.

Of course, as the C library is accessible from C++, qsort would certainly be easier for sorting a C compatible 2D array. But this way allows the use of stable_sort or partial_sort if they are relevant.