1

I know that multidimensional arrays are allocated contiguously, so int[4][3] arr; will allocate 12 int cells in a row.

My first question is, given that C does not keep track of the lengths of arrays, how does it know the proper arithmetic needed to convert the two coordinate access pattern into the single coordinate memory address? E.g., if 

arr == 0x? // some memory address

Then 

&arr[2][1] == 0x? + 3 * 2 int cells + 1 int cell.

Where are the 3 pulled from?

My second question is when arrays are allocated on the heap, are they still allocated in the same contiguous manner? Or is it implemented as an array of pointers, which dereference to one dimensional arrays?

Improve this question
4
  • 2
    It does track the lengths. Can we close the question? Commented Jul 27, 2015 at 20:09
  • 3
    they're really just "arrays-of-arrays", and since arrays are fixed-size, and have to be declared in advance, the compiler can do the appropriate math to "dereference" any item in the array. Commented Jul 27, 2015 at 20:15
  • 1
    You're confusing arrays with pointers. Pointers don't have the length of what they point to, but arrays are declared with all their dimensions. Commented Jul 27, 2015 at 20:16
  • "Where is the 3 pulled from?" From the second specified dimension of the 2D array int[4][3] arr [sic]. That is crucial, but the first dimension is not, perhaps that is what you are confusing. You can declare a function foo(int bar[][3]) which does need to know the first dimension to work, but of course it needs to know the limit in some way.. Commented Jul 27, 2015 at 20:20

2 Answers 2

Reset to default
5

C does keep track of array lengths, but only at compile time, not at runtime (it's not saved in the array structure):

#include <stdio.h>

int main(int argc, char **argv)
{
  char array[] = "hello world";
  char* char_ptr = array;

  printf("array size: %lu\n", sizeof(array));
  printf("char_ptr size: %lu\n", sizeof(char_ptr));
  printf("void_ptr size: %lu\n", sizeof(void*));

  int matrix[2][3] = {{1,2,3},{4,5,6}};
  printf("matrix size (items): %lu\n", sizeof(matrix)/sizeof(int));
  return EXIT_SUCCESS;
}

Output:

array size: 12
char_ptr size: 8
void_ptr size: 8
matrix size (items): 6

There's this nuance in C that arrays auto-convert to pointers, but pointers and arrays (declared at compile time) are still two different types for the compiler.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

The array dimension is also known at runtime. The compiler may or may not use storage for it. For arrays whose size is known at compile-time , the compiler can bake that into the code generated, so it usually wouldn't need to store the array dimensions on their own anywhere. For other arrays it may need to, e.g. char ch[atoi(foo)]; and later on using sizeof ch.
4

  1. The compiler simply remembers the type (including the 3) of the array variable. In that way it knows what to do when you access it.

  2. A compiler will treat an array in the same way on the heap or on the stack. An array of pointers is a completely different type, so it has no other choice.

Note that with current advanced compiler optimisations, it's impossible to know what the final code will actually do, depending on how you use the array. If, for example, only one column is accessed ever, the others might be optimised away, resulting in a 1-d array in memory.

Improve this answer

4 Comments

what do you mean by your last sentence?
@MattMcNabb Clear now?
Yes (although in fact anything at all in your program may be optimized to anything else, so long as the program output is the same, so this is not a special case)
@MattMcNabb Because the questions were basic, I thought it would be good to also add this, indeed generic, remark.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.