2

I know this answer is in violation of the reinterpret_cast rules but it also presumes that sub-arrays will be allocated linearly.

I believed this was not guaranteed, but as I search the standard, I find my confidence wavering. If I statically allocate a 2D array, like this:

int foo[][4] = { { 5, 7, 8 },
                 { 6, 6 },
                 {},
                 { 5, 6, 8, 9 } };

Am I allowed to assume that all elements will be allocated linearly? That is to say that if foo[0] is at address 0x00000042, will:

  • foo[1] be at address 0x00000052
  • foo[2] be at address 0x00000062
  • foo[3] be at address 0x00000072

These addresses are in hex, and yes they are providing space for the 4-element sub-array with sizeof(int) == 4; they may and may not be zero-initialized.

Bhargav Rao
  • 50,140
  • 28
  • 121
  • 140
Jonathan Mee
  • 37,899
  • 23
  • 129
  • 288
  • If `foo[0]` is at address `0x00000042`, `foo[1]` will be at address `0x00000052` only if `sizeof(int)` is `4`. I suspect you assumed that `sizeof(int)` is `4`. – R Sahu Jun 27 '16 at 15:18
  • 1
    @NathanOliver That's definitely not a dupe as he `malloc`s the memory in a loop so thee are absolutely no guarantees that can be made about the layout of those sub-arrays in memory. – Jonathan Mee Jun 27 '16 at 15:19
  • @JonathanMee The question is not the same but the answers describe a static 2d array not a dynamically allocated array of pointers. hence the no close vote from me. – NathanOliver Jun 27 '16 at 15:20
  • @RSahu OK I've edited I think that I have all my bases covered... – Jonathan Mee Jun 27 '16 at 15:20

2 Answers2

5

Are Sub-Arrays Guaranteed to be Allocated Linearly?

Yes. Whether the elements of the array are sub-arrays or non-array objects, they are guaranteed to be stored contiguously in memory.

For completeness, here is the standard quote:

[dcl.array]

  1. [snip] An object of array type contains a contiguously allocated non-empty set of N subobjects of type T. [snip]

There is no exception for the case when T is an array.

So we know this isn't guaranteed to be the case for const char[4].

On the contrary, we do know that this is guaranteed for char[4] objects just like it is guaranteed for other types.

For example: const char first[] = "foo"; char foo[][4] = {"bar", "foo", "", "baz"}

first would be stored like this in memory:

{'f', 'o', 'o', '\0'}

foo would be stored like this:

{'b', 'a', 'r', '\0', 'f', 'o', 'o', '\0', '\0', '\0', '\0', '\0', 'b', 'a', 'z', '\0'}

So why would you say this is guaranteed for ints?

It is guaranteed for int[4], char[4] and any other type that you can imagine.

Community
  • 1
  • 1
eerorika
  • 232,697
  • 12
  • 197
  • 326
  • 1
    So we know this isn't guaranteed to be the case for `const char[4]`. For example: `const char first[] = "foo"; char foo[][4] = {"bar", "foo", "", "baz"}` So why would you say this is guaranteed for `int`s? – Jonathan Mee Jun 27 '16 at 15:10
  • @JonathanMee, they will be if you use `char foo[][4] = { {'b', 'a', 'r', '\0'}, ...};`. – R Sahu Jun 27 '16 at 15:21
  • 1
    @RSahu: They will be even if you use `char foo[][4] = {"bar", "foo", "", "baz"}` -- Not sure why he thinks otherwise. – Benjamin Lindley Jun 27 '16 at 15:25
  • @JonathanMee see my edit. – eerorika Jun 27 '16 at 15:27
  • @BenjaminLindley Hmm, I thought that string literals were only ever allocated once by the compiler. Apparently I thought wrong. – Jonathan Mee Jun 27 '16 at 15:29
  • @JonathanMee: They are. But when you initialize a char array with a string literal, the string literal is copied to the array. It is a separate entity from the string literal – Benjamin Lindley Jun 27 '16 at 15:30
  • 1
    When you don't supply enough initializers for an array, the remainder isn't undefined, it's zero filled. There isn't an exception when a string is used as an initializer, is there? – Mark Ransom Jun 27 '16 at 15:33
  • 1
    @JonathanMee: Wait, did you mean that when you create two string literals with the same value, the compiler gives them the same address? It might do, but that is not a guarantee from the standard. And anyway, that is a separate issue from this, as per my previous comment. That would only be relevant if we were initializing pointers with string literals. – Benjamin Lindley Jun 27 '16 at 15:34
  • @MarkRansom thanks for pointing that out. I don't know why I thought otherwise. Answer fixed. – eerorika Jun 27 '16 at 15:34
3

From the C language standard ISO/IEC 9899 §6.2.5 Types/p20 (Emphasis Mine):

An array type describes a contiguously allocated nonempty set of objects with a particular member object type, called the element type.

Also from the C language standard ISO/IEC 9899 §6.5.2.1/p3 Array subscripting (Emphasis Mine):

Successive subscript operators designate an element of a multidimensional array object. If E is an n-dimensional array (n >= 2) with dimensions i x j x . . . x k, then E (used as other than an lvalue) is converted to a pointer to an (n - 1)-dimensional array with dimensions j x . . . x k. If the unary * operator is applied to this pointer explicitly, or implicitly as a result of subscripting, the result is the pointed-to (n - 1)-dimensional array, which itself is converted into a pointer if used as other than an lvalue. It follows from this that arrays are stored in row-major order (last subscript varies fastest).

From the above we can conclude that a 2D array is actually a 1D array stored in row-major order.

Consequently, it's safe to assume that elements of a sub-array are stored contiguously in memory.

101010
  • 41,839
  • 11
  • 94
  • 168