I had heard that the
vector class in C++ STL doesn't double every time it needs to resize (as we were taught to do in data structures class), but instead it multiplies the size by 1.5. In a recent article on
comp.lang.c++.moderated, Andrew Koenig explains why. It's related to the golden ratio and the Fibonacci sequence:
From: "Andrew Koenig" <firstname.lastname@example.org> Subject: Re: vector growth factor of 1.5 Newsgroups: comp.lang.c++.moderated Date: 5 Nov 2003 17:26:10 -0500 Organization: AT&T Worldnet There is a technical reason to prefer 1.5 to 2 -- more specifically, to prefer values less than 1+sqrt(5)/2. Suppose you are using a first-fit memory allocator, and you're progressively appending to a vector. Then each time you reallocate, you allocate new memory, copy the elements, then free the old memory. That leaves a gap, and it would be nice to be able to use that memory eventually. If the vector grows too rapidly, it will always be too big for the available memory. It turns out that if the growth factor is >= 1+sqrt(5)/2, the new memory will always be too big for the hole that has been left sofar; if it is <1+sqrt(5)/2, the new memory will eventually fit. So 1.5 is small enough to allow the memory to be recycled.
The authors have been having some trouble getting the patches accepted into the CVS version. I guess I'll just keep applying their patches.