23

I was wondering how do arrays work in c. I end up with an hypothesis and I'd like to know if I am right or not.

We know arrays are a sequence of adjacent memory cases(boxes), where each box has the size of the type it stocks (i.e if INTs one box has a size = sizeof(int) and an array of 3 INTs takes in memory adjacent places of 3 sizeof(int) )

Now we also know that we can dynamically allocate memory for an array of a certain type (malloc in C, new in C++).

what makes me wonder is the fact that an array has for origin the the address of the first box of the array and the first value (the value in the later box) when calling it with the bracket [0] is array[0] == *(array+0) == *array (whether array was declared "type * array" or "type array[]" or "type array[size]") and "array" called that way whether define as a pointer or an array ("type * array" or "type array[]" or "type array[size]") is the address of the first box.

I end up thinking and I'd like a confirmation on this: arrays when even declared with the square brackets ([]) are actually in memory a sequence of n pointers each containing (having as a value not as an address) the address of a memory box Bi containing the actual value + those memory boxes (B0,...,Bn each containing the actual values). such that in the and when one declares "int array[5]" the program actually allocate 5 adjacent boxes of int pointers P0,P1,..,P4 and 5 int sized memory places scattered all over the computer memory B0,B1,...,B4 where the value of Pi is the address of Bi

enter image description here

Am I right or wrong!!?? Thank you!

Paiku Han
  • 581
  • 2
  • 16
  • 38

4 Answers4

13

arrays when even declared with the square brackets ([]) are actually in memory a sequence of n pointers each containing [...] the address of a memory box Bi containing the actual value + those memory boxes

Nope.

It sounds like you're puzzled how array[0] == *(array+0) == *array could be true both for an array declared as int array[10]; and int *array = ...;. A perfectly reasonable question; We're told that for a pointer ptr the expression *ptr gets the value the pointer is pointing at, so when we use the same syntax with an array where are the addresses that we're dereferencing?

Here's the secret: The array index operator ([]) does not work on arrays in C and C++. When you apply it to an array the language implicitly converts the array into a pointer to the array's first element. Thus adding to an array or dereferencing an array appears to behave the same as adding or dereferencing a pointer.

int array[10];

// These lines do exactly the same thing:
int *ptr1 = &array[0]; // explicitly get address of first element
int *ptr2 = array;     // implicitly get address of first element

So arrays really are a contiguous set of elements in memory where each element really is the value, not a pointer to another location containing the value. It's just that the way arrays are defined means that they often convert to a pointer implicitly and so it seems like there are pointers when really there's just an implicit conversion.

bames53
  • 86,085
  • 15
  • 179
  • 244
  • "The array index operator ([]) does not work on arrays." Of course it does. That's what it's for. But what the operator *does* is identical to pointer addition. – user207421 Oct 14 '13 at 23:18
  • 8
    @EJP Nope, if you read the C++ spec you'll see that the subscript operator is defined only to work with expressions of type "pointer to T", not expressions with array types. The reason using a subscript on an array is identical to using it on a pointer is because using it on an array first converts the array into a pointer and after that it actually is identical. – bames53 Oct 14 '13 at 23:25
  • 1
    @EJP Another way to see this is if you use the AST dump feature in clang on code like: `int main() { int array[10]; array[0]; }`, the AST will show you a node `ArraySubscriptExpr` that has a node `ImplicitCastExpr ` on the left. – bames53 Oct 14 '13 at 23:37
3

Arrays are stored contiguously in the virtual memory. However, the physical memory addresses that they map to may or may not be contiguous.

And the array elements do not store a pointer to point to the next element. Only the value is stored.

digital_revenant
  • 3,274
  • 1
  • 15
  • 24
2

Think of it as this:

array[n] is simply a syntactic sugar for *(array + n).

And no, there are no pointers, the array actually contains the values in a continuos memory range.

Karoly Horvath
  • 94,607
  • 11
  • 117
  • 176
  • yeah that's what I wrote and that how I do understand it but my question is what happen in term of memory allocation when one does "int array[n]" (or any other type for that matter)? – Paiku Han Oct 14 '13 at 22:26
  • 1
    `*` does dereferencing, so you get the *value* from location `n`. if what you wrote would be true, there would be a need for an extra step of dereferencing. (but there isn't as you can clearly see from the notation). – Karoly Horvath Oct 14 '13 at 22:28
  • 1
    do you see the green part of your picture? write the values directly there. that's what happens. the actual allocation depends on whether it's a local variable or dynamically allocated one. each has it's own (implementation specific) rules *but* it's not array specific. – Karoly Horvath Oct 14 '13 at 22:32
0

The array does not consist of any pointers. The elements of an array are stored on the heap whereas the reference to those elements is stored on the stack. If you declare an array called values of type int and it consists of 5 elements.

The variable values is a pointer to the first value values[0] stored on the heap, it is also referred to as the base address which is the address of the first element of the array. You might wonder that how would the code find the other elements of the array. values[1] can be dereferenced by *(values+1) or at a low level it is like this *(&values + n*sizeof(values[0])) where n is the index of the element you want to dereference.

So you get the other elements of an array by just adding the size of the element to the memory. This is because the elements of an array are stored side-by-side in memory or technically stated, the blocks of memory share the same border.

An array does not have any pointers, an array like data-structure that contains pointers is called a linked list.

You can learn about the internal working of arrays here