Is the Data in Nested Std::Arrays Guaranteed to Be Contiguous

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

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.)

Does std::array of std::array have contiguous memory?

According to the standard the memory should be contiguous. The 26.3.7.1 [array.overview] paragraph states (emphasis mine):

The header defines a class template for storing fixed-size
sequences of objects. An array is a contiguous container. An instance
of array stores N elements of type T, so that size() == N is an
invariant.

Update: It appears the implementation might include the padding.
More info on the subject in these SO posts:

Is the size of std::array defined by standard?

and specifically this answer:

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

Is the memory in std::array contiguous?

Yes, it is contiguous, as it is basically (and actually) a type arr[10];, but with STL like interface. It also doesn't decay to a pointer on the slightest provocation.

You can safely pass &arr[0] to a function expecting a C-style array, that's the design goal of it. To use it with the STL algorithms however, just use the begin and end functions:

// either members
std::sort(arr.begin(), arr.end());
// or free from <iterator>
std::sort(std::begin(arr), std::end(arr));

---

For the language lawyer part, §23.3.2.1 [array.overview] p1:

The header <array> defines a class template for storing fixed-size sequences of objects. An array supports random access iterators. An instance of array<T, N> stores N elements of type T, so that size() == N is an invariant. The elements of an array are stored contiguously, meaning that if a is an array<T, N> then it obeys the identity &a[n] == &a[0] + n for all 0 <= n < N.

And §23.3.2.1 [array.overview] p2:

An array is an aggregate (8.5.1) that can be initialized with the syntax

• array<T, N> a = { initializer-list };

Also, in p3, listing the members of std::array:

T elems[N]; // exposition only

[ Note: The member variable elems is shown for exposition only, to emphasize that array is a class aggregate. The name elems is not part of array’s interface. —end note ]

Is a vector of arrays contiguous?

Is a vector of arrays contiguous?

No, it is not. std::array may contain padding or even additional members at the end. More details, e.g., here:

• Is the data in nested std::arrays guaranteed to be contiguous?
• Is the size of std::array defined by standard

---

But I believe this is very unlikely to happen and you can simply check such situations by comparing 2 * sizeof(double) with sizeof(std::array<double, 2>).

Are the data elements of nested std::initializer_lists guaranteed to be contiguous?

C++11 § [support.initlist] 18.9/1 specifies that for std::initializer_list<T> iterator must be T*, so you are guaranteed that sequential elements in a single initializer_list are contiguous.

In the case of nested lists, e.g., std::initializer_list<std::initializer_list<int>>, there is no requirement that all elements are contiguous. The top-level list's begin() must return a pointer to a contiguous array of std::initializer_list<int>, and each of those lists' begin() must return a pointer to a contiguous array of int. Those second-tier int arrays could be scattered all over memory or stored precisely in total order exactly as you observed. Both ways are compliant.

What is the memory layout of vector of arrays?

Arrays do not have any indirection, but just store their data "directly". That is, a std::array<int, 5> literally contains five ints in a row, flat. And, like vectors, they do not put padding between their elements, so they're "internally contiguous".

However, the std::array object itself may be larger than the set of its elements! It is permitted to have trailing "stuff" like padding. So, although likely, it is not necessarily true that your data will all be contiguous in the first case.

An int
+----+
|    |
+----+

A vector of 2 x int
+----+----+----+-----+        +----+----+
| housekeeping | ptr |        | 1  |  2 |
+----+----+----+-----+        +----+----+
                   |          ^
                   \-----------

An std::array<int, 5>
+----+----+----+----+----+----------->
| 1  |  2 |  3 |  4 |  5 | possible cruft/padding....
+----+----+----+----+----+----------->

A vector of 2 x std::array<int, 5>
+----+----+----+-----+        +----+----+----+----+----+----------------------------+----+----+----+----+----+----------->
| housekeeping | ptr |        | 1  |  2 |  3 |  4 |  5 | possible cruft/padding.... | 1  |  2 |  3 |  4 |  5 | possible cruft/padding....
+----+----+----+-----+        +----+----+----+----+----+----------------------------+----+----+----+----+----+----------->
                   |          ^
                   \-----------

And, even if it were, due to aliasing rules, whether you'd be able to use a single int* to navigate all 10 numbers would potentially be a different matter!

All in all, a vector of ten ints would be clearer, completely packed, and possibly safer to use.

In the case of a vector of vectors, a vector is really just a pointer plus some housekeeping, hence the indirection (as you say).

Are std::vector elements guaranteed to be contiguous?

This was missed from C++98 standard proper but later added as part of a TR. The forthcoming C++0x standard will of course contain this as a requirement.

From n2798 (draft of C++0x):

23.2.6 Class template vector [vector]

1 A vector is a sequence container that supports random access iterators. In addition, it supports (amortized)
constant time insert and erase operations at the end; insert and erase in the middle take linear time. Storage
management is handled automatically, though hints can be given to improve efficiency. The elements of a
vector are stored contiguously, meaning that if v is a vector where T is some type other
than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().

Is this nested array using stack or heap memory?

There is no stack. Don't think about a stack. What matters is whether a given container class performs any dynamic allocation or not.

std::array<T,N> doesn't use any dynamic allocation, it is a very thing wrapper around an automatically allocated T[N].

Anything you put in a vector will however be allocated by the vector's own allocator, which in the default case (usually) performs dynamic allocation with ::operator new().

So in short, vector<array<char,N>> is very simiar to vector<int>: The allocator simply allocates memory for as many units of array<char,N> (or int) as it needs to hold and constructs the elements in that memory. Rinse and repeat for nested vectors.

---

For your "additional questions": vector<vector<T>> is definitely not contiguous for T at all. It is merely contiguous for vector<T>, but that only contains the small book-keeping part of the inner vector. The actual content of the inner vector is allocated by the inner vector's allocator, and separately for each inner vector. In general, vector<S> is contiguous for the type S, and nothing else.

I'm not actually sure about vector<array<U,N>> -- it might be contiguous for U, because the array has no reason to contain any data besides the contained U[N], but I'm not sure if that's mandatory.

You might want to ask that as a separate question, it's a good question!

---

Related Topics