How to properly work with dynamically-allocated mu

Question

This question already has an answer here:

• How do I declare a 2d array in C++ using new? 22 answers

How do I define a dynamic multi-dimensional array in C++? For example, two-dimensional array? I tried using a pointer to pointer, but somehow it is failing.

Answer 1

The first thing one should realize that there is no multi-dimensional array support in C++, either as a language feature or standard library. So anything we can do within that is some emulation of it. How can we emulate, say, 2-dimensional array of integers? Here are different options, from the least suitable to the most suitable.

Improper attempt #1. Use pointer to pointer

If an array is emulated with pointer to the type, surely two-dimensional array should be emulated with a pointer to pointer to the type? Something like this?

int** dd_array = new int[x][y];

That's a compiler error right away. There is no new [][] operator, so compiler gladly refuses. Alright, how about that?

int** dd_array = new int*[x];
dd_array[0][0] = 42;

That compiles. When being executed, it crashes with unpleasant messages. Something went wrong, but what? Of course! We did allocate the memory for the first pointer - it now points to a memory block which holds x pointers to int. But we never initialized those pointers! Let's try it again.

int** dd_array = new int*[x];
for (std::size_t i = 0; i < x; ++i)
   dd_array[i] = new int[y];

dd_array[0][0] = 42;

That doesn't give any compilation errors, and program doesn't crash when being executed. Mission accomplished? Not so fast. Remember, every time we did call a new, we must call a delete. So, here you go:

for (std::size_t i = 0; i < x; ++i)
    delete dd_array[i];
delete dd_array;

Now, that's just terrible. Syntax is ugly, and manual management of all those pointers... Nah. Let's drop it all over and do something better.

Less improper attempt #2. Use std::vector of std::vector

Ok. We know that in C++ we should not really use manual memory management, and there is a handy std::vector lying around here. So, may be we can do this?

std::vector<std::vector<int> > dd_array;

That's not enough, obviously - we never specified the size of those arrays. So, we need something like that:

std::vector<std::vector<int> > dd_array(x);
for(auto&& inner : dd_array)
    inner.resize(y);

dd_array[0][0] = 42;

So, is it good now? Not so much. Firstly, we still have this loop, and it is a sore to the eye. What is even more important, we are seriously hurting performance of our application. Since each individual inner vector is independently allocated, a loop like this:

int sum = 0;
for (auto&& inner : dd_array)
    for (auto&& data : inner)
       sum += data;

will cause iteration over many independently allocated inner vectors. And since CPU will only cache continuous memory, those small independent vectors cann't be cached altogether. It hurts performance when you can't cache!

So, how do we do it right?

Proper attempt #3 - single-dimensional!

We simply don't! When situation calls for 2-dimensional vector, we just programmatically use single-dimensional vector and access it's elements with offsets! This is how we do it:

vector<int> dd_array(x * y);
dd_array[k * x + j] = 42; // equilavent of 2d dd_array[k][j]

This gives us wonderful syntax, performance and all the glory. To make our life slightly better, we can even build an adaptor on top of a single-dimensional vector - but that's left for the homework.