Tip: Three ways to allocate memory for a 2-dimensional matrix in C++

C++ does not support real multi-dimensional arrays, but can only simulate them. This tip describes three ways to allocate memory for a two-dimensional matrix.

1. data[row * ncol + column];
2. data[row][column];

Often form a is used, but there are also routines and libraries that use form b. An example of the latter is Numerical Recipes.

To allocate memory for form a you must allocate a contiguous block of memory to hold all matrix elements. For form b you have a choice: you can allocate each row apart or you can allocate a contiguous block of memory. Thus you may have the following.

1. One block Allocate a vector to hold all elements.
   Elements are accessed like int x = data[row * ncol + column];
2. A block per row and a column Allocate a vector for each row and a vector with a pointer to each row
   Elements are accessed like int x = data[row][column];
3. One block and a column Allocate a vector to hold all elements and a vector with a pointer to each row
   Elements are accessed like int x = data[row][column];

It is verywell possible to mix forms 1 and 3, because you can very easily convert from form 3 to form 1 and it isn't too dificult to convert from form 1 to form 3. Both conversion are shown below.

Here are several advantages and disadvantages for the three variants.

1. One block
   + One memory allocation (faster).
   - Large memory block required (harder to find a suitable memory block).
2. A block per row and a column
   + Smaller memory blocks are required (easier to find suitable memory blocks).
   - Many memory alloations (slower).
3. One block and a column
   + Two memory allocations (faster).
   - Large memory block required (harder to find a suitable memory block).

The next sections show implementations for the three variations. Note that these classes are only meant to illustrate the idea, they are by no means complete. Also Error handling has been omitted for clarity.

1. One block

In this variant, a single memory block is allocated to hold the data (see the constructor). As a consequence, the two indices must be converted to a single offset to access an element (see function Value).

/**
 * 2D Matrix with 1D storage internally.
 */
template <typename TValue>
class Matrix
{
public:
   /**
    * the value type.
    */
   typedef TValue ValueType;

   /**
    * this type.
    */
   typedef Matrix<ValueType> Self;

   /**
    * the pointer type.
    */
   typedef ValueType* PointerType;

   /**
    * the storage type.
    */
   typedef ValueType* StorageType;

   /**
    * the size type.
    */
   typedef int SizeType;

   /**
    * constructor.
    */
   Matrix( SizeType nrow, SizeType ncol )
      : m_nrow( nrow )
      , m_ncol( ncol )
      , m_data( new ValueType[ nrow * ncol ] )
   {
   }

   /**
    * destructor.
    */
   virtual ~Matrix()
   {
      delete[] m_data;
   }

   /**
    * the i-th row;
    * this allows you to write matrix[y][x] to access an element.
    */
   PointerType operator[]( int i )
   {
      return &Value( i, 0 );
   }

   /**
    * alias for Get(y,x) (const);
    * this allows you to write int x = matrix(y,x) to access an element.
    */
   ValueType operator()( SizeType y, SizeType x ) const
   {
      return Value( y, x );
   }

   /**
    * alias for Get(y,x) (non-const);
    * this allows you to write matrix(y,x) = x; to access an element.
    */
   ValueType& operator()( SizeType y, SizeType x )
   {
      return Value( y, x );
   }

   /**
    * the number of rows.
    */
   SizeType Rows() const
   {
      return m_nrow;
   }

   /**
    * the number of columns.
    */
   SizeType Columns() const
   {
      return m_ncol;
   }

   /**
    * the value of the given location (const).
    */
   ValueType Get( SizeType y, SizeType x ) const
   {
      return Value( y, x );
   }

   /**
    * the value of the given location (non-const).
    */
   ValueType& Get( SizeType y, SizeType x )
   {
      return Value( y, x );
   }

   /**
    * set the value of the given location.
    */
   void Set( SizeType y, SizeType x, const ValueType& value )
   {
      Value( y, x ) = value;
   }

