[Scummvm-devel] ScummVM 1.0.0: Release status 2009-08-11 -- Full feature, freeze

[Kostas Nakos]

Neil Millstone wrote:
> I also played around with the automatic expansion algorithm of 
> Common::Array.  This template doubles the number of elements it can hold 
> each time it runs out of memory, which strikes me as a little 
> inefficient.

Well, it is a good, in theoretical treatment terms, strategy to double 
the size of a dynamic table on overflow and halve it when the number of 
elements drops below a quarter. This keeps an asymptotic O(N) for a 
sequence of N insert/deletes.

But in practice it might be preferable to pay a little extra in CPU but 
allow the size of the table to grow slower.

Cheers,
Kostas