Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C++ (http://www.velocityreviews.com/forums/f39-c.html)
-   -   Question about memory allocation in std::vector<T> (http://www.velocityreviews.com/forums/t590881-question-about-memory-allocation-in-std-vector-t.html)

ciccio 02-11-2008 10:44 AM

Question about memory allocation in std::vector<T>
 
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. 02-11-2008 11:23 AM

Re: Question about memory allocation in std::vector<T>
 
ciccio <no_valid_email@spam.com> wrote:

> 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::push_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 02-11-2008 11:41 AM

Re: Question about memory allocation in std::vector<T>
 
Daniel T. wrote:
> 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. 02-11-2008 01:29 PM

Re: Question about memory allocation in std::vector<T>
 
Juha Nieminen <nospam@thanks.invalid> wrote:
> Daniel T. wrote:


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


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


All times are GMT. The time now is 04:49 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.