   /**
    * the internal representation.
    */
   friend StorageType GetImpl( Self& matrix )
   {
      return matrix.m_data;
   }

protected:
   /**
    * the value of the given location (non-const).
    */
   ValueType& Value( SizeType y, SizeType x )
   {
      return m_data[ y * Columns() + x ];
   }

private:
   /**
    * the number of rows.
    */
   SizeType m_nrow;

   /**
    * the number of columns.
    */
   SizeType m_ncol;

   /**
    * the internal representation.
    */
   StorageType m_data;

private:
   /**
    * prevent asignement.
    */
   Self& operator= ( const Self& );

   /**
    * prevent copy-asignement.
    */
   Matrix( const Self& );
};

2. A block per row and a column

In this variant, a memory block is allocated for each row. In addition to that, one memory block is allocated for the highest dimension to hold pointers to the rows. See function Create.

/**
 * 2D Matrix with non-contiguous 2D storage internally.
 */
template <typename TValue>
class Matrix
{
public:
   /**
    * the value type.
    */
   typedef TValue ValueType;

   /**
    * the value type.
    */
   typedef Matrix<ValueType> Self;

   /**
    * the pointer type.
    */
   typedef ValueType* PointerType;

   /**
    * the storage type.
    */
   typedef ValueType** StorageType;

   /**
    * the size type.
    */
   typedef int SizeType;

   /**
    * contructor.
    */
   Matrix( SizeType nrow, SizeType ncol )
      : m_nrow( nrow )
      , m_ncol( ncol )
      , m_data( Create( nrow, ncol ) )
   {
   }

   /**
    * destructor.
    */
   virtual ~Matrix()
   {
      for ( int row = 0; row < Rows(); ++row )
      {
         delete[] m_data[ row ];
      }

      delete[] m_data;
   }

   /**
    * the i-th row;
    * this allows you to write matrix[y][x] to access an element.
    */
   PointerType operator[]( int i )
   {
      return m_data[ i ];
   }

   /**
    * alias for Get(y,x) (const);
    * this allows you to write int x = matrix(y,x) to access an element.
    */
   ValueType operator()( SizeType y, SizeType x ) const
   {
      return Get( y, x );
   }

   /**
    * alias for Get(y,x) (non-const);
    * this allows you to write matrix(y,x) = x; to access an element.
    */
   ValueType& operator()( SizeType y, SizeType x )
   {
      return Get( y, x );
   }

   /**
    * the number of rows.
    */
   SizeType Rows() const
   {
      return m_nrow;
   }

   /**
    * the number of columns.
    */
   SizeType Columns() const
   {
      return m_ncol;
   }

   /**
    * the value of the given location (const).
    */
   ValueType Get( SizeType y, SizeType x ) const
   {
      return m_data[ y ][ x ];
   }

   /**
    * the value of the given location (non-const).
    */
   ValueType& Get( SizeType y, SizeType x )
   {
      return m_data[ y ][ x ];
   }

   /**
    * set the value of the given location.
    */
   void Set( SizeType y, SizeType x, const ValueType& value )
   {
      m_data[ y ][ x ] = value;
   }

   /**
    * the internal representation.
    */
   friend StorageType GetImpl( Self& matrix )
   {
      return matrix.m_data;
   }

protected:
   /**
    * convenience function to create the internal representation inside the
    * member initialization list (MIL).
    */
   StorageType Create( SizeType nrow, SizeType ncol )
   {
      StorageType m = new PointerType[ nrow ];

      for ( int row = 0; row < nrow; ++row )
      {
         m[ row ] = new ValueType[ ncol ];
      }

      return m;
   }

private:
   /**
    * the number of columns.
    */
   SizeType m_ncol;

   /**
    * the number of rows.
    */
   SizeType m_nrow;

   /**
    * the internal representation.
    */
   StorageType m_data;

private:
   /**
    * prevent asignement.
    */
   Self& operator= ( const Self& );

