Are C multidimensional arrays contiguous without holes?

Question

I am unable to find in the C standard docs specifically where it says that multidimensional arrays are contiguous. While it can be inferred from the fact that array elements are contiguous, I want some perspective from the community.

The following code prints out the numbers in the order that I would expect, which is 1 - 9.

#include <stdio.h>

int main()
{
    int a[][3] = {{1,2,3},{4,5,6},{7,8,9}};
    int* p = (int*)a;
    int i;

    for (i = 0; i < sizeof(a)/sizeof(int); i++)
        printf("%d ",p[i]);

    return 0;
}

Since multidimensional-arrays are arrays of arrays, elements are contiguous (i think). — , Apr 15 '16 at 12:36
They better be -- it is a fairly common idiom to process 2-dimensional arrays with a single as opposed to nested for loop. All such code would be broken if this weren't the case. — John Coleman, Apr 15 '16 at 12:38
An `array[x][y]` of type `z` is guaranteed to occupy (x * y * sizeof(z)) **only**. Note that `sizeof(z)` is not in all cases guaranteed to occupy the maximum amount of bits needed for the type only - It can be bigger and `sizeof(char)`, for example, can be more than 8 on some CPUs. — tofro, Apr 15 '16 at 13:52
@tofro NIt: `sizeof(z) * x * y` has advantage over `x * y * sizeof(z)` given various types of `x,y`. — chux - Reinstate Monica, Apr 15 '16 at 19:07
@chux Sorry, but that comment doesn't make much sense to me. — tofro, Apr 16 '16 at 08:12
@tofro. `sizeof()` and the result needed for indexing is `size_t` - an unsigned type potentially with a far wider range then `x,y`. Example: With large arrays and use of `int x,y`, `x * y * ...` can overflow, whereas `sizeof(z) * x * y` would not. — chux - Reinstate Monica, Apr 16 '16 at 12:59
And that fits to *Order of evaluation of the operands of any C operator, ... and the order of evaluation of the subexpressions within any expression is unspecified* exactly how? — tofro, Apr 16 '16 at 13:48
@tofro I think what he is saying is that if x and y are ints, there is potential overflow. However, since size_t is an unsigned integral type, by multiplying x by sizeof(z) first, the product will be a size_t which is largest enough to fit the result. Then multiplying that by y will yield a size_t as well. — Bran, Apr 16 '16 at 14:11
All right and OK. But the order of arguments doesn't necessarily fix how an expression is actually calculated. Just writing it the other way round will not help. In all of my understanding, it is up to the compiler whether it calculates the first or second multiplication first. — tofro, Apr 16 '16 at 16:47

Sourav Ghosh · Accepted Answer · 2016-04-15T12:50:42.157

Yes, it can be obtained by induction. (Just to add, as a suggestion, if that helps, try to think of multi-dimensional arrays as array of arrays.)

For example, consider an array like a[3][3].

So, a[0][0], a[0][1] and a[0][2] are elements of a[0] and they will be contiguous.
Next, a[0] and a[1] are elements of a, so it will be contiguous

an so on.

Taken together, a[0][2] and a[1][0] will be residing next to each other, thereby continuing the contiguity.

For better visual representation, see the below illustration.

The array, say int arr[4][5], has four rows, a[0],a[1], a[2] and a[3] and they are contiguous.

Now each of those rows have five columns, like a[n][0], a[n][1], a[n][2], a[n][3], a[n][4] and they are contiguous.

So, the all the elements (and elements of elements) of the array are contiguous.

Thanks for confirming. This was my same thought. – Bran Apr 15 '16 at 13:03 — Bran, Apr 15 '16 at 13:03

score 9 · Answer 2 · answered Apr 15 '16 at 12:40

According to 6.2.5 Types p20:

An array type describes a contiguously allocated nonempty set of objects with a particular member object type, called the element type. The element type shall be complete whenever the array type is specified. ...

Therefore all array types, multidimensional or not, are contiguously allocated.

score 7 · Answer 3 · answered Apr 15 '16 at 12:37

7

Yes they are contiguous. I would say the fact "an array" (i.e. singular) is contiguous infers that a multi-dimensional one is. Each array within it must be contiguous and the outer array must be a contiguous collection of those arrays...

answered Apr 15 '16 at 12:37

noelicus

14,468
3
92
111

score 1 · Answer 4 · answered Apr 15 '16 at 12:42

1

C does not explicitly have multi-dimentional arrays, C have array of arrays, and arrays in C are contiguously represented in memory. Hence all arrays in C are contiguous.

answered Apr 15 '16 at 12:42

fluter

13,238
8
62
100

@JohnColeman Sorry, I wanted to make sure that new comer understands C does NOT have multi-dimensional arrays, it has array of arrays. – fluter Apr 15 '16 at 12:48
2

@fluter What would be considered a "real" multidimensional array? – Bran Apr 15 '16 at 13:08
3

Actually C standard mentions multidimensional arrays many times, including, for example, footnote 142 in chapter §6.7.6.2: *"When several ‘‘array of’’ specifications are adjacent, a multidimensional array is declared."* – user694733 Apr 15 '16 at 13:09
@user694733 You're right, I totally missed that. I believe he might be referring to simulated MD arrays in the same way pass-by-reference is done in C. – Bran Apr 15 '16 at 13:13

Are C multidimensional arrays contiguous without holes?

4 Answers4

Linked