Re: [RFC] Vector (string?) growth factor of 1.5 (insted of 2)

[Matt Austern <austern at apple dot com>]

On Feb 3, 2004, at 5:11 AM, Dhruv Matani wrote:

> On Tue, 2004-02-03 at 05:41, Paolo Carlini wrote:
> > Gabriel Dos Reis wrote:
> >
> > > if the only thing you have is a genuine input iterator you're
> > > effectively stuck. However, if you have at least a bidirectional
> > > iterator, then you can have an idea of the amount staorage you need.
> > > We already have dispatchers that compute those iterator categories.
> > > It might be a good idea to take advantage of them.
> >
> > Ok. I think that, by and large, we already do our best, both in
> > string and in vector...
> >
> > A detail comes to my mind, though: perhaps, at construction time,
> > speed matters more and, in the case of the constructor from input
> > iterators, we should allow for a bigger factor. Later, memory usage
> > matters more and a smaller factor seem in order (-> as you say, if
> > the max speed is really needed reserve is always available, then).
>
> Yes. This seems to me to be a really nice suggestion! Make the growth
> factor inversely proportional to the size of the vector.

I don't think that is a good suggestion.  In fact, I don't think it is 
standard
conforming.

It's easy to prove that if you have a constant growth factor, i.e. if 
you're
using exponential growth, then adding one element is amortized
constant time, as required by the standard.  That is, the number of
copies you perform when you add N elements at a time is O(N).

If you're using a growth factor inversely proportional to the size of 
the
vector, then you've no longer got exponential growth.  The number of
copies for adding N elements will be superlinear, meaning that adding
a single element is no longer amortized constant time, which violates
the standard.

Exercises for the reader:
1. If you've got a growth factor g, then the number of copies you have
to make when adding N elements, one at a time, approaches k N.
Find k as a function of g.

2. If your growth factor is inversely proportional to the current size 
of
the vector, then how many copies do you have to make if you're
adding N elements one at a time?

(I know the answer to exercise 1.  I don't know the answer to exercise
2.  My guess would be something like N log N, because this problem
feels more or less like the integral of 1/x.)

				--Matt