Allocation of memory for arrays, hoe does it work?

Discussion in 'C++' started by hall, Jul 8, 2003.

  1. hall

    hall Guest

    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


    --
    ( - Remove capital X from email to reply - )
     
    hall, Jul 8, 2003
    #1
    1. Advertising

  2. 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=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.

    --
    Karl Heinz Buchegger
     
    Karl Heinz Buchegger, Jul 8, 2003
    #2
    1. Advertising

  3. 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.
     
    Buster Copley, Jul 9, 2003
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    5
    Views:
    380
    -berlin.de
    Dec 24, 2004
  2. Ken
    Replies:
    24
    Views:
    3,945
    Ben Bacarisse
    Nov 30, 2006
  3. chris
    Replies:
    6
    Views:
    1,031
    chris
    Oct 28, 2005
  4. Philipp
    Replies:
    21
    Views:
    1,183
    Philipp
    Jan 20, 2009
  5. pluskid
    Replies:
    8
    Views:
    176
    Judson Lester
    Feb 5, 2008
Loading...

Share This Page