Сортировка двумерного массива C с помощью std :: sort

Question

У меня есть 2D массив a[][40].Я пытаюсь отсортировать его, вызывая std::sort, и я написал функцию Compare.Однако C++ хочет, чтобы у меня была сортировка std::vector, а не простой массив, и я хочу, чтобы отсортированный массив сам по себе был a, я не хочу создавать другой массив и сохранять там результаты сортировки.Кажется, есть много способов достичь этого.Я мог бы придумать пять способов, но ни один из них не кажется эффективным и работающим.

1)

Непосредственно используйте std::sort(std::begin(a), std::begin(a) + something, cmp);

Этоне работает, потому что std::begin не знает, как указать начало 2D-массива.Кроме того, он будет неправильно сортироваться, даже если скомпилирован, поскольку 2D-массив - это не массив ссылок на массивы, а последовательные массивы (в отличие от Java)

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

2)

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

Затем скопируйте все обратно в a

Это не работает, потому что это двумерный массив, и его нельзя отсортироватьКстати, используя std::sort.В отличие от первого испытания, этот использует вдвое больше памяти и копирует все дважды (если он работал)!

Детская площадка: 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);

Затем измените порядок a на тот же, что и k;

Идея проста: создать вектор репрезентативных «указателей», отсортировать их (так как функция cmp2 тайно обращается к a и сравнивает значения), а затем заставить a иметь тот же порядок сk.

В итоге цикл переупорядочения будет очень сложным, потребует большой временной переменной.Кроме того, для cmp2 для доступа к значениям a должна быть создана глобальная переменная-указатель, которая указывает на a, что является «плохим» кодом.

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

4)

Для всех unsigned char[40] можно создать структуру, а ее значения можно скопировать в структуры.Операторы сравнения и = должны быть объявлены.После сортировки их можно скопировать обратно в a.

Было бы отличным решением, если бы массивы не нужно было копировать в структуры, чтобы использовать операторы структуры, но им нужнобудут скопированы, поэтому все значения будут скопированы дважды, и будет использоваться память по мере необходимости.

5)

Для всех unsigned char[40], структура, которая имеетуказатель на них можно создать.Они могут быть отсортированы по указанным значениям, и результат может быть сохранен в массиве указателей.

Это, вероятно, лучший вариант, хотя результатом является массив указателей вместо a.Еще одна причина, по которой он хорош, это то, что он перемещает не массивы, а указатели.

Подводя итог, мне нужно отсортировать двумерный массив a[][40] по std::sort, но я пока не решилпо лучшему.Кажется, есть «лучший способ сделать это», о котором я не могу думать.Не могли бы вы помочь мне?

РЕДАКТИРОВАТЬ: Чтобы уточнить, я хочу, чтобы {{3,2}{1,4}} стал {{1,4}{3,2}}

Answer 1

Проблема не в итерации двумерного массива.При условии, что размер столбцов равен constexpr, указатели на массивы являются хорошими итераторами.

Но все алгоритмы сортировки (или мутирования) в C ++ требуют, чтобы базовый тип был перемещаемым, конструируемым и перемещаемым, а массив нельзя назначать,Но упаковки базовых массивов может быть достаточно:

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

Затем вы можете отсортировать C-совместимый 2D-массив с любым алгоритмом сортировки C ++:

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

Накладные расходы - это вектор структурсодержит указатель и логическое значение, но сортируется фактически исходный 2D-массив.

Конечно, поскольку библиотека C доступна из C ++, qsort, безусловно, будет проще для сортировки C-совместимого 2D-массива.,Но этот способ позволяет использовать stable_sort или partial_sort, если они актуальны.