[1]Howard E. Hinnant
    2006-02-14
     __________________________________________________________________

             Growth Factor deriviation for reallocating a buffer


template <typename T, class Allocator>

typename some_container<T, Allocator>::size_type

some_container<T, Allocator>::grow_by(size_type n)

{

    const size_type m = max_size();

    const size_type c = capacity();

    if (n > m - c)

        base::throw_length_error();

    const size_type m3 = m / 3;

    if (c < m3)

        return c + std::max(3*(c+1)/5, n);

    if (c < m3*2)

        return c + std::max((c+1)/2, n);

    return m;

}


   The rationale for the 1.6 growth factor stems from an argument that
   Andrew Koenig has made: If you do nothing but continually grow a buffer
   by 2, freeing the old buffer, the new buffer will never fit into the
   spaces already deallocated. It will always be too large. So Andy
   computed what the largest growth factor could be such that after a
   while, the deallocated buffers (assuming they were coalesced by the
   heap manager) satisfy the request for the new buffer. The factor (f)
   can be derived by considering the current buffer size: S[i], and how it
   relates to the previous buffer size:

     S[i] = f S[i-1]

   Which also can be expressed:

     S[i] = f S[i-1] = f^ i S[0]

   Now for some i we want the sum of all previous buffers to be greater
   than or equal to the next buffer size:

     ���[j=0]^i-1 S[j] >= S[i+1]

   Substituting in f and S[0]:

     ��[j=0]^i-1 f^ j S[0] >= f^ i+1 S[0]

   The initial buffer size S[0] is known to be positive and can be
   factored out of the equation.

     ��[j=0]^i-1 f^ j >= f^ i+1

   The summation on the left hand side can be algebraically simplified:

     (f^ i - 1) / (f - 1) >= f^ i+1

   The growth factor f is known to be greater than 1, so we can multiply
   through by the denominator of the left hand side:

     f^ i - 1 >= f^ i+1 (f - 1)

   Expand and rearrange:

     0 >= f^ i+2 - f^ i+1 - f^ i + 1

   For sufficiently large i, the constant factor 1 can be neglected, and
   then a factor of f^ i can be factored out:

     0 >= f^ i (f^ 2 - f - 1)

   Since f^ i is known to be positive we can simplify to:

     0 >= f^ 2 - f - 1

   This equation can be solved for f, picking the root that is greater
   than 1, we obtain:

     1 < f <= (1 + ���5) / 2

   or

     1 < f <= 1.618033989...

   Dinkumware has repeatedly advertised that they are using a growth
   factor of 1.5, based on this same argument (for vector and string).

References

   1. mailto:howard.hinnant@gmail.com