How to Create a Contiguous 2D Array in C++

How to dynamically allocate a contiguous 2D array in C++?

As other answers have said: allocate n * m entries to create the contiguous data, and then it can be wrapped in pointers to create a 2d array.

... absolutely requires use of arrays and NOT vectors ...

I'm not sure if vector is a constraint based on the API being used, or requirements -- but it's worth noting that vector can be used for the memory management of the implementation -- while still using the raw data (which can be accessed by &vec[0] or vec.data(), which returns a pointer to the first element of the array, and can be used with functions accepting raw pointers).

Since this question is about c++, one option is to wrap an array of n * m in a class that acts like a 2-d array while actually being contiguous.

A simple example could be:

class array_2d
{
public:

   array_2d( std::size_t rows, std::size_t columns )
     : m_rows(rows), m_cols(columns), m_array( new char[rows * columns] )
   {
   }

   ~array_2d()
   {
       delete [] m_array;
   }

   // row-major vs column-major is up to your implementation
   T& operator()( std::ptrdiff_t row, std::ptrdiff_t col )
   {
      // optional: do bounds checking, throw std::out_of_range first

      return m_array[row * m_cols + col];
      // alternatively:
      // return m_array[col * m_rows + row];
   }

   // get pointer to the array (for raw calls)
   char* data()
   {
     return m_array;
   }

private:

   char* m_array; 
   std::size_t m_rows;
   std::size_t m_cols;
};

(Ideally char* would be std::unique_ptr<char[]> or std::vector<char> to avoid memory-leak conditions, but since you said vector is not viable, I'm writing this minimally)

This example overloads the call operator (operator()) -- but this could also be a named function like at(...); the choice would be up to you. The use of such type would then be:

auto array = array_2d(5,5); // create 5x5 array
auto& i01 = array(0,1); // access row 0, column 1

Optionally, if the [][] syntax is important to behave like a 2d-array (rather than the (r,c) syntax), you can return a proxy type from a call to an overloaded operator [] (untested):

class array_2d_proxy
{
public:
   array_2d_proxy( char* p ) : m_entry(p){}

   char& operator[]( std::ptrdiff_t col ){ return m_entry[col]; }

private:

   char* m_entry;
};

class array_2d
{
  ...
  array_2d_proxy operator[]( std::ptrdiff_t row )
  {
    return array_2d_proxy( m_array + (row * m_cols) );
  }
  ...
};

This would allow you to have the 'normal' 2d-array syntax, while still being contiguous:

auto& i00 = array[0][0];

2D array as contiguous block of memory

To allocate a contiguous memory, you'll have to use

arr  = malloc(sizeof(int *) * rows);
arrayData = malloc(sizeof(int) * columns * rows);

for(i = 0; i < rows; i++)
     arr[i]  = arrayData + i * columns ;

To deallocate you'll need to have

free( arrData );
free( arr );

See here

Are C multidimensional arrays contiguous without holes?

Yes, it can be obtained by induction. (Just to add, as a suggestion, if that helps, try to think of multi-dimensional arrays as array of arrays.)

For example, consider an array like a[3][3].

• So, a[0][0], a[0][1] and a[0][2] are elements of a[0] and they will be contiguous.

• Next, a[0] and a[1] are elements of a, so it will be contiguous

an so on.

Taken together, a[0][2] and a[1][0] will be residing next to each other, thereby continuing the contiguity.

For better visual representation, see the below illustration.

The array, say int arr[4][5], has four rows, a[0],a[1], a[2] and a[3] and they are contiguous.

Now each of those rows have five columns, like a[n][0], a[n][1], a[n][2], a[n][3], a[n][4] and they are contiguous.

So, the all the elements (and elements of elements) of the array are contiguous.

How to pass a dynamically allocated contiguous 2D array with user-decided size to a function in C11?

The most correct form is this:

int(*matrix)[d][d] = malloc( sizeof(int[d][d]) );

Here it is pretty clear that we are declaring a pointer to a square 2D array of int. However, the reason why this form isn't often used is because de-referencing turns cumbersome: (*matrix)[i][j]. To skip this extra de-referencing, a handy trick is to drop one dimension out of the pointer declaration (and that's what your current code does too):

int(*matrix)[d] = malloc( sizeof(int[d][d]) );

Now we can do a readable matrix[i][j] as expected.

As for how to declare a function, just declare it as using a 2D array because that's what you want:

void fillMatrix (size_t size, int matrix[size][size]);

Now this decays to a pointer to the first element and what is the type of such a pointer? Since the first element is of type int [size] and a pointer to it is int(*)[size], we actually end up with the very same type as was used in main, 100% compatible.

Full example:

#include <stdio.h>
#include <stdlib.h>

void fillMatrix (size_t size, int matrix[size][size])
{
  int k=1;

  for(size_t i=0; i<size; i++)
  {
    for(size_t j=0; j<size; j++)
    {
      matrix[i][j] = k++;
    }
  }
}

void printMatrix (size_t size, int matrix[size][size])
{
  for(size_t i=0; i<size; i++)
  {
    for(size_t j=0; j<size; j++)
    {
      printf("%2.d ", matrix[i][j]);
    }
    puts("");
  }
}

int main (void)
{
  size_t size=5;
  int(*matrix)[size] = malloc( sizeof(int[size][size]) );

  fillMatrix(size, matrix);
  printMatrix(size, matrix);
  
  free(matrix);
}

Further study: Correctly allocating multi-dimensional arrays

How to dynamically allocate a contiguous block of memory for a 2D array

If your array dimensions are known at compile time:

#define ROWS ...
#define COLS ...

int (*arr)[COLS] = malloc(sizeof *arr * ROWS);
if (arr) 
{
  // do stuff with arr[i][j]
  free(arr);
}

If your array dimensions are not known at compile time, and you are using a C99 compiler or a C2011 compiler that supports variable length arrays:

size_t rows, cols;
// assign rows and cols
int (*arr)[cols] = malloc(sizeof *arr * rows);
if (arr)
{
  // do stuff with arr[i][j]
  free(arr);
}

If your array dimensions are not known at compile time, and you are not using a C99 compiler or a C2011 compiler that supports variable-length arrays:

size_t rows, cols;
// assign rows and cols
int *arr = malloc(sizeof *arr * rows * cols);
{
  // do stuff with arr[i * rows + j]
  free(arr);
}

---

Related Topics