'How is a Vector of Vector aligned in memory?
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?
Solution 1:[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.
Solution 2:[2]
vector<vector <int>> m;
- The inner vector or rows are implemented as independent objects on the free store.
- Elements in each row are compactly stored, capable of performing dynamic allocation through
push_back
andresizing
. - 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 ofm[i]
is not stored in the address immediately next to the last element ofm[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
Solution 3:[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.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
Solution | Source |
---|---|
Solution 1 | |
Solution 2 | Community |
Solution 3 | Ralph Tandetzky |