Std::Vector of Std::Vectors Contiguity

std::vector of std::vectors contiguity

No. The elements of a vector are stored in a dynamically allocated block of memory; otherwise, the capacity of the vector could not increase. The vector object just holds a pointer to that block.

The requirement that the elements be stored sequentially applies only to the elements themselves, and not to any dynamically allocated members of those elements.

Would vector of vectors be contiguous?

In short, no. This is what actually happens:

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

2d std::vector Contiguous Memory?

The overhead size of a vector is not 0. You have 24 bytes between the last element of your vector and the first element of the next vector. Try this:

cout << sizeof(std::vector<int>) << endl;

You will find the output to be 24 (Likely for your implementation of std::vector and compiler etc). Live example which happens to match.

You can imagine the vector layout like this:

If you want your elements to actually be contiguous then you need to do:

1. Use a std::array<std::array<int>> for no overhead (c++11 only). Note that this cannot be resized.
2. Use std::vector<int> and the formula row * numRows + col to access the element for row, col.

std::vector contiguous meaning

Contiguous in this context means that sequentially numbered vector's elements are located next to each other in memory space. For example, if an element i is located at the address a, and has a size of s, then the element i+1 would be located at the address a+s, the element i+2 would be at a+s+s, and so on.

This is important for two reasons:

• Contiguous requirement makes random access possible - you can compute the location of any element based on vector's base address and element's index
• You can predict locality of reference - processing vector elements sequentially is the same as processing array elements sequentially for the purposes of cache behavior analysis.

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

Vector of vectors memory layout

A std::vector<T> internally stores a pointer to dynamically allocated memory. So while the elements of a single std::vector<T> will be continuous in memory there is no relationship to any pointers that those elements store themselves.

Therefore a std::vector<std::vector<T>> will not have the elements of the "inner vectors" stored continuously in relation to each other. It would also be impossible for a resize of one of those "inner vectors" to affect the others, since at the point where the resize happens there is no information about any relationship to other std::vector<T> objects.

On the other hand a std::array is a (thin) wrapper around a C-style array and uses neither dynamic allocation nor is resizable, so a std::array<std::array<T,N>,N> will have the same memory layout as a T[N][N] array.

Why is std::vector contiguous?

If std::vector didn't guarantee contiguousness, a new container would be invented which did.

The contiguity guarantee makes it easier to inter-operate with existing code that expects a contiguous array, and also gives very good performance because it is cache-friendly. (Inserting/deleting in the middle is in practice very fast for moderate sizes because of this.)

Copying the array on expansion is surprisingly cheap - if you append to a vector a million elements one at a time, each element will have been copied on average around once.

---

Related Topics