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;

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

3 Answers 3


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.

  • In G++, each vector has three pointers. A pointer to the start of the memory block, a pointer to the end of the memory block, and a pointer to the last part of the memory block currently used by the vector. May 8, 2013 at 19:14
  • That seems to mirror the implementation in Visual C++ 2010 that I briefly looked at. Looking at minimizing the overhead for the implementation that's the way that makes most sense to me, too. May 8, 2013 at 19:25

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


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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.