This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: vector<> can probably never grow to it's maximum size!
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