如何动态分配矩阵？

Question

如何在C++中动态分配二维矩阵？ 我已经尝试了我所知道的方法：

#include <iostream>

int main(){
    int rows;
    int cols;
    int * arr;
    arr = new int[rows][cols];
 }

一个参数时它能正常工作，但两个参数就不行了。我该怎么办？

- chustar

---

一遍又一遍地做：https://dev59.com/gnRC5IYBdhLWcg3wP-dh https://dev59.com/O0bRa4cB1Zd3GeqP039S 以及其他。 - dmckee --- ex-moderator kitten

回想起来，其他一些答案比我的好得多。（我仍然不懂C++，但至少现在我知道自己不懂C++了。）现在能否接受其中一个答案呢？ - isekaijin

Answer 1

一个矩阵可以表示为一个数组的数组。

int rows = ..., cols = ...;
int** matrix = new int*[rows];
for (int i = 0; i < rows; ++i)
    matrix[i] = new int[cols];

当然，要删除矩阵，你应该执行以下操作：

for (int i = 0; i < rows; ++i)
    delete [] matrix[i];
delete [] matrix;

---

我刚刚想到了另外一个可能性:

int rows = ..., cols = ...;
int** matrix = new int*[rows];
if (rows)
{
    matrix[0] = new int[rows * cols];
    for (int i = 1; i < rows; ++i)
        matrix[i] = matrix[0] + i * cols;
}

释放该数组更加简单：

if (rows) delete [] matrix[0];
delete [] matrix;

这种解决方案的优点在于为所有元素分配单个大块内存，而不是多个小块。我发布的第一种解决方案是更好地说明了“数组的数组”概念。

- pyon

---

出于清晰的考虑，我更倾向于第一个选项。 - Patrizio Bertoni

@PatrizioBertoni：显然我更喜欢第二种方法。有一个巧妙的技巧可以将任意n维矩阵M存储为两个一维数组c（系数）和x（实际元素）。然后，给定一个索引向量i，M的第i个元素就是x的第c*i个元素，其中*表示点积。我喜欢这个技巧，因为（0）它适用于任意的n，（1）它说明了从0开始的索引的重要性，（2）对于那些关心线性代数的人来说，它揭示了张量积的奥秘... :-p - isekaijin

为什么我们需要先释放每一行？我们为什么不能只是 delete [] matrix？ - CutePoison

在第一种可能性中，每行都被分配为一个单独的内存块。 - isekaijin

为什么在分配/删除之前需要 if (rows)？ - LCsa

Answer 2

你也可以使用 std::vector 来实现这个功能：

使用：'std::vector< std::vector >'

例子：

#include <vector>
std::vector< std::vector<int> > a;
  
  //m * n is the size of the matrix

    int m = 2, n = 4;
    //Grow rows by m
    a.resize(m);
    for(int i = 0 ; i < m ; ++i)
    {
        //Grow Columns by n
        a[i].resize(n);
    }
    //Now you have matrix m*n with default values

    //you can use the Matrix, now
    a[1][0]=1;
    a[1][1]=2;
    a[1][2]=3;
    a[1][3]=4;

//OR
for(i = 0 ; i < m ; ++i)
{
    for(int j = 0 ; j < n ; ++j)
    {      //modify matrix
        int x = a[i][j];
    }

}

- aJ.

---

使用std::vector值得肯定。我个人不常使用STL，但那是因为在内存管理方面我自虐。使用STL会少出现错误。 - isekaijin

虽然这个方法可行，但需要重复手动操作。你可以使用预定义的类（有很多种），或者自己设计一个类来封装C风格的n维数组。 - dmckee --- ex-moderator kitten

不要调整大小，只需使用正确的尺寸构建它。 int m = 10, n = 4; std::vector< std::vector<int> > a(m, std::vector<int>(n,0)); - TimW

Answer 3

尝试使用boost::multi_array

#include <boost/multi_array.hpp>

