Multi Dimensional Dynamically Allocated Arrays

There is a nice trick to get a dynamically backed contiguous amount of memory to index like a static array. This is easy to find on the internet, however even thought the C++ standard talks about how to do a 3D version I could not find any example code.

From the C++ standard page (https://en.cppreference.com/w/cpp/language/operators)

“operator[] can only take one subscript. In order to provide multidimensional array access semantics, e.g. to implement a 3D array access a[i][j][k] = x;, operator[] has to return a reference to a 2D plane, which has to have its own operator[] which returns a reference to a 1D row, which has to have operator[] which returns a reference to the element. To avoid this complexity, some libraries opt for overloading operator() instead, so that 3D access expressions have the Fortran-like syntax a(i, j, k) = x;”

To be clear, this is what we are trying to obtain:

    array a;
    a.setDimensions(3, 4, 5);
    a[2][0][4] = 42;
    // ... vs ...
    a(2, 0, 4) = 42;

So here it is how the C syntax style can be done for 3D.

First the version that explains in detail what is going on. Here you can see the plane object talked about in the standard. This does not return a reference as the size is small enough.

struct array
{
	struct row
	{
		row(array* array, int i, int j) 
			: _array{array}, _i{i}, _j{j} {};
		inline int &operator[](int k) 
		{ 
			assert(k < _array->_kSize);
			int offset = 
				(_i * _array->_kSize * _array->_jSize) +
				(_j * _array->_kSize) +
				(k);
			return *(_array->_data + offset); 
		}
		int		_i;
		int		_j;
		array*	_array;
	};
	struct plane
	{
		plane(array* array, int i) 
			: _array{array}, _i{i} {};
		inline row operator[](int j) 
		{ 
			assert(j < _array->_jSize); 
			row newRow(_array , _i, j); 
			return newRow;
		}
		int	_i;
		array*	_array;
	};
	inline plane operator[](int i)
	{
		assert(i < this->_iSize);
		plane newPlane(this, i); 
		return newPlane;
	}
	void setDimensions(int x, int y, int z)
	{
		_iSize = x;
		_jSize = y;
		_kSize = z;
1	}
	int		_data[24];
	int		_iSize{1};
	int		_jSize{1};
	int		_kSize{1};
};

This is a faster version that uses the typical approach where the returned value is a pointer to the objects so that the last [ ] addressing is done ‘for free’.

struct arrayFast
{
	struct plane
	{
		plane(int* data, int kSize) 
			: _data{data}, _kSize{kSize} {};
		inline int* operator[](int j)
		{
			return _data + j * _kSize;
		}
		int*	_data;
		int	_kSize;
	};
	inline plane operator[](int i)
	{
		int offset = i * _jSize * _kSize;
		plane newPlane(_data + offset, _kSize);
		return newPlane;
	}
	void setDimensions(int x, int y, int z)
	{
		_iSize = x;
		_jSize = y;
		_kSize = z;
	}
	int		_data[24];
	int		_kSize{1};
	int		_jSize{1};
	int		_iSize{1};
};

Finally the recommended solution of using operator() instead.

struct arrayFaster
{
	inline int& operator()(int i, int j, int k)
	{
		int offset = (i * _kSize * _jSize) + (j * _kSize) + (k);
		return *(_data + offset);
	}
	void setDimensions(int x, int y, int z)
	{
		_kSize = z;
		_jSize = y;
		_iSize = x;
	}
	int		_data[24];
	int		_iSize{1};
	int		_jSize{1};
	int		_kSize{1};
};

This last one looks much easier to understand and you would expect it to be the fastest solution as well. The code is direct and the maths in one place.

I did a quick check on Godbolt (https://godbolt.org/z/EP36qooaE) and it looks like the 2nd and last options are very similar in instructions. I did not speed test these, but it is interesting enough that for now I will be using the traditional C syntax solution.