How do I best handle dynamic multi-dimensional arrays in C/C++?

Question

What is the accepted/most commonly used way to manipulate dynamic (with all dimensions not known until runtime) multi-dimensional arrays in C and/or C++.

I'm trying to find the cleanest way to accomplish what this Java code does:

public static void main(String[] args){
 Scanner sc=new Scanner(System.in);
 int rows=sc.nextInt();
 int cols=sc.nextInt();
 int[][] data=new int[rows][cols];
 manipulate(data);
}

public static void manipulate(int[][] data){
   for(int i=0;i<data.length;i++)
   for(int j=0;j<data[0].length.j++){
         System.out.print(data[i][j]);       
   }    
}

(reads from std_in just to clarify that dimensions aren't known until runtime).

Edit:I noticed that this question is pretty popular even though it's pretty old. I don't actually agree with the top voted answer. I think the best choice for C is to use a single-dimensional array as Guge said below "You can alloc rowscolssizeof(int) and access it by table[row*cols+col].".

There is a number of choices with C++, if you really like boost or stl then the answers below might be preferable, but the simplest and probably fastest choice is to use a single dimensional array as in C.

Another viable choice in C and C++ if you want the [][] syntax is lillq's answer down at the bottom is manually building the array with lots of malloc's.

Answer 1

Use boost::multi_array.

As in your example, the only thing you need to know at compile time is the number of dimensions. Here is the first example in the documentation :

#include "boost/multi_array.hpp"
#include <cassert>

int 
main () {
  // Create a 3D array that is 3 x 4 x 2
  typedef boost::multi_array<double, 3> array_type;
  typedef array_type::index index;
  array_type A(boost::extents[3][4][2]);

  // Assign values to the elements
  int values = 0;
  for(index i = 0; i != 3; ++i) 
    for(index j = 0; j != 4; ++j)
      for(index k = 0; k != 2; ++k)
        A[i][j][k] = values++;

  // Verify values
  int verify = 0;
  for(index i = 0; i != 3; ++i) 
    for(index j = 0; j != 4; ++j)
      for(index k = 0; k != 2; ++k)
        assert(A[i][j][k] == verify++);

  return 0;
}

Edit: As suggested in the comments, here is a "simple" example application that let you define the multi-dimensional array size at runtime, asking from the console input. Here is an example output of this example application (compiled with the constant saying it's 3 dimensions) :

Multi-Array test!
Please enter the size of the dimension 0 : 4

Please enter the size of the dimension 1 : 6

Please enter the size of the dimension 2 : 2

Text matrix with 3 dimensions of size (4,6,2) have been created.

Ready!
Type 'help' for the command list.

>read 0.0.0
Text at (0,0,0) :
  ""

>write 0.0.0 "This is a nice test!"
Text "This is a nice test!" written at position (0,0,0)

>read 0.0.0
Text at (0,0,0) :
  "This is a nice test!"

>write 0,0,1 "What a nice day!"
Text "What a nice day!" written at position (0,0,1)

>read 0.0.0
Text at (0,0,0) :
  "This is a nice test!"

>read 0.0.1
Text at (0,0,1) :
  "What a nice day!"

>write 3,5,1 "This is the last text!"
Text "This is the last text!" written at position (3,5,1)

>read 3,5,1
Text at (3,5,1) :
  "This is the last text!"

>exit

The important parts in the code are the main function where we get the dimensions from the user and create the array with :

const unsigned int DIMENSION_COUNT = 3; // dimension count for this test application, change it at will :)

// here is the type of the multi-dimensional (DIMENSION_COUNT dimensions here) array we want to use
// for this example, it own texts
typedef boost::multi_array< std::string , DIMENSION_COUNT > TextMatrix;

// this provide size/index based position for a TextMatrix entry.
typedef std::tr1::array<TextMatrix::index, DIMENSION_COUNT> Position; // note that it can be a boost::array or a simple array

/*  This function will allow the user to manipulate the created array
    by managing it's commands.
    Returns true if the exit command have been called.
*/
bool process_command( const std::string& entry, TextMatrix& text_matrix );

/* Print the position values in the standard output. */
void display_position( const Position& position );

int main()
{
    std::cout << "Multi-Array test!" << std::endl;

    // get the dimension informations from the user
    Position dimensions; // this array will hold the size of each dimension 

    for( int dimension_idx = 0; dimension_idx < DIMENSION_COUNT; ++dimension_idx )
    {
        std::cout << "Please enter the size of the dimension "<< dimension_idx <<" : ";
        // note that here we should check the type of the entry, but it's a simple example so lets assume we take good numbers
        std::cin >> dimensions[dimension_idx]; 
        std::cout << std::endl;

    }

    // now create the multi-dimensional array with the previously collected informations
    TextMatrix text_matrix( dimensions );

    std::cout << "Text matrix with " << DIMENSION_COUNT << " dimensions of size ";
    display_position( dimensions );
    std::cout << " have been created."<< std::endl;
    std::cout << std::endl;
    std::cout << "Ready!" << std::endl;
    std::cout << "Type 'help' for the command list." << std::endl;
    std::cin.sync();


    // we can now play with it as long as we want
    bool wants_to_exit = false;
    while( !wants_to_exit )
    {
        std::cout << std::endl << ">" ;
        std::tr1::array< char, 256 > entry_buffer; 
        std::cin.getline(entry_buffer.data(), entry_buffer.size());

        const std::string entry( entry_buffer.data() );
        wants_to_exit = process_command( entry, text_matrix );
    }

    return 0;
}

And you can see that to accede an element in the array, it's really easy : you just use the operator() as in the following functions :

void write_in_text_matrix( TextMatrix& text_matrix, const Position& position, const std::string& text )
{
    text_matrix( position ) = text;
    std::cout << "Text \"" << text << "\" written at position ";
    display_position( position );
    std::cout << std::endl;
}

void read_from_text_matrix( const TextMatrix& text_matrix, const Position& position )
{
    const std::string& text = text_matrix( position );
    std::cout << "Text at ";
    display_position(position);
    std::cout << " : "<< std::endl;
    std::cout << "  \"" << text << "\"" << std::endl;
}

Note : I compiled this application in VC9 + SP1 - got just some forgettable warnings.

Answer 2

There are two ways to represent a 2-dimension array in C++. One being more flexible than the other.

Array of arrays

First make an array of pointers, then initialize each pointer with another array.

// First dimension
int** array = new int*[3];
for( int i = 0; i < 3; ++i )
{
    // Second dimension
    array[i] = new int[4];
}

// You can then access your array data with
for( int i = 0; i < 3; ++i )
{
    for( int j = 0; j < 4; ++j )
    {
        std::cout << array[i][j];
    }
}

THe problem with this method is that your second dimension is allocated as many arrays, so does not ease the work of the memory allocator. Your memory is likely to be fragmented resulting in poorer performance. It provides more flexibility though since each array in the second dimension could have a different size.

Big array to hold all values

The trick here is to create a massive array to hold every data you need. The hard part is that you still need the first array of pointers if you want to be able to access the data using the array[i][j] syntax.

int* buffer = new int[3*4];   
int** array = new int*[3];

for( int i = 0; i < 3; ++i )
{
    array[i] = buffer + i * 4;
}

The int* array is not mandatory as you could access your data directly in buffer by computing the index in the buffer from the 2-dimension coordinates of the value.

// You can then access your array data with
for( int i = 0; i < 3; ++i )
{
    for( int j = 0; j < 4; ++j )
    {
        const int index = i * 4 + j;
        std::cout << buffer[index];
    }
}

The RULE to keep in mind

Computer memory is linear and will still be for a long time. Keep in mind that 2-dimension arrays are not natively supported on a computer so the only way is to "linearize" the array into a 1-dimension array.

Answer 3

Here is the easy way to do this in C:

void manipulate(int rows, int cols, int (*data)[cols]) {
    for(int i=0; i < rows; i++) {
        for(int j=0; j < cols; j++) {
            printf("%d ", data[i][j]);       
        }
        printf("\n");
    }
}

int main() {
    int rows = ...;
    int cols = ...;
    int (*data)[cols] = malloc(rows*sizeof(*data));
    manipulate(rows, cols, data);
    free(data);
}

This is perfectly valid since C99, however it is not C++ of any standard: C++ requires the sizes of array types to be compile times constants. In that respect, C++ is now fifteen years behind C. And this situation is not going to change any time soon (the variable length array proposal for C++17 does not come close to the functionality of C99 variable length arrays).

Answer 4

You can alloc rowscolssizeof(int) and access it by table[row*cols+col].

Answer 5

The standard way without using boost is to use std::vector :

std::vector< std::vector<int> > v;
v.resize(rows, std::vector<int>(cols, 42)); // init value is 42
v[row][col] = ...;

That will take care of new / delete the memory you need automatically. But it's rather slow, since std::vector is not primarily designed for using it like that (nesting std::vector into each other). For example, all the memory is not allocated in one block, but separate for each column. Also the rows don't have to be all of the same width. Faster is using a normal vector, and then doing index calculation like col_count * row + col to get at a certain row and col:

std::vector<int> v(col_count * row_count, 42);
v[col_count * row + col) = ...;

But this will loose the capability to index the vector using [x][y]. You also have to store the amount of rows and cols somewhere, while using the nested solution you can get the amount of rows using v.size() and the amount of cols using v[0].size().

Using boost, you can use boost::multi_array, which does exactly what you want (see the other answer).

---

There is also the raw way using native C++ arrays. This envolves quite some work and is in no way better than the nested vector solution:

int ** rows = new int*[row_count];
for(std::size_t i = 0; i < row_count; i++) {
    rows[i] = new int[cols_count];
    std::fill(rows[i], rows[i] + cols_count, 42);
}

// use it... rows[row][col] then free it...

for(std::size_t i = 0; i < row_count; i++) {
    delete[] rows[i];
}

delete[] rows;

You have to store the amount of columns and rows you created somewhere since you can't receive them from the pointer.

Answer 6

2D C-style arrays in C and C++ are a block of memory of size rows * columns * sizeof(datatype) bytes.

The actual [row][column] dimensions exist only statically at compile time. There's nothing there dynamically at runtime!

So, as others have mentioned, you can implement

  int array [ rows ] [ columns ];

As:

 int  array [ rows * columns ]

Or as:

 int * array = malloc ( rows * columns * sizeof(int) );

---

Next: Declaring a variably sized array. In C this is possible:

int main( int argc, char ** argv )
{
  assert( argc > 2 );

  int rows    = atoi( argv[1] );
  int columns = atoi( argv[2] );

  assert(rows > 0 && columns > 0);
  int data [ rows ] [ columns ];  // Yes, legal!

  memset( &data, 0, sizeof(data) );

  print( rows, columns, data );
  manipulate( rows, columns, data );
  print( rows, columns, data );
}

---

In C you can just pass the variably-sized array around the same as a non-variably-sized array:

void manipulate( int theRows, int theColumns, int theData[theRows][theColumns] )
{
  for (   int r = 0; r < theRows;    r ++ )
    for ( int c = 0; c < theColumns; c ++  )
      theData[r][c] = r*10 + c;
}

However, in C++ that is not possible. You need to allocate the array using dynamic allocation, e.g.:

int *array = new int[rows * cols]();

or preferably (with automated memory management)

std::vector<int> array(rows * cols);

Then the functions must be modified to accept 1-dimensional data:

void manipulate( int theRows, int theColumns, int *theData )
{
  for (   int r = 0; r < theRows;    r ++ )
    for ( int c = 0; c < theColumns; c ++  )
      theData[r * theColumns + c] = r*10 + c;
}

Answer 7

If you're using C instead of C++ you might want to look at the Array_T abstraction in Dave Hanson's library C Interfaces and Implementations. It's exceptionally clean and well designed. I have my students do a two-dimensional version as an exercise. You could do that or simply write an additional function that does an index mapping, e.g.,

void *Array_get_2d(Array_T a, int width, int height, int i, int j) {
    return Array_get(a, j * width, i, j);
}

It is a bit cleaner to have a separate structure where you store the width, the height, and a pointer to the elements.

Answer 8

I recently came across a similar problem. I did not have Boost available. Vectors of vectors turned out to be pretty slow in comparison to plain arrays. Having an array of pointers makes the initialization a lot more laborious, because you have to iterate through every dimension and initialize the pointers, possibly having some pretty unwieldy, cascaded types in the process, possibly with lots of typedefs.

DISCLAIMER: I was not sure if I should post this as an answer, because it only answers part of your question. My apologies for the following:

• I did not cover how to read the dimensions from standard input, as other commentators had remarked.
• This is primarily for C++.
• I have only coded this solution for two dimensions.

I decided to post this anyway, because I see vectors of vectors brought up frequently in reply to questions about multi-dimensional arrays in C++, without anyone mentioning the performance aspects of it (if you care about it).

I also interpreted the core issue of this question to be about how to get dynamic multi-dimensional arrays that can be used with the same ease as the Java example from the question, i.e. without the hassle of having to calculate the indices with a pseudo-multi-dimensional one-dimensional array.

I didn't see compiler extensions mentioned in the other answers, like the ones provided by GCC/G++ to declare multi-dimensional arrays with dynamic bounds the same way you do with static bounds. From what I understand, the question does not restrict the answers to standard C/C++. ISO C99 apparently does support them, but in C++ and prior versions of C they appear to be compiler-specific extensions. See this question: Dynamic arrays in C without malloc?

I came up with a way that people might like for C++, because it's little code, has the ease of use of the built-in static multi-dimensional arrays, and is just as fast.

template <typename T> 
class Array2D {
private:
    std::unique_ptr<T> managed_array_;
    T* array_;
    size_t x_, y_;

public:
    Array2D(size_t x, size_t y) {
        managed_array_.reset(new T[x * y]);
        array_ = managed_array_.get();
        y_ = y;
    }
    T* operator[](size_t x) const {
        return &array_[x * y_];
    }
};

You can use it like this. The dimensions do not

auto a = Array2D<int>(x, y);
a[xi][yi] = 42;

You can add an assertion, at least to all but the last dimension and extend the idea to to more than two dimensions. I have made a post on my blog about alternative ways to get multi-dimensional arrays. I am also much more specific on the relative performance and coding effort there.

Performance of Dynamic Multi-Dimensional Arrays in C++

Answer 9

You could use malloc to accomplish this and still have it accessible through normal array[][] mean, verses the array[rows * cols + cols] method.

main()
{
   int i;
   int rows;
   int cols;
   int **array = NULL;

   array = malloc(sizeof(int*) * rows);
   if (array == NULL)
       return 0;  // check for malloc fail

   for (i = 0; i < rows; i++)
   {
       array[i] = malloc(sizeof(int) * cols)
       if (array[i] == NULL)
           return 0;  // check for malloc fail
   }

   // and now you have a dynamically sized array
}

Answer 10

There is no way to determine the length of a given array in C++. The best way would probably be to pass in the length of each dimension of the array, and use that instead of the .length property of the array itself.