   /**
    * prevent copy-asignement.
    */
   Matrix( const Self& );
};

3. One block and a column

In this variant the data is located in one contiguous block of memory. An extra vector with pointers that point to the rows in this block provides for the two-dimensional view. See function Create. The first time I saw this form of memory allocation was in the LTI- Lib a library for image processing and computer vision.

/**
 * 2D Matrix with contiguous 2D storage internally.
 */
template <typename TValue>
class Matrix
{
public:
   /**
    * the value type.
    */
   typedef TValue ValueType;

   /**
    * the value type.
    */
   typedef Matrix<ValueType> Self;

   /**
    * the value type.
    */
   typedef ValueType* PointerType;

   /**
    * the value type.
    */
   typedef ValueType** StorageType;

   /**
    * the value type.
    */
   typedef int  SizeType;

   /**
    * constructor.
    */
   Matrix( SizeType nrow, SizeType ncol )
      : m_nrow( nrow )
      , m_ncol( ncol )
      , m_data( Create( nrow, ncol ) )
   {
   }

   /**
    * destructor.
    */
   virtual ~Matrix()
   {
      delete[] m_data[0];
      delete[] m_data;
   }

   /**
    * the i-th row;
    * this allows you to write matrix[y][x] to access an element.
    */
   PointerType operator[]( int i )
   {
      return m_data[ i ];
   }

   /**
    * alias for Get(y,x) (const);
    * this allows you to write int x = matrix(y,x) to access an element.
    */
   ValueType operator()( SizeType y, SizeType x ) const
   {
      return Get( y, x );
   }

   /**
    * alias for Get(y,x) (non-const);
    * this allows you to write matrix(y,x) = x; to access an element.
    */
   ValueType& operator()( SizeType y, SizeType x )
   {
      return Get( y, x );
   }

   /**
    * the number of rows.
    */
   SizeType Rows() const
   {
      return m_nrow;
   }

   /**
    * the number of columns.
    */
  SizeType Columns() const
   {
      return m_ncol;
   }

   /**
    * the value of the given location (const).
    */
   ValueType Get( SizeType y, SizeType x ) const
   {
      return m_data[ y ][ x ];
   }

   /**
    * the value of the given location (non-const).
    */
   ValueType& Get( SizeType y, SizeType x )
   {
      return m_data[ y ][ x ];
   }

   /**
    * set the value of the given location.
    */
   void Set( SizeType y, SizeType x, const ValueType& value )
   {
      m_data[ y ][ x ] = value;
   }

   /**
    * the internal representation.
    */
   friend StorageType GetImpl( Self& matrix )
   {
      return matrix.m_data;
   }

protected:
   /**
    * convenience function to create the internal representation inside the
    * member initialization list (MIL).
    */
   StorageType Create( SizeType nrow, SizeType ncol )
   {
      StorageType     m = new PointerType[ nrow ];
      PointerType block = new ValueType[ nrow * ncol ];

      m[0] = block;

      for ( int row = 1; row < nrow; ++row )
      {
         m[ row ] = &block[ row * ncol ];
      }

      return m;
   }

private:
   /**
    * the number of columns.
    */
   SizeType m_nrow;

   /**
    * the number of rows.
    */
   SizeType m_ncol;

   /**
    * the internal representation.
    */
   StorageType m_data;

private:
   /**
    * prevent asignement.
    */
   Self& operator= ( const Self& );

   /**
    * prevent copy-asignement.
    */
   Matrix( const Self& );
};

4. Conversions

Converting a two-dimensional view to a one-dimensional view is easy, provided that the memory of the two-dimensional view is allocated as a contiguous block.

/**
 * convert two-dimensional view to one-dimensional view;
 * requires contiguous allocated memory block.
 */
template <typename T>
T* To1DView( T** matrix )
{
   return matrix[0];
}