int main(){
    int rows;
    int cols;
    boost::multi_array<int, 2> arr(boost::extents[rows][cols] ;
}

- yoco

---

+1 for使用 Boost，但是使用这样的库取决于您使用的编译器优化代码的能力。 - isekaijin

Answer 4

arr = new int[cols*rows];

如果您不介意语法问题

arr[row * cols + col] = Aij;

或者在某些地方使用运算符[]重载。这可能比数组更加缓存友好，也可能不是，更可能的是您不应该关心它。我只是想指出：a）数组不是唯一的解决方案；b）如果矩阵位于一个内存块中，则某些操作更容易实现。

for(int i=0;i < rows*cols;++i)
   matrix[i]=someOtherMatrix[i];

比一行短

for(int r=0;i < rows;++r)
  for(int c=0;i < cols;++s)
     matrix[r][c]=someOtherMatrix[r][c];

虽然向这样的矩阵添加行更加痛苦

- maykeye

Answer 5

const int nRows = 20;
const int nCols = 10;
int (*name)[nCols] = new int[nRows][nCols];
std::memset(name, 0, sizeof(int) * nRows * nCols); //row major contiguous memory
name[0][0] = 1; //first element
name[nRows-1][nCols-1] = 1; //last element
delete[] name;

- sballot

---

一些解释会非常完美！;) - Andreas

@Andreas - name 是一个大小为 nCols 的数组的指针，这里是一个指向矩阵第一行的指针。name+i 将会是指向矩阵中第 i 行的指针。 - rcgldr

@rcgldr 谢谢，但我完全理解这段代码。如果有人在很多年后添加了一个额外的答案，即使已经有很多答案，甚至是被接受的答案，那么如果该答案能够快速解释它与现有答案的不同之处，那将是非常有价值的。 - Andreas

@Andreas - 我在上一条评论中失去了一个编辑。如果列数固定，那么这种方法才有效。否则，指针数组似乎是最好的选择。为整个矩阵进行单个分配，并为指针数组进行单个分配仅需要两个分配。如果行数有最大值，则指针数组可以是矩阵类中的固定大小数组，只需要对数据进行单个分配。 - rcgldr

@Andreas - 我写了一个矩阵类，允许嵌入矩阵。嵌入矩阵构造函数有一个额外的参数，指向另一个矩阵中的某一行的指针，它用于初始化嵌入矩阵的指针数组。 - rcgldr

Answer 6

 #include <iostream>

    int main(){
        int rows=4;
        int cols=4;
        int **arr;

        arr = new int*[rows];
        for(int i=0;i<rows;i++){
           arr[i]=new int[cols];
        }
        // statements

        for(int i=0;i<rows;i++){
           delete []arr[i];
        }
        delete []arr;
        return 0;
     }

- KV Prajapati

Answer 7

这是我所知道的最清晰直观的方法来在C++中分配动态二维数组。在此示例中，使用模板涵盖了所有情况。

template<typename T> T** matrixAllocate(int rows, int cols, T **M)
{
    M = new T*[rows];
    for (int i = 0; i < rows; i++){
        M[i] = new T[cols];
    }
    return M;
}

... 

int main()
{
    ...
    int** M1 = matrixAllocate<int>(rows, cols, M1);
    double** M2 = matrixAllocate(rows, cols, M2);
    ...
}

- KeyC0de

Answer 8

或者你可以只分配一个一维数组，但以二维方式引用元素：

要访问第2行第3列（左上角为第0行第0列）：

arr[2 * MATRIX_WIDTH + 3]

其中MATRIX_WIDTH是一行中的元素数量。

- DmitryK

---

为什么要费力地去“hack up”一个二维数组，而不是直接创建一个真正的二维数组呢？ - Chris Lutz

当性能真正关键时，因为您可以以缓存友好的方式访问二维方式。 - DeusAduro

更好的方法是：分配一个一维元素数组和另一个一维指向每行第一个元素的指针数组。 - isekaijin

Answer 9

我有一个网格类，如果您不需要任何数学运算符，它可以用作简单矩阵。

/**
 * Represents a grid of values.
 * Indices are zero-based.
 */
template<class T>
class GenericGrid
{
    public:
        GenericGrid(size_t numRows, size_t numColumns);

        GenericGrid(size_t numRows, size_t numColumns, const T & inInitialValue);

        const T & get(size_t row, size_t col) const;

        T & get(size_t row, size_t col);

        void set(size_t row, size_t col, const T & inT);

        size_t numRows() const;

        size_t numColumns() const;

    private:
        size_t mNumRows;
        size_t mNumColumns;
        std::vector<T> mData;
};


