Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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); // ← !
share|improve this question
add comment

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
    
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. –  Steven Burnap May 8 '13 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. –  Timo Geusch May 8 '13 at 19:25
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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