Сортировка 2-D массива в C ++ с использованием встроенной функции std :: sort

Question

У меня есть матрица вида pMat[M][N] (где M и N переменные и, следовательно, вводимые пользователем).Я хочу отсортировать элементы 2-D массива, используя встроенную функцию std::sort.

Например, рассмотрим следующий массив:

5 9 6
8 1 3
7 2 4

Он должен быть выведен как:

1 2 3
4 5 6
7 8 9

Ниже приведен код, который я написал для этой цели:

#include <iostream>
#include <algorithm>

int main() {
    int M, N, **pMat;
    std::cin >> M >> N;
    pMat = new int* [M];
    for (int i=0; i<M; i++){
        pMat[i] = new int[N];
    }
    for (int i=0; i<M; i++){
        for (int j=0; j<N; j++){
            std::cin >> pMat[i][j];
        }
    }
    std::sort(&pMat[0][0], (&pMat[0][0])+(M*N));
    for (int i=0; i<M; i++){
        for (int j=0; j<N; j++){
            std::cout << pMat[i][j] << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}

Я написал приведенный выше код, исходя из следующего понимания:

1. Массивыв C++ хранятся в смежных ячейках памяти
2. std::sort(add1,add2) сортирует все элементы, присутствующие в ячейках памяти [add1,add2)

Приведенный выше код не дает правильного вывода,Например, когда предоставляется следующий вход:

4 3
13 2 1
4 5 6
7 8 9
10 11 12

, он отображает следующий вывод:

0 0 0 
5 6 13 
7 8 9 
10 11 12

Как мне написать код?И где мое понимание неверно?

(Для информации я посмотрел следующий ответ: Сортировка 2D-массива в C ++ с использованием встроенных функций (или любого другого метода)? , но этоне отвечает на мой запрос)

Answer 1

Как сказал @alter_igel.У вас проблема с не непрерывным массивом.Здесь исправлено.

#include <iostream>
#include <algorithm>

int main() {

    int M, N, *pMat;
    std::cin >> M >> N;

    pMat = new int[M*N];

    for (int i=0; i<M; i++){
        for (int j=0; j<N; j++){
            std::cin >> pMat[i*N+j];
        }
    }
        std::cout << std::endl;

    std::sort(pMat, pMat+(M*N));

    for (int i=0; i<M; i++){
        for (int j=0; j<N; j++){
            std::cout << pMat[i*N+j] << " ";
        }
        std::cout << std::endl;
    }
    return 0;
}

Answer 2

Один из способов сделать это - создать один большой массив непрерывной (сортируемой) памяти и затем обращаться к этому массиву как массив подмассивов через секунду массив указателей.

Второй массив просто содержит список указателей, каждый из которых указывает на отдельный подмассив внутри большего.

Примерно так:

int M, N;

std::cin >> M >> N;

// one big array of actual data
// (an array of contiguous sub-arrays)
std::vector<int> v(M * N);

// array of pointers to sub-arrays within the actual data
std::vector<int*> pMat;

// point the pointers at the actual data
// each pointer pointing to the relevant sub-array
for(int i = 0; i < M; i++)
    pMat.push_back(v.data() + (i * N));

// get the input, changing the actual data
// through the pointers
for(int i = 0; i < M; i++)
    for(int j = 0; j < N; j++)
        std::cin >> pMat[i][j];

// sort the actual data
std::sort(std::begin(v), std::end(v));

// look at the data through the sub-array pointers
for(int i = 0; i < M; i++)
{
    for(int j = 0; j < N; j++)
        std::cout << pMat[i][j] << " ";
    std::cout << '\n';
}

return 0;

Примечание: Я использовал std::vector для управления массивами, но он также будет работать со встроенными массивами, созданными с помощью new[] и delete[] (не рекомендуется).

РЕДАКТИРОВАТЬ: Для добавления.

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

template<typename T>
class two_dee_array
{
public:
    two_dee_array(std::size_t M, std::size_t N): v(M * N), stride(N) {}

    T& operator()(std::size_t M, std::size_t N)
        { return v[(M * stride) + N]; }

    T const& operator()(std::size_t M, std::size_t N) const
        { return v[(M * stride) + N]; }

    std::size_t col_size() const { return stride; }
    std::size_t row_size() const { return v.size() / stride; }

    auto begin() { return std::begin(v); }
    auto end() { return std::end(v); }

    auto begin() const { return std::begin(v); }
    auto end() const { return std::end(v); }

    auto cbegin() const { return std::cbegin(v); }
    auto cend() const { return std::cend(v); }

private:
    std::vector<int> v;
    std::size_t stride;
};

int main()
{
    int M, N;

    std::cin >> M >> N;

    two_dee_array<int> v(M, N);

    for(int i = 0; i < M; i++)
        for(int j = 0; j < N; j++)
            std::cin >> v(i, j);

    std::sort(std::begin(v), std::end(v));

    for(int i = 0; i < M; i++)
    {
        for(int j = 0; j < N; j++)
            std::cout << v(i, j) << " ";
        std::cout << '\n';
    }
}