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[i]=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[i]. 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[i] 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[i] (on a Win32 machine, the memory
adress is 4 bytes, isn't it?)

regards
hall
--
( - Remove capital X from email to reply - )

[Karl Heinz Buchegger]

hall wrote:

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[i]=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[i]. 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[i] 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[i] = 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[i] 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[i].

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[i] (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.

--
Karl Heinz Buchegger
kb******@gascad .at

[Buster Copley]

Ron Natalie wrote:

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.