Amortized Analysis

Raja R Harinath harinath@cs.umn.edu
Sat Jul 7 15:09:00 GMT 2001


Kevin Atkinson <kevina@users.sourceforge.net> writes:
[snip amortized analysis]
> Personally I think all STL containers should have a shrink method so that
> the container can shrink to the exact size needed once you are done adding
> to it.  I know you can always create a new container and make a copy but
> this has the potential to be not as efficient as just freeing the unused
> memory.  Because in some cases this memory can be freed without any
> copying or reallocation being done.  For example in the case of very large
> strings which are allocated with mmap.

I think it can also be shown that automatically halving the space when
75% is unused is compatible with automatic doubling, and maintains
amortized constant-time appends.  IMHO, that may be cleaner rather
than (micro-)managing the memory allocation with 'shrink()'.

- Hari
-- 
Raja R Harinath ------------------------------ harinath@cs.umn.edu
"When all else fails, read the instructions."      -- Cahn's Axiom
"Our policy is, when in doubt, do the right thing."   -- Roy L Ash



More information about the Libstdc++ mailing list