How do you dynamically allocate a matrix?
https://stackoverflow.com/questions/1403150
-
05-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
How do you dynamically allocate a 2D matrix in C++? I have tried based on what I already know:
#include <iostream>
int main(){
int rows;
int cols;
int * arr;
arr = new int[rows][cols];
}
It works for one parameter, but now for two. What should I do?
Solution
A matrix is actually an array of arrays.
int rows = ..., cols = ...;
int** matrix = new int*[rows];
for (int i = 0; i < rows; ++i)
matrix[i] = new int[cols];
Of course, to delete the matrix, you should do the following:
for (int i = 0; i < rows; ++i)
delete [] matrix[i];
delete [] matrix;
I have just figured out another possibility:
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;
}
Freeing this array is easier:
if (rows) delete [] matrix[0];
delete [] matrix;
This solution has the advantage of allocating a single big block of memory for all the elements, instead of several little chunks. The first solution I posted is a better example of the arrays of arrays concept, though.
OTHER TIPS
You can also use std::vectors for achieving this:
using std::vector< std::vector<int> >
Example:
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];
}
}
#include <boost/multi_array.hpp>
int main(){
int rows;
int cols;
boost::multi_array<int, 2> arr(boost::extents[rows][cols] ;
}
#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;
}
arr = new int[cols*rows];
If you either don't mind syntax
arr[row * cols + col] = Aij;
or use operator[] overaloading somewhere. This may be more cache-friendly than array of arrays, or may be not, more probably you shouldn't care about it. I just want to point out that a) array of arrays is not only solution, b) some operations are more easier to implement if matrix located in one block of memory. E.g.
for(int i=0;i < rows*cols;++i)
matrix[i]=someOtherMatrix[i];
one line shorter than
for(int r=0;i < rows;++r)
for(int c=0;i < cols;++s)
matrix[r][c]=someOtherMatrix[r][c];
though adding rows to such matrix is more painful
or you can just allocate a 1D array but reference elements in a 2D fashion:
to address row 2, column 3 (top left corner is row 0, column 0):
arr[2 * MATRIX_WIDTH + 3]
where MATRIX_WIDTH is the number of elements in a row.
The other answer describing arrays of arrays are correct.
BUT if you are planning of doing a anything mathematical with the arrays - or need something special like sparse matrices you should look at one of the many maths libs like TNT before re-inventing too many wheels
I have this grid class that can be used as a simple matrix if you don't need any mathematical operators.
/**
* 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;
}
Using the double-pointer is by far the best compromise between execution speed/optimisation and legibility. Using a single array to store matrix' contents is actually what a double-pointer does.
I have successfully used the following templated creator function (yes, I know I use old C-style pointer referencing, but it does make code more clear on the calling side with regards to changing parameters - something I like about pointers which is not possible with references. You will see what I mean):
///
/// 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;
}
}
}
}
}
To de-allocate the memory created using the abovementioned utility, one simply has to de-allocate in reverse.
///
/// 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;
}
}
}
To use these abovementioned template functions is then very easy (e.g.):
.
.
.
double l_ppMatrix = 0;
NewMatrix(&l_ppMatrix, 3, 3); // Create a 3 x 3 Matrix and store it in l_ppMatrix.
.
.
.
DeleteMatrix(&l_ppMatrix);
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;
Here is the most clear & intuitive way i know to allocate a dynamic 2d array in C++. Templated in this example covers all cases.
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);
...
}
