Shrink factor for dynamic array?

Question

Dynamic array usually have a growth factor of 3/2 to 2. But once the memory is allocated, it is never shrank automatically. Would it be pertinent to have a decay factor let's say twice as big as the growth factor? I mean if the number of elements is N times smaller than the decay factor, the array is reallocated (realloc) with a smaller size?

I found plenty of information about dynamic arrays growth, but nothing about the opposite operation.

Answer 1

For a decay factor to make any sense, you would need to expect your array to

• operate for long periods with few elements

• have bursts where much, much more memory is needed

• and other data structures that don't need memory while the array is large.

That is generally not the case. The usual case is either of these:

• The array is grow once, use once, throw away.

• The array is long lived, and frequently changes its length.

• The array is long lived and generally does not grow/shrink much at all.

In all these cases, introduction of a shrink factor would be pure overhead. And that is why such shrink factors are generally not bothered with. Especially since shrink factors have the potential to destroy the O(N) aggregated add time behavior of an exponentially growing allocation.