使用内置的std :: sort函数在C ++中对二维数组进行排序 [英] Sorting 2-D array in C++ using inbuilt std::sort function

问题描述

我有一个格式为pMat[M][N]的矩阵(其中M和N是可变的，因此是用户输入的).我想使用内置的std::sort函数对二维数组的元素进行排序.

I have a matrix of the form pMat[M][N] (where M and N are variable and, hence, input from the user). I want to sort the elements of the 2-D array using the inbuilt std::sort function.

例如，考虑以下数组:

5 9 6
8 1 3
7 2 4

它的输出应为:

1 2 3
4 5 6
7 8 9

以下是我为此编写的代码:

The following is the code that I wrote for the purpose:

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

我基于以下理解编写了以上代码:

I wrote the above code based on the following understanding:

1. C++中的数组存储在连续的内存位置中
2. std::sort(add1,add2)对内存位置[add1,add2)
中存在的所有元素进行排序

1. Arrays in C++ are stored in contiguous memory locations
2. std::sort(add1,add2) sorts all the elements present in the memory locations [add1,add2)

上面的代码没有给出正确的输出.例如，当提供以下输入时:

The above code doesn't give the correct output. For example, when provided with the following input:

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

我该如何编写代码?我的理解错在哪里?

How can I go about writing the code? And where is my understanding wrong?

(有关信息，我查看了以下答案:

(For information, I looked at the following answer: Sort a 2D array in C++ using built in functions(or any other method)? , but it does not answer my query)

推荐答案

一种方法是创建一个大的连续数组(可排序)的数组，然后将该数组作为第二个指针数组的子数组.

One way to do this is to create one big array of contiguous (sortable) memory and then access that array as an array of sub-arrays through a second array of pointers.

第二个数组仅包含一个指针列表，每个指针指向较大的指针中的一个不同子数组.

The second array simply contains a list of pointers, each one pointing to a different sub-array within the larger one.

类似这样的东西:

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[]创建的内置阵列(不推荐).

Note: I used std::vector to manage my arrays but it will also work with built in arrays created with new[] and delete[] (not recommended).

编辑:要添加.

或者(更好的是 )，您可以创建一个类，该类将数据存储在一个大的连续块中，并使用如下所示的数学偏移量访问不同的子数组:

Alternatively (much better) you can create a class that will store the data in a big contiguous block and access the different sub-arrays using mathematical offsets like this:

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

这篇关于使用内置的std :: sort函数在C ++中对二维数组进行排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！