Converting a one-dimensional view to a two-dimemsional view requires an extra (dynamically allocated) column with a pointer for each row. To handle the destruction we use a proxy class to return from the conversion function ToScoped2DView.

#include "Matrix1D.h"

/**
 * convert one-dimensional view to two-dimensional view;
 */
template <typename T>
class Scoped2DViewProxy
{
public:
   /**
    * this type.
    */
   typedef Scoped2DViewProxy< T > Self;

   /**
    * the value type.
    */
   typedef T ValueType;

   /**
    * the pointer type.
    */
   typedef ValueType* PointerType;

   /**
    * destructor.
    */
   ~Scoped2DViewProxy()
   {
      delete[] m_rows;
   }

   /**
    * construct the view of a column with pointers to rows.
    */
   Scoped2DViewProxy( const PointerType base1D, int nrow, int ncol )
      : m_rows( 0 )
   {
      m_rows = new PointerType[ nrow ];

      m_rows[ 0 ] = base1D;

      for ( int i = 1; i < nrow; ++i )
      {
         m_rows[ i ] = &base1D[ ncol * i ];
      }
   }

   /**
    * use compiler-generated copy-assignment.
    */
   // Scoped2DViewProxy( const Self& );

   /**
    * automatic conversion to 2 dimensional view.
    */
   operator PointerType* ()
   {
      return m_rows;
   }

   /**
    * explicit conversion to 2 dimensional view.
    */
   PointerType* Data()
   {
      return m_rows;
   }

private:
   /**
    * prevent default construction.
    */
   Scoped2DViewProxy();

   /**
    * prevent assignment.
    */
   Self& operator= ( const Self& );

   /**
    * the column with pointers to rows.
    */
   PointerType* m_rows;
};

/**
 * create a scoped 2D view proxy for a one-dimensional array that represents 2D data.
 */
template <typename T>
Scoped2DViewProxy<T> ToScoped2DView( T* base1D, int nrow, int ncol )
{
   return Scoped2DViewProxy<T>( base1D, nrow, ncol );
}

/**
 * create a scoped 2D view proxy for an Matrix with element type T.
 */
template <typename T>
Scoped2DViewProxy<T> ToScoped2DView( Matrix< T >& matrix )
{
   return Scoped2DViewProxy<T>( GetImpl( matrix ), matrix.Rows(), matrix.Columns() );
}

The following example shows how you may use the scoped two-dimensional array that the conversion function returns.

#include <iostream>             // for std::cout
#include "ToScoped2DView.h"     // for ToScoped2DView() and class Matrix<> (1D internally)

/**
 * print contents of a two-dimensional array.
 */
template <typename T>
void PrintArray2D( T** array2D, int nrow, int ncol )
{
   for ( int y = 0; y < nrow; ++y )
   {
      for ( int x = 0; x < ncol; ++x )
      {
         std::cout << array2D[ y ][ x ] << " ";
      }
      std::cout << std::endl;
   }
}

/**
 * fill a matrix (1D) and print its contents using ToScoped2DView().
 */
int main()
{
   /*
    * create and fill matrix with 1-dimensional data internally:
    */
   Matrix<int> matrix( 3, 4 );

   for ( int y = 0; y < matrix.Rows(); ++y )
   {
      for ( int x = 0; x < matrix.Columns(); ++x )
      {
         matrix( y, x ) = 10 * y + x;
      }
   }

   /*
    * intended use:
    */
   PrintArray2D<int>( ToScoped2DView( matrix ), matrix.Rows(), matrix.Columns() );

   /*
    * you can also write:
    */
   PrintArray2D( ToScoped2DView( matrix ).Data(), matrix.Rows(), matrix.Columns() );

   /*
    * Warning: you cannot use array2D below: its contents is not valid after the semicolon!
    */
   int** array2D = ToScoped2DView( matrix );    // Wrong!

   return 0;
}

Martin Moene Electronics Department · Leiden Institute of Physics · Leiden University