Question about memory allocation in std::vector<T>

[ciccio]

Hi,

I was wondering if std::vector stores its content in a sequential array?


Assume you reserve an std::vector for n places, but you push_back n+m
elements, what happens then?

As far as I know, the mechanism of std::vector will allocate n more
places and stores those m elements in there. But are they continuously
with the first n elements? I.e can I for example ask a pointer to the
first element in the vector and use pointer arithmetic to get to all the
elements in the vector, or are all the blocks extra allocated in
separate memory blocks?

 

[Daniel T.]

I was wondering if std::vector stores its content in a sequential
array?
Yes.

Assume you reserve an std::vector for n places, but you push_back
n+m elements, what happens then?

If vector.size() == vector.capacity() and you push_back another element,
the vector will allocate a new block, copy the first size() objects into
the new block, then push the pushed element on the end. Also,
vector:ush_back is guaranteed to complete in "amortized constant time"
which means that it will generally allocate more than it needs (some
proportion of the total size of the array) so that it won't have to
allocate every time you push a new element into it.

As far as I know, the mechanism of std::vector will allocate n more
places and stores those m elements in there. But are they
continuously with the first n elements?
Yes.

I.e can I for example ask a pointer to the first element in the
vector and use pointer arithmetic to get to all the elements in the
vector, or are all the blocks extra allocated in separate memory
blocks?

The former. The latter is how a deque works.

 

[Juha Nieminen]

The former. The latter is how a deque works.

Actually if you do a reserve() call to a deque AFAIK it's not
guaranteed that it will allocate one contiguous block. Doing direct
pointer arithmetic on deque elements is not valid (although doing it
with deque iterators is).

 

[Daniel T.]

Daniel T. wrote:

Actually if you do a reserve() call to a deque AFAIK it's not
guaranteed that it will allocate one contiguous block. Doing direct
pointer arithmetic on deque elements is not valid (although doing it
with deque iterators is).

There is no reserve for deque. You are otherwise correct (and agreeing
with what I said.)