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

Discussion in 'C++' started by ciccio, Feb 11, 2008.

  1. ciccio

    ciccio Guest

    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?
    ciccio, Feb 11, 2008
    #1
    1. Advertising

  2. ciccio

    Daniel T. Guest

    ciccio <> 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.
    Daniel T., Feb 11, 2008
    #2
    1. Advertising

  3. 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).
    Juha Nieminen, Feb 11, 2008
    #3
  4. ciccio

    Daniel T. Guest

    Juha Nieminen <> 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.)
    Daniel T., Feb 11, 2008
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chandra Shekhar Kumar

    Re: std::vector memory allocation

    Chandra Shekhar Kumar, Jun 25, 2003, in forum: C++
    Replies:
    0
    Views:
    2,267
    Chandra Shekhar Kumar
    Jun 25, 2003
  2. Andrew Koenig

    Re: std::vector memory allocation

    Andrew Koenig, Jun 25, 2003, in forum: C++
    Replies:
    0
    Views:
    938
    Andrew Koenig
    Jun 25, 2003
  3. Ken
    Replies:
    24
    Views:
    3,831
    Ben Bacarisse
    Nov 30, 2006
  4. Replies:
    8
    Views:
    1,890
    Csaba
    Feb 18, 2006
  5. Rune Allnor
    Replies:
    4
    Views:
    923
    Rune Allnor
    Dec 11, 2008
Loading...

Share This Page