Declare a multidimentional array without the size

Question

I want to declare an array of arrays or multidimensional array without knowing the size.

I want to do something similar to what I did in this cases with simple arrays:

int *array;
cin >> size;
array = new int[size];

Maybe I can loop to initialize a pointer of pointers like this:

int **array;
cin >> rows >> col;
array = new *int[rows]
for (int i = 0; i < rows; ++i)
    array[i] = new int[col];

But I would prefer to not do this if a better solution exists.

Solution 1

Why not use std::vector?

std::vector<std::vector<int> > array;

If you don't want to use an array of pointers, you could use one large array that you allocate dynamically after you get the size and access it as an array of rows.

int rows = 10;
int columns = 20;

int* array = new int[rows * columns];

for (int count = 0; count < rows; count++)
{
   int* row = &array[count * columns];

   for (int inner_count = 0; inner_count < columns; inner_count++)
   {
      int* element = &row[inner_count];

      //do something
   }
}

delete [] array;

Solution 2

You're pretty much going to have to go with the loop version. You can make one slight improvement, which is to allocate one big block and then build your own int* index into it:

int **array;
int *storage;
cin >> rows >> col;
array = new *int[rows];
storage = new int[rows*col];
for (int i = 0; i < rows; ++i)
    array[i] = storage + col * i;

This has the nice property that you can still use array[i][j] syntax for accessing the array.

Solution 3

You could use a single std::vector to contain the entire two dimensional array and wrap it in a class to hide the details. Here's an example, it uses a data( row, col ) member function that returns a reference to the element at row and col. I included an example 2 dimensional matrix of int where each entry in the array is initialized to the product of its row and col. When an instance of this class goes out of scope, the default destructor will get called and release the memory, that way you don't have to remember to call delete[] to release the memory. All elements of the matrix will be contiguous in memory, this is cache friendly and should give you good performance.

#include <iostream>
#include <vector>
#include <stdexcept>

template <typename T>
class matrix {
    std::vector<T> data_;
public:
    size_t const rows_;
    size_t const cols_;
    matrix(size_t rows, size_t cols)
        : rows_(rows)
        , cols_(cols)
        , data_( rows * cols )
    {}
    T& data( size_t row, size_t col ) {
        if (row > rows_ || col > cols_) throw std::out_of_range("matrix");
        return data_[ row * cols_ + col ];
    }
};

int main( int argc, char** argv )
{
    matrix<int> array(100,100);

    for(size_t r=0; r < array.rows_; ++r) {
        for(size_t c=0; c < array.cols_; ++c) {
            array.data(r,c) = r * c;
        }
    }

    std::cout << "8 x 7 = " << array.data(8,7) << std::endl;

    return 0; // array goes out of scope here, memory released automatically
}

When you run this you will get

8 x 7 = 56

Comments

[Ed S.]

Don't use a vector of vectors if the code in question is performance sensitive. You will face tons of cache misses when compared to a single large block of memory.

[blackløtus]

@EdS.yea this is one of the reasons and I want to try to do this without use a loop to initialize it.