Allocation of memory for arrays, hoe does it work?

[hall]

I have a question regarding where memory is allocated when arrays are
created. I'll illustrate this by example. I may be wrong on some
details, do feel free to correct me.

The code piece:

int p[3][3];

Creates a 2dimensional array. p can be thought of as a pointer,
containing the adres of the first element in the array. The memory is
allocated in one sequence, so

p[x][y];

would mean: 'the integer at adress p + (x + 3*y)*sizeof(int)'. So far i
understand how memory is allocated, but what happens when I dynamically
allocate a 2d array?

int **n;
*n=new int[3];
for (int i=0; i<3; i++) n=new int[3];

Here, the memory can't be in a sequence since the compiler at line (2)
impossably can know how much memory will be allocated for each of the
pointers p. So my best guess for the memory allocation here is that
line (2) allocates an array of three pointer-to-int and stores the
adress of the first element in p. In line (3), each of these pointers in
p are set to point at the first element of an array of three int:s.
These three int-arrays need not be allocated anywhere near each other,
right? The memory would therefor be allocated in a very different way
than the simple int p[3][3] array, and i can accept this as I am now
dealing with pointers and not an array, but what does

n[x][y]

mean? how is this interpreted? Has the [] operators been overloaded or
am I totally wrong in my guess for where memory is allocated?

Also, the dynamically callocated array would need mor memory, wouldn't
it? apart form the 9 stored integers (18 bytes), it would also require
4*4 bytes for the pointers n and n (on a Win32 machine, the memory
adress is 4 bytes, isn't it?)

regards
hall

 

[Karl Heinz Buchegger]

I have a question regarding where memory is allocated when arrays are
created. I'll illustrate this by example. I may be wrong on some
details, do feel free to correct me.

The code piece:

int p[3][3];

Creates a 2dimensional array. p can be thought of as a pointer,
containing the adres of the first element in the array.

But note: p is *not* a pointer.
You have the right idea, but this sentence may be misleading to
other newbies.

The memory is
allocated in one sequence, so

p[x][y];

would mean: 'the integer at adress p + (x + 3*y)*sizeof(int)'. So far i
understand how memory is allocated, but what happens when I dynamically
allocate a 2d array?

int **n;
*n=new int[3];

n = new int* [3];

for (int i=0; i<3; i++) n=new int[3];

Here, the memory can't be in a sequence since the compiler at line (2)
impossably can know how much memory will be allocated for each of the
pointers p. So my best guess for the memory allocation here is that
line (2) allocates an array of three pointer-to-int and stores the
adress of the first element in p. In line (3), each of these pointers in
p are set to point at the first element of an array of three int:s.
These three int-arrays need not be allocated anywhere near each other,
right? The memory would therefor be allocated in a very different way
than the simple int p[3][3] array, and i can accept this as I am now
dealing with pointers and not an array,

an image is worth 1000 words.

int p[2][3] looks in memory like this:


p
+---+---+---+---+---+---+
| | | | | | |
+---+---+---+---+---+---+

| | | |
+--- 3 ---+ +--- 3 ---+

| |
+---- 2 times ---+


while

int **n;
n = new int* [2];
for( int i = 0; i < 2; ++i ) n = new int [3];

looks like this



n
+-----+ +------+ +---+---+---+
| o---------->| o---------------->| | | |
+-----+ +------+ +---+---+---+
| o---------+
+------+ | +---+---+---+
+--->| | | |
+---+---+---+

but what does

n[x][y]

mean? how is this interpreted? Has the [] operators been overloaded or
am I totally wrong in my guess for where memory is allocated?

No. Array indexing in C is defined to be:

n[x] = *(n+x);

thus array indexing is defined in terms of pointer arithmetic. That's
why the above works.

Take the address stored in n. Add x (adjusted to the data
type size) and add it to n. Use this new pointer to look
up the memory.

so a works completely different, depending on what a really
is. If it is a fixed size array, then the compiler knows where
in memory the array is located. The compiler adds x to that location
and uses that for the lookup.

If on the other hand the array a has been dynamically allocated, then
the lookup works a little bit different: locate a, fetch the starting
address from there, add the index and use the result for the lookup.

Note: Under the hood there is one more lookup in the second version,
yet you use always the same C syntax: a.

Also, the dynamically callocated array would need mor memory, wouldn't
it?

Look up the image. Yes it would.

apart form the 9 stored integers (18 bytes), it would also require
4*4 bytes for the pointers n and n (on a Win32 machine, the memory
adress is 4 bytes, isn't it?)

Yes.
Note: It is undefined how many bytes are needed to store something.
You could express the above as:

in the dynamic case there would be 9 * sizeof(int) bytes for the data
+ 3 * sizeof(int*) bytes for the pointer array
+ 1 * sizeof(int**) bytes for the starting pointer.

Now that would be true on every machine and everybody could still see
that that would require more memory then 9 * sizeof(int) for the
static case.

 

[Buster Copley]

While you can write
int (*n)[3] = new int[3][3];
There's no way to declare n for a runtime determined size.

The size of the first dimension can be determined at run-time,
as in

void f (int size)
{
int (* n) [3] = new int [size][3];
// ...
delete [] n;
}

Think of n as a one-dimensional dynamic array whose
value-type is int [3]. So we're passing `size', but
not `3', as an argument of `operator new []'.

The value-type must be completely known at compile
time to make pointer arithmetic operations well defined.

Dynamically allocated arrays would not be necessary if
their size had to be a compile-time constant. We could
dynamically allocate an instance of an appropriate
struct instead.