C++ Declaring a static contiguous multi-dimensional array on the heap the right way

Question

What is the right way to declare a multi-dimensional array that does not change size during runtime on the heap? (ideally in C++11, if there is some feature only available in C++14 (not C++17) I would love to hear about it too, but chances are it would not work for me)

I have by now looked through dozens of questions and answers about this topic but none seems to really answer it/some answers conflict with others.

The following solutions I have found and the problems they seem to have that make them non-viable (most of these taken from SO answers and their comments, examples all given with assuming a 3D-array as the target):

• Normal [][][] array declared with new/declaring an array of pointers
  Problem: Non-contiguous in memory, every individual array has its independent location in memory

• multiple std::arrays/boost::arrays nested inside each other
  Problem: Non-contiguous in memory, every individual array has its independent location in memory

• Matrix
  Problem: Just a container for std::array, same problems apply basically

• multiple std:vectors nested inside each other
  Problem: Dynamic, pretty much all the other problems mentioned before

• Declare as a single block with a pointer to a normal [] array, then go through the index by calculation during runtime with a function like GetIndex(array,x,y,z)
  Problem: This seems to tick all points, but this solution seems less than ideal because of the significant CPU-overhead this seems to introduce when you need to access/change the elements often

Little bit unrelated to that, I have also had some issues with these solutions if they were in classes and I had to access their values from the outside with the . operator, so I would be even more grateful if someone could tell the correct solution with an example of both correct declaration and correct access of the heap-allocated multidimensional-array as a class-member.

Answer 1

Normal [][][] array declared with new/declaring an array of pointers Problem: Non-contiguous in memory, every individual array has its independent location in memory

...

Yes, the size is always declared with a #define. – uncanny

Yeah, C++ multidimensional arrays are tricky and quite good at making C++ code unreadable. Actually, you can create static multidimensional array if sizes are known at compile time, so you will get it allocated as a contiguous chunk of memory.

int main()
{
    int arr[100][200][100]; // allocate on the stack

    return 0;
}

The question is how to allocate it on the heap... No problem, just wrap it into a struct, and allocate this struct on the heap.

#include <memory>

struct Foo
{
    int arr[100][200][100];
};

int main()
{
    auto foo = std::make_unique<Foo>(); // allocate on the heap
    auto& arr = foo->arr;

    arr[1][2][3] = 42;

    return 0;
}

The std::make_unique call allocates Foo on the heap, and guarantees that memory will be deallocated. Also, you are able to access the array inside and outside of Foo with almost zero amount of boilerplate code. Nice!

Answer 2

The right way is to write/use a multidimensional array class. Multidimensional arrays are fundamental objects throughout computer science and it's (IMO) insane that the STL never included first-class support for multidimensional arrays. Internally, the class should allocate a 1d array on the heap (for runtime-sized arrays) and do the arithmetic to convert multidimensional indices into 1d indices.

Eigen is a good choice if you're doing numerical work; not sure how useful it is for multidimensional arrays of a non-numeric type.

Answer 3

If all but the first dimension are compile-time constants (whether or not the first is), just write new T[x][Y][Z] or (more safely) std::make_unique<T[][Y][Z]>(x). The result is contiguous and the compiler has every opportunity to apply tricks like shifts instead of multiplications if appropriate to the dimensions. What you can’t do with such an entity is pass it as pointer and size to a function expecting a one-dimensional array:

f(&a3[0][0][0],x*Y*Z);  // undefined behavior

because pointer arithmetic is defined only within one T[] array (here, the array a3[0][0] that is a T[Z]).

If the first dimension is also constant, you can use a nested std::array (which has no extra memory overhead in practice) or just

struct A3 {
  T a[X][Y][Z];
};

Either has the advantage that it can be passed and returned by value and used as a standard container element. Such an object can of course also be passed by reference, or you can use an “array parameter”:

T f(A3 &a3) {
  return a3.a[0][0][1]+a3.a[0][1][0]+a3.a[1][0][0];
}
T g(T a[][Y][Z]) {
  return a[0][0][1]+a[0][1][0]+a[1][0][0];
}

Note that g’s parameter type is actually T (*)[Y][Z], which is why the first bound may be omitted. If you have

A3 *a3;

you would call these as

f(*a3);
g(a3->a);

but that’s just standard pointer usage and has nothing to do with the array type or the heap allocation.

Answer 4

Memory is nearly always one-dimensional. What we see as multi-dimensional arrays in languages are an illusion created by the compiler.

Let's take an example.

int numbers_1[10];
int numbers_2[2][5];

These both allocate enough storage for 10 integers and leaving type-safety - as might be in C/C++ - aside, are equivalent from the point of view of a processor. Indeed, you can transform - treat either as having however many dimensions as you like - one into the other through type casting pointers.

numbers_1[0] == ((int**)numbers_1)[0][0];

This expression holds true, so forth for all the 10 elements.

It does not matter what the storage class of an array is, they are all really just one dimensional.

Also, I believe it will help if you read about how Turing machines work. The tape is one dimensional even in UTM and that is the most powerful theoretical machine we have.