Sunday, November 09, 2003

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" <>
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.

1 comment:

Anonymous wrote at Monday, May 16, 2011 at 2:05:00 PM PDT