0

Coming from Python, if C does not have array bounds, how does it know where a[1] starts?

int a[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
b = a[1][1];
Improve this question
3
  • 3
    When you say int a[3][3]; (or whatever) then C does have array bounds. You gave it the [3] (in your case, both of them). For non-constant size arrays, you'd have to malloc/calloc them yourself, treat them as single-dimension arrays, and do the (very simple) multi-dimension index arithmetic yourself. – John Forkosh Feb 12 '17 at 10:35
  • @JohnForkosh: "For non-constant size arrays, you'd have to malloc/calloc them yourself, ..." But technically, you don't get an "array" (expression of array type) from that. You just get a pointer to an element. So I would say that actual "arrays" always have bounds. – user102008 Feb 18 '17 at 3:00
  • @user102008 You don't even get "a pointer to an element", you typically just get a void *ptr=malloc(nbytes) that you have to cast yourself, e.g., ival = ((int *)ptr)[i], or something along those lines. All that housekeeping was intended to be implied by my "do the (very simple) multi-dimension index arithmetic yourself" remark. (Maybe I should have spelled it all out as an "answer", but I typically prefer comments whenever my remarks can fit within that format.) – John Forkosh Feb 18 '17 at 4:47
5

C knows the bound of an array at compile time, as opposed to Python which knows the bound of an array at runtime.

The compiler basically rewrite array access into pointer operations. It knows at compile time that the size of a the first dimension of the array is int[3], i.e. sizeof(int)*3. So:

b = a[x][y];

Is basically rewritten to

b = *(a + x * 3 + y);

So the knowledge about the dimension (the number 3) is encoded into the code, even if the dimensions are not explicitly available at runtime. Arguably, arrays are purely a compile-time construct in C.

Improve this answer
2
  • The pointer arithmetic here is very misleading. It would be correct if the pointer arithmetic would be for bytes, i.e. with (char*)a (and casting back the whole to (int*)). But a is int[][3], so a+1 is already 3*sizeof(int) bytes after a. So the multiplication by sizeof(int) will bring you completely out of range ! See online demo here: ideone.com/ZhpOWB – Christophe Feb 12 '17 at 23:40
  • @Christophe: You are totally correct. It was intended as psudocode to clarify the underlying calculation, but I guess this ended up being misleading. – JacquesB Feb 13 '17 at 8:12
1

C stores your 2D array as a contiguous bloc of 9 integers:

1 2 3 4 5 6 7 8 9

C uses compile time type and dimension information for generating the pointer arithmetic to access the elements.

In your example a[i] is a pointer to the start of the i-th row. Knowing that's a is a 2D array of int, and knowing that the last dimension has a size of 3, it can determine that a[i] is an array of 3 int starting at the i*3 th integer in a.

1 2 3 4 5 6  | 7 8 9 |
             ^
             Start of a[2]

Similarly, For accessing a[i][j] the compiler will generate code that uses the 3*i+j th integer in a.

However C consider that the programmer knows what he's doing. It will not check bounds. If i would be 5 and j 120, the code would execute blindly, causing undefined behaviour such as for example memory corruption, core dumps, and other bad things.

So if bounds are important for your algorithm, you should either use fixed bounds, or pass the bounds as extra parameter to your function.

If you'd use C++ instead of C, you could use vectors, which are dynamic arrays that know their size ( but it would still be up to you to check the bounds)

Improve this answer
2
  • 1
    If you use .at() instead of the [] operator to access elements, then C++ well check the boundaries. – Lie Ryan Feb 12 '17 at 11:34
  • @LieRyan yes, you are fully right. I was referring to operator[] only, and wanted to underline the importance to check bounds before accessing. In fact, i mentionne c++ just to draw attention of op, that if he'd have the language choice, c++ could provide higher level alternatives to raw arrays he would be more comfortable with; I didn't want to go too much into c++ specifics as the question was targetted as c. But anyways, thanks for this valuable comment. – Christophe Feb 12 '17 at 13:46
0

C knows because it knows the size of an int. So array[1] starts one int size up from array[0]. The same applies to array[1][1]

| size of an int |  
01011101 01101110 10...  
^                 ^  
array[0]          array[1]

Note that the size of an int is dependant on the platform, this was just an example.

Improve this answer
0

C knows where the next storage location for a given type is for the packing at the time of declaration so if you have an array of 16 bit integers the 'next' index in a single dimension array will be, usually, two bytes higher address but on some machines and with some compiler settings it might be the first 2 bytes of the next 64 bit word.
For a 2D array the next in the other direction normally would be the length of the single, lower, dimension as declared times the step for adjacent members of the lower order array, possibly plus some padding. For a 3D array the next element in the 3rd Dimension would normally be the size of the lower order 2D array aways, again possibly plus some padding.

The good news is that the compiler takes care of this if you use the normal indexing mechanisms, the bad is that, since the mechanism is not specified in the ANSI specification, it is up to the compiler manufacturer and how this is done and/or controlled. If you decide to try to access data in such structures directly then you are likely to have major issues. As a result of this ambiguity storing such data or exchanging it between programs that are possibly compiled with a different compiler, or even the same compiler but with different settings, on a single machine become a nightmare and given issues such as base component size and endianness exchanging data between machines or even times becomes even more so.

This is the reason that good data storage and exchange specifications are so verbose and often include the need to pack data in specific structures.

I had an issue several years ago where the data was being received as a bitfield 24 bits long, (in a telecommunications application), but on the Solaris machine we were using, with the default compiler, rather than being 3 bytes long this structure was 192 bytes. This was because, for speed, even an int:1 was stored in a 64 bit word. Several hours of researching the compiler settings showed that controlling this changed between versions of the compiler and we eventually switched to gcc instead. See the gcc manual for type attributes here for some more information.

Also be aware that C does not of itself have any array boundaries and not all compilers check against the array size. As a result if an array is defined as being int MyArray[8][12][20]; in one module but another shows it as extern int MyArray[]; then the second module will happily set MyArray[50000] = 0 with resulting problems.

Improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.