Two-Dimensional vector in C++ – inefficient with dynamic-sized sub vectors?

Question

I know that std::vector uses a contiguous block of memory, but I often see people use vectors of vectors, even when they modify the number of elements in these vectors contained within an outer vector. Won't this lead to efficiency problems when an inner vector need to be resized as all the following vectors will have to have their elements moved as well?

In other words, in the following code, won't growing lists[0] trigger the moving of the elements of the 99 sub vectors following it too, and not just lists[0]?

std::vector<std::vector<int>> lists;
lists.resize(100);

// use and grow sub vectors
// ...
lists[0].push_back(88); // ← !

Answer 1

std::vector stores its elements in a contiguous block of memory as you described, but that doesn't mean that the whole vector object resides in a contiguous piece of memory. While it's implementation dependent, it's most likely safe to assume that the vector object itself contains some data that is mostly "management overhead" like the size of the vector and a pointer to the payload data instead of the payload data itself. That way it's much easier to do efficient move assignments or reallocations.

For example if you look at the vector implementation in Visual C++, you'll find that its data members are actually just a few pointers.

So in your scenario of a vector of vectors, the data stored in the "inner" vector simply contains the management data but not the payload for the nested vector. Thus, extending or shrinking the nested vector will not cause elements in the outer vector to move around in memory.

Answer 2

Each std::vector stores its elements in a contiguous heap allocation. This means the element data is separate from the object member data (remember, locally declared std::vector's are allocated on the stack, not the heap...). That is what allows a std::vector to be dynamically resized -- note that C/C++ has no provision for resizing a struct!

So, in a std::vector< std::vector<int> >, the outer std::vector stores an array of fixed-size std::vector<int> datastructures in its heap allocation. Each of those vectors manages its own heap-allocated array of int, separately from its "parent" or any of its "siblings".

Answer 3

The mechanism described by Timo is accurate, but it may help to consider that changing vector.size() cannot change sizeof(vector), because the latter has to be a compile-time constant.

Conversely, if your 2D array was really a contiguous int[HEIGHT * WIDTH], changing the width would require reorganising everything.