In essence, a multidimensional array is just an array in
which every element is another array.
What do you think would happen if I wanted to access the second
element of this 2D array? Since this is array of arrays, I should
get back the second nested array.
In this situation, we could say a second column. And then we can use another
set of brackets to get the element from that nested array.
So how could we replicate this on the heap?
Let's say that we want to make a dynamic two‑dimensional array.
Every dimension will be taken from the terminal at runtime, so I will
change this code a little bit to reflect that requirement.
We know how to allocate an array of integers on the heap.
We can just use the special new keyword for creating arrays. But now
I want to have an array which is two dimensional,
which is an array of arrays.
We know that an array name works similar to a pointer, so an
array of arrays would be an array made up of elements where each
one of them points to another array.
In other words, first, we need to make an array of pointers to integers.
And since this pointer should capture the first element from the array,
I need to add another asterisk to its declaration.
We didn't use this syntax yet, but this is a pointer to a pointer. In this case,
a pointer that points to a pointer, which points to an integer.
The difference is important because if this was just a pointer to an integer,
then the compiler would think that this pointer points to the first byte
of a 4‑byte sequence, which makes an integer value.
However, since this is an array of pointers,
our pointer actually points to the first byte of an 8‑byte sequence
because on my computer a pointer needs 8 bytes.
This allocated array represents one dimension, in this case, a number
of rows. But this is just an array of pointers.
Each one of these pointers need to point to another array, which
will hold numbers from each column of the table.
We need to do this manually now,
so let's create a for loop which will allocate a new array
on the heap and store its address inside of the pointer
element from the first array.
Once we do this, we are done.
Now we can use this pointer to a pointer,
just like a name for a 2D array. I can prove this by compiling the same
code for printing the table from the previous lesson.
As you can see, it still works.
So how come this syntax with two square brackets still works? Well,
we can write this expression in a different way.
This is how it would look like if we used the dereference operator
instead of square brackets. First, we need to dereference the first
dimension with the required offset.
This will give us one of the elements from the first array, and that
element is a pointer to a first integer from one of the nested
arrays. Then we can add an offset to that first address to get the
required column from the nested array, and this would get us back the
number from the matrix.
Even though this approach works,
I would advise you against creating multidimensional arrays like this.
Aside from the fact that it looks messy and weird to allocate each
dimension explicitly, it is also really bad for performance.
Imagine what happens in memory when we execute this code. First, we need to
allocate space for this pointer to a pointer, which is 8 bytes.
Then we allocate based on the heap for an array of
two pointers, which is 16 bytes.
And after that, for each one of these elements, we need to
allocate another subarray on the heap.
In this case, this is 2 subarrays with 3 integers,
so we need 24 bytes for all of them.
So this is 48 bytes in total, and all of these subarrays are
scattered throughout the heap because we used new operator to
allocate space for each one of them specifically.
And when you want to access one of these numbers from the matrix, first, we
need to find the required pointer inside of the main array and then follow the
address from that pointer to find the correct subarray, and only then we can
find the right element in that subarray.
So this multidimensional array is placed all over the heap.
When we create a static array on the stack,
we only need enough storage to hold all of the elements. In
this case, this would be six integers, so 24 bytes.
This is half of the amount of memory we needed to store the same
array on the heap, and this static array also places all of these
integers next to each other in memory, which is always better for performance.
Even though we said that an array name works kind of like a pointer to
the first element of the array, we have proven that there are
differences between a real pointer and in array name.
Aside from everything we already covered,
I didn't explicitly explained that the compiler actually works its magic
with the array names to get us exactly what we need without actually
storing this in some kind of a pointer variable.
Unlike regular variables, array names don't have a place in memory.
Only the array elements need space. Array name just exists in the code.
So when we have 2D arrays on the stack,
all of these subarrays are also managed by the compiler magic.
We don't actually need a pointer for each subarray.
When you try to access the first subarray,
compiler will know what you're trying to do and what
location in memory it needs to check.
That's why I said that using this syntax is the same as using a
mathematical formula from the previous lesson, because you don't need
any additional space or computing power. Compiler will take care of
this before the actual compilation.
So if you need to have dynamic arrays on the heap,
the best solution would be to actually use the mathematical formula we talked
about and allocate space in a single, one‑dimensional array.
You can get the total number of elements by multiplying the
number of rows and columns, and then you can use the
formula to access these elements.
We will still need additional 8 bytes to store this pointer to an array, but we
need it to access the heap, and this is a small price to pay compared to how
much space we needed for the previous implementation.
Also, now we have all of the elements placed in a
single block of memory on the heap.
In my opinion,
this is the best way to implement an array on the heap if
all of its dimensions need to be dynamic.