how does reserve() work?

J

JDT

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
 
V

Victor Bazarov

JDT said:
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
 
H

haijin.biz

your understanding is perfect --- as it is the same as one of my c++
books said.
 
J

James Kanze

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.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,901
Latest member
Noble71S45

Latest Threads

Top