How is a Vector of Vector aligned in memory?

Question

I understand as Set size of vector of vectors at run time describes, one can declare vector of vector as

vector<vector<int> > ref;

then resize the first level by

ref.resize(i);

and push element at the 2nd level:

ref[i].push_back(23);

But how are vector of vector aligned in memory?

For simple vector, it's a container and align its element continuously, like an array; but in the case of vector of vector, I couldn't see the picture.

As the size of each inner vector (the vector in vector of vector) size might change, does the outer vector of vector (the vector in vector of vector) align inner vectors continously? Does the outer vector researve memeory space for each inner vector? what if one vector overshoot?

Answer 1

The size of the vector<int> struct that is stored in ref is constant. Common implementations has this as three pointers, or around 12 bytes on 32-bit architectures, or 24 bytes on shiny new 64-bit architectures.

So ref manages roughly ref.capacity() * 12 bytes of continuous storage.

Each element/vector<int> in ref manages its own integers independent of the elements ref manages. In the artistic rendering below ref.size() == ref.capacity() for the sake of simplicity.

So your

ref.resize(i);

only affects the top row. Your

ref[i].push_back(23);

only affects the i-th column.

Answer 2

vector<vector <int>> m;

1. The inner vector or rows are implemented as independent objects on the free store.
2. Elements in each row are compactly stored, capable of performing dynamic allocation through push_back and resizing.
3. It is not necessary for each inner vector in the vector< vector<int> > to have the same size. So, the inner-vectors (not their elements) are not stored contiguously. That means, the first element of m[i] is not stored in the address immediately next to the last element of m[i-1].

does the outer vector of vector (the vector in vector of vector) align inner vectors continously?

No. See point#2

Does the outer vector researve memeory space for each inner vector?

No. See point#1. you need to resize or do push_back into inner vector.

how are vector of vector aligned in memory?

vector<T> vec;

consumes this much memory

sizeof(vector<T>) + (vec.size() ∗ sizeof(T))

where,

sizeof(vector<T>) = 12 bytes

and T is vector<int> for a vector of vector.

So, the memory consumed for a 3-by-4 vector<vector<int>> would be.

 = sizeof(vector<vector<int>>) + (vec.size() * sizeof(vector<int>))
 = 12 + 3 * 12 
 = 48 

what if one vector overshoot?

vector.resize function corrupting memory when size is too large

Answer 3

A vector<vector<int>> could look like this in memory:

+-+-+-+
|b|e|c|  vector<vector<int>
+-+-+-+ 
 | | |
 | | +-------------------+
 | |                     |
 | +---------------+     |
 |                 |     |
 V                 V     V
+-+-+-+-+-+-+-+-+-+
|b|e|c|b|e|c|b|e|c|  3x vector<int>
+-+-+-+-+-+-+-+-+-+ 
 | | | | | | | | |
 | | | | | | | | +-------------+
 | | | | | | | |               |
 | | | | | | | +-------+       |
 | | | | | | |         |       |
 | | | | | | V         V       V
 | | | | | |+-+-+-+-+-+      
 | | | | | ||i|i|i|i|i|   5x int   
 | | | | | |+-+-+-+-+-+      
 | | | | | |       
 | | | | +-+---+ 
 | | | |       | 
 | | | V       V 
 | | |+-+-+-+-+  
 | | ||i|i|i|i|  4x int
 | | |+-+-+-+-+
 | | |
 | +-+-----------+
 |               |
 V               V
+-+-+-+-+-+-+-+-+
|i|i|i|i|i|i|i|i|  8x int
+-+-+-+-+-+-+-+-+

Here b denotes the begin() poiner, e denotes the end() pointer and c denotes the capacity() pointer.

You see, that the rows are not contiguous in memory as you would expect from a matrix structure. Every vector (inner and outer vectors) takes care of it's own memory allocations. The outer vector does not care about what it's elements are doing.