Is an array of vectors entirely contiguous memory?

Question

I know vectors are guaranteed to be contiguous memory, and so are arrays. So what happens when I do something like this:

std::vector<uint8_t> my_array[10];
my_array[2].push_back(11);
my_array[2].push_back(7);

What would the memory look like? If both need to be contiguous, would every element of the array after my_array[2] be pushed forward a byte every time I do a push_back() on my_array[2]?

Would this be the same situation as when I have an array of structs, where the structs have a member that has a variable size, such as a string or another vector?

Answer 1

Memory footprint of std::vector consists of two parts:

• The memory for the std::vector object itself (very small, and independent of the size), and
• The memory for the data of the vector (depends on the number of elements in the vector).

The first kind of data will be contiguous in an array; the second kind of data is allocated dynamically, so it would not be contiguous in an array.

This would not be the same as with a C struct that has a flexible data member, because the data portion of std::vector is not always allocated in the same kind of memory, let alone being adjacent to it. The vector itself may be allocated in static, dynamic, or automatic memory areas, while its data is always in the dynamic area. Moreover, when vector is resized, the memory for its data may be moved to a different region.

Each time you call push_back, std::vector checks if it has enough dynamic memory to accommodate the next data element. If there is not enough memory, then the vector allocates a bigger chunk of memory, and moves its current content there before pushing the new item.

Answer 2

The vector memory structure is contiguous in memory; however std::vector's all contain a pointer pointing to dynamically allocated memory for the actual storage (which is very very likely not contiguous).

Knowing this, std::vector::push_back will only check to see if the (external) dynamically allocated array has enough capacity to hold the new item, if not it will reallocate space. A push_back on the first vector that overflows will not cause the second vector in the array to reallocate memory, that isn't how it works.

Also, there is no such thing as a struct having a variable size, the size of structures and classes have to be known at compile time.

std::string also has a fixed size, although you may think it is variable, because it also (like vector) has a pointer to the char* it contains.