This is the mail archive of the libstdc++@gcc.gnu.org mailing list for the libstdc++ project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: Amortized Analysis


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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]