Is the data in nested std::arrays guaranteed to be contiguous?

Question

Is the data in std::array<std::array<T,N>, M> guaranteed to be contiguous? For example:

#include <array>
#include <cassert>

int main()
{
    enum {M=4, N=7};
    typedef std::array<char,N> Row;
    typedef std::array<Row, M> Matrix;
    Matrix a;
    a[1][0] = 42;
    const char* data = a[0].data();

    /* 8th element of 1D data array should be the same as
       1st element of second row. */
    assert(data[7] == 42);
}

Is the assert guaranteed to succeed? Or, to put it another way, can I rely on there being no padding at the end of a Row?

EDIT: Just to be clear, for this example, I want the data of the entire matrix to be contiguous.

Even if the storage is contiguous, I believe you would be falling foul of aliasing rules. See this question I asked many moons ago (about C, admittedly): http://stackoverflow.com/questions/6290956/one-dimensional-access-to-a-multidimensional-array-well-defined-c. — Oliver Charlesworth, Mar 18 '12 at 21:58
possible duplicate of [Is the memory in std::array contiguous?](http://stackoverflow.com/questions/6632915/is-the-memory-in-stdarray-contiguous) by recursion — Lightness Races in Orbit, Mar 18 '12 at 22:07
@LightnessRacesinOrbit : No, I don't think it's a duplicate. While the data in a single `std::array` is contiguous, that doesn't imply that the entire set of data in nested `std::array`s is contiguous. Or at least it's not obvious to a non-language lawyer like me. — Emile Cormier, Mar 18 '12 at 22:15
@Emile: Yes, it does. If every element in an `std::array` is contiguous, then that means every `std::array` in an `std::array>` is directly next to the next one. And, by recursion, each of those "sub"-`std::array`s are contiguous, too. A container doesn't suddenly and magically lose contiguousness (if, indeed, that's a guarantee of the container) just because it's its own `value_type`. _[edit: However, that is not the same as the inner-most `T`s all being contiguous to one another. Seems that's what you meant after all, so, fine :P]_ — Lightness Races in Orbit, Mar 19 '12 at 09:22
@LightnessRacesinOrbit : Like James said in his answer, there is no requirement that there be no padding or extra data members at the end of an `array`, though I admit that decent implementations would not do such a thing. — Emile Cormier, Mar 19 '12 at 15:34

score 19 · Accepted Answer · answered Mar 18 '12 at 22:01

No, contiguity is not guaranteed in this case.

std::array is guaranteed to be an aggregate, and is specified in such a way that the underlying array used for storage must be the first data member of the type.

However, there is no requirement that sizeof(array<T, N>) == sizeof(T) * N, nor is there any requirement that there are no unnamed padding bytes at the end of the object or that std::array has no data members other than the underlying array storage. (Though, an implementation that included additional data members would be, at best, unusual.)

R. Martinho Fernandes · Answer 2 · 2012-03-18T22:35:58.020

5

They are very likely contiguous. If they are not, the compiler is actively fighting you there. There's no guarantee it won't insert padding but there's hardly a reason for it.

Is the assert guaranteed to succeed?

data[7] is an out-of-bounds access (undefined behaviour). The inner array object has only seven elements, so index 7 is not valid.

edited Mar 18 '12 at 22:35

answered Mar 18 '12 at 22:01

R. Martinho Fernandes

228,013
71
433
510

Hmm, your answer seems a bit contradictory (or I'm just too dense). If the data is contiguous, wouldn't `data[7]` point to the first element of the second row? – Emile Cormier Mar 18 '12 at 22:05
@Emile the flaw in thinking "8th element of 1D data array should be the same as 1st element of second row." is ignoring that no array in that code has an 8th element. There's no guarantee as to what `data[7]` will do because of that. In practice, yes, I suspect it will point to the first element of the second row, but as it always is with UB, *you can't safely rely on it*. – R. Martinho Fernandes Mar 18 '12 at 22:10
Ok, then I take "*they are very likely contiguous*" to mean that the data in **each inner array** is contiguous. Is this what you meant? – Emile Cormier Mar 18 '12 at 22:12
And each inner array is also contiguous with each other. But when indexing you can't cross from one to the other. It's not a `std::array` thing. The same is true for `int x[4][7]; int* xp = x; xp[7];`. With "they are very likely contiguous" I meant that no sane compiler will insert any padding. – R. Martinho Fernandes Mar 18 '12 at 22:15
I'm not saying that's false, but it sure seems counter-intuitive to me. If `int x[4][7]` is contiguous, then that means (to me) that the data occupies 28 consecutive slots of `sizeof(int)` bytes in memory. If I do `xp[7]` (which is equivalent to `*(xp+7)`), then it should just dereference the 8th slot in those 28 consecutive slots. Is indexing different than pointer arithmetic followed by dereferencing? – Emile Cormier Mar 18 '12 at 22:22
@Emile Yes, it will *have the same memory layout* as one big array object with 28 elements (like `int x[28]`). But there is no "one big array with 28 elements". There is one array with 4 elements and four arrays with 7 elements. It will probably work, but the standard gives no guarantees. – R. Martinho Fernandes Mar 18 '12 at 22:27
Yes, indexing is pointer arithmetic followed by dereferencing. But `xp+7` is the one-past-the-end pointer of the first inner array, which is not dereferenceable. – R. Martinho Fernandes Mar 18 '12 at 22:29
Thanks for the enlightening clarifications. :-) – Emile Cormier Mar 18 '12 at 22:33
1

@Emile: Just to be clear, and getting back to your original question: I wouldn't mind relying on there being no padding (I don't want to support a compiler that does crazy stuff like that!), because it can actually be tested: `static_assert(sizeof(Matrix) == sizeof(char)*M*N, "nested std::arrays should have no padding");`. I am more weary of relying on indexing as one big array, because that can't be tested (it may work now and usually does, but may fail later when the optimizer decides to take advantage of it to optimize). – R. Martinho Fernandes Mar 18 '12 at 22:50

Is the data in nested std::arrays guaranteed to be contiguous?

2 Answers2

Linked

Related