how does reserve() work?

Discussion in 'C++' started by JDT, Apr 14, 2007.

  1. JDT

    JDT Guest

    Hi,

    My understanding about vector's reserve() is to allocate memory for the
    vector. If so, is it right that each push_back() in the following loop
    causes no memory reallocation and its execution time should be constant
    (i.e. internally, only one value is copied and then the integer "size"
    is increased by one)? Thanks for any help.

    vector<int> v;
    v.reserve(100);
    for (int i=0; i<100; i++)
    v.push_back(i);

    JD
    JDT, Apr 14, 2007
    #1
    1. Advertising

  2. JDT wrote:
    > My understanding about vector's reserve() is to allocate memory for
    > the vector. If so, is it right that each push_back() in the
    > following loop causes no memory reallocation and its execution time
    > should be constant (i.e. internally, only one value is copied and
    > then the integer "size" is increased by one)? Thanks for any help.


    Yes. The value when it's pushed without reallocation is simply
    copy-constructed using "placement new" (in most implementations).

    Most implemenations employ some kind of "hidden" reserve() even
    though you don't use it directly. They usually allocate more memory
    than is immediately needed to prevent frequent reallocations. To
    learn the capacity of the vector (how many elements it can contain
    before next reallocation), call 'capacity' member function.

    > vector<int> v;
    > v.reserve(100);
    > for (int i=0; i<100; i++)
    > v.push_back(i);


    V
    --
    Please remove capital 'A's when replying by e-mail
    I do not respond to top-posted replies, please don't ask
    Victor Bazarov, Apr 14, 2007
    #2
    1. Advertising

  3. JDT

    Guest

    your understanding is perfect --- as it is the same as one of my c++
    books said.
    , Apr 14, 2007
    #3
  4. JDT

    James Kanze Guest

    On Apr 14, 1:24 am, JDT <> wrote:

    > My understanding about vector's reserve() is to allocate memory for the
    > vector. If so, is it right that each push_back() in the following loop
    > causes no memory reallocation and its execution time should be constant
    > (i.e. internally, only one value is copied and then the integer "size"
    > is increased by one)? Thanks for any help.


    > vector<int> v;
    > v.reserve(100);
    > for (int i=0; i<100; i++)
    > v.push_back(i);


    That's correct. More importantly, it is guaranteed that none of
    the push_back's invalidate iterators, references or pointers
    into the vector, e.g.:

    vector< int > v ;
    v.push_back( 0 ) ;
    vector< int >::iterator i = v.begin() ;
    int& r = v[ 0 ] ;
    int* p = &v[ 0 ] ;
    for ( int i = 1 ; i < 100 ; ++ i ) {
    v.push_back( i ) ;
    }

    With the reserve, i, r and p are guaranteed to still be valid
    here. Without the reserve, no.

    In most programs, this is by far the real reason to use reserve.
    The standard requires amortized constant time for push_back
    anyway, so you won't get very many re-allocations, regardless of
    what you do (and, roughly speaking, pushing back 10000 elements
    will take 10 times longer, and no more, than pushing back 1000,
    and 100 times more than pushing back 100). On the other hand,
    an invalid iterator or pointer can be a real pain.

    --
    James Kanze (Gabi Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
    James Kanze, Apr 14, 2007
    #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. dot
    Replies:
    0
    Views:
    404
  2. joeblack
    Replies:
    3
    Views:
    517
    joeblack
    Nov 4, 2003
  3. MarionEll
    Replies:
    0
    Views:
    352
    MarionEll
    Oct 26, 2004
  4. john smith

    vector.reserve

    john smith, Jul 25, 2003, in forum: C++
    Replies:
    5
    Views:
    684
    John Harrison
    Jul 25, 2003
  5. Alex Vinokur

    vector : reserve(LONG_MAX)

    Alex Vinokur, Apr 22, 2004, in forum: C++
    Replies:
    2
    Views:
    444
    Pete Becker
    Apr 22, 2004
Loading...

Share This Page