What's the best strategy for managing Buffer Growth ?
For example, in STL vector class, initially the vector may be allocated some space, when there its run out of space and you want to add new elements, it has to do a *realloc* and then copy all the existing elements over from the old space into the newly allocated space. If at every addition , the vector is just grown by 1, then on an average for a eventual vector of size N, there would have been O(N) reallocs/allocation and each element on an average would have been copied O(N) [Why?]. The same holds whenever the buffer grows by a fixed amount ( say 64 bytes or so ) with some small constant factor advantage. However, if on the other hand, when you run out of space, you realloc (X + X/2) elements, where X is the current size of vector, then it turns out that in the long run, on an average O(logN) reallocs happen and each element is copied on an average twice, where N is the final size of the vector.
n = S(k) = (3/2)* S(k-1). Solve this recurrence to figure out k.
k is the number of iterations/reallocs to reach the size of n
[Reference: More Exceptional C++, Herb Sutter]
No comments:
Post a Comment