template<class T>
GenericGrid<T>::GenericGrid(size_t numRows, size_t numColumns):
    mNumRows(numRows),
    mNumColumns(numColumns)
{
    mData.resize(numRows*numColumns);
}


template<class T>
GenericGrid<T>::GenericGrid(size_t numRows, size_t numColumns, const T & inInitialValue):
    mNumRows(numRows),
    mNumColumns(numColumns)
{
    mData.resize(numRows*numColumns, inInitialValue);
}


template<class T>
const T & GenericGrid<T>::get(size_t rowIdx, size_t colIdx) const
{
    return mData[rowIdx*mNumColumns + colIdx];
}


template<class T>
T & GenericGrid<T>::get(size_t rowIdx, size_t colIdx)
{
    return mData[rowIdx*mNumColumns + colIdx];
}


template<class T>
void GenericGrid<T>::set(size_t rowIdx, size_t colIdx, const T & inT)
{
    mData[rowIdx*mNumColumns + colIdx] = inT;
}


template<class T>
size_t GenericGrid<T>::numRows() const
{
    return mNumRows;
}


template<class T>
size_t GenericGrid<T>::numColumns() const
{
    return mNumColumns;
}

- StackedCrooked

Answer 10

使用双指针是执行速度/优化和易读性之间的最佳折衷方案。实际上，使用单个数组存储矩阵内容就是双指针所做的事情。

我成功地使用了以下模板创建函数（是的，我知道我使用旧的C风格指针引用，但这确实使调用方面的代码更清晰，关于更改参数 - 这是我喜欢指针而不是引用的东西。您将看到我的意思）：

///
/// Matrix Allocator Utility
/// @param pppArray Pointer to the double-pointer where the matrix should be allocated.
/// @param iRows Number of rows.
/// @param iColumns Number of columns.
/// @return Successful allocation returns true, else false.
template <typename T>
bool NewMatrix(T*** pppArray, 
               size_t iRows, 
               size_t iColumns)
{
   bool l_bResult = false;
   if (pppArray != 0) // Test if pointer holds a valid address.
   {                  // I prefer using the shorter 0 in stead of NULL.
      if (!((*pppArray) != 0)) // Test if the first element is currently unassigned.
      {                        // The "double-not" evaluates a little quicker in general.
         // Allocate and assign pointer array.
         (*pppArray) = new T* [iRows]; 
         if ((*pppArray) != 0) // Test if pointer-array allocation was successful.
         {
            // Allocate and assign common data storage array.
            (*pppArray)[0] = new T [iRows * iColumns]; 
            if ((*pppArray)[0] != 0) // Test if data array allocation was successful.
            {
               // Using pointer arithmetic requires the least overhead. There is no 
               // expensive repeated multiplication involved and very little additional 
               // memory is used for temporary variables.
               T** l_ppRow = (*pppArray);
               T* l_pRowFirstElement = l_ppRow[0];
               for (size_t l_iRow = 1; l_iRow < iRows; l_iRow++)
               {
                  l_ppRow++;
                  l_pRowFirstElement += iColumns;
                  l_ppRow[0] = l_pRowFirstElement;
               }
               l_bResult = true;
            }
         }
      }
   }
}

使用上述实用程序创建的内存需要释放时，只需按相反的顺序进行释放。

///
/// Matrix De-Allocator Utility
/// @param pppArray Pointer to the double-pointer where the matrix should be de-allocated.
/// @return Successful de-allocation returns true, else false.
template <typename T>
bool DeleteMatrix(T*** pppArray)
{
   bool l_bResult = false;
   if (pppArray != 0) // Test if pointer holds a valid address.
   {
      if ((*pppArray) != 0) // Test if pointer array was assigned.
      {
         if ((*pppArray)[0] != 0) // Test if data array was assigned.
         {
               // De-allocate common storage array.
               delete [] (*pppArray)[0];
            }
         }
         // De-allocate pointer array.
         delete [] (*pppArray);
         (*pppArray) = 0;
         l_bResult = true;
      }
   }
}

使用上述模板函数非常简单（例如）：

   .
   .
   .
   double l_ppMatrix = 0;
   NewMatrix(&l_ppMatrix, 3, 3); // Create a 3 x 3 Matrix and store it in l_ppMatrix.
   .
   .
   .
   DeleteMatrix(&l_ppMatrix);

- Rufus Neethling