Re: how does reserve() work?
On Apr 14, 1:24 am, JDT <jdt_yo...@yahoo.com> 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: james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34