vector<> can probably never grow to it's maximum size!

[Dhruv Matani]

On Wed, 2004-10-20 at 22:52, Dhruv Matani wrote:
> On Wed, 2004-10-20 at 22:03, Paolo Carlini wrote:
> > Dhruv Matani wrote:
> > 
> > >>In my opinion, you cannot *always* consider growing 1-item-at-a-time only
> > >>because ::operator new throws. As I already told you, from the point of view
> > >>of the user, that knows nothing about memory and so on, the vector is 
> > >>growing slowly and since you are catching the exceptions he cannot know why.
> > >>    
> > >>
> > >Hmmm. The user may also start wondering why the vector is performing so
> > >many copies.
> > >
> > Which copies?
> 
> If the allocator gives back only __n+1, then the asymptotic complexity
> of the push_back operation will become O(n^2)!

I meant that the function would be O(n), and the loop containing
push_back would be O(N^2).

> 
> Every stage will copy all the previous n elements.
> 
> 
> > 
> > Paolo.
-- 
        -Dhruv Matani.
http://www.geocities.com/dhruvbird/

The price of freedom is responsibility, but it's a bargain, because
freedom is priceless. ~ Hugh Downs