kdelibs/kdecore

Stefan Heimers kde-optimize@mail.kde.org
Wed, 19 Mar 2003 22:27:38 +0100


Am Wednesday 19 March 2003 21:48 schrieb Harri Porten:
> On Wed, 19 Mar 2003, Eray Ozkural wrote:
> > --- kdelibs/kdecore/netwm.cpp  #1.84:1.85
> > @@ -475,5 +475,7 @@ Z &NETRArray<Z>::operator[](int index) {
> >      } else if (index >= sz) {
> >          // allocate space for the new data
> > -        Z *newdata = new Z[index + 1];
> > +        // open table has amortized O(1) access time
> > +        // when N elements appended -- exa
> > +        Z *newdata = new Z[max(2 * sz, index+1)];

> What difference does this patch make ? I don't see how the extra
> space is being used.

If you increase the size of the data structure later, you will not need 
to reallocate each time, only once you hit the 2*sz boundary.

I don't know if this ever happens in this context, but it's a trick also 
used in some string classes, for example QString.

Stefan