In article <11**********************@g49g2000cwa.googlegroups .com>,

"ma740988" <ma******@gmail.com> wrote:

|| If your vector returns a capacity of zero, then it probably hasn't

pre-allocated any memory.

Does that mean then that each call to push_back results in relocation?

(I understand the reserve case where relocation will happen after

exceeding the capacity).

This program will give you an idea as to how often your vector

reallocates:

#include <iostream>

#include <vector>

int main()

{

std::vector<int> v;

const int N = 1000;

for (int i = 0; i < N; ++i)

{

if (v.size() == v.capacity())

std::cout << v.capacity() << '\n';

v.push_back(0);

}

}

On gcc 4 it prints out:

0

1

2

4

8

16

32

64

128

256

512

Which means: A default constructed vector allocates no memory. On the

first push_back it allocates enough memory for 1 element. After that it

reallocates twice as much memory as it needs when size() exceeds

capacity().

Other possibilities exist. However the capacity() is required to grow

geometrically. That is, as N -> infinity, you should be able to see

that capacity() grows by the relation: new_capacity = k * old_capacity

where k is some constant greater than 1 (in the gcc example, k == 2).

Studies exist which demonstrate that k == (1 + sqrt(5))/2 may be an

optimal growth factor for purposes of recycling free'd memory for vector

use in the absence of other parts of the program requesting memory

between push_backs. I'm aware of another implementation which uses k ==

1.5, which I imagine would print out (but I have not tested):

0

1

2

3

4

6

9

13

19

28

42

63

94

141

211

316

474

711

and yet another that I know prints out:

0

1

2

3

5

8

13

21

34

55

88

141

226

362

579

927

While the slow growth at the beginning of this cycle may appear tedious,

it can actually be beneficial in cases like;

vector<vector<T> > v;

where the inner vectors are expected to be small or even empty. And of

course reserve(N) is always there when you want to override the

automatic transmission.

-Howard