C++ – Efficiency of Two-Dimensional Vectors with Dynamic-Sized Sub Vectors

cc++11stl

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); // ← !

Best Answer

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.