This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: Amortized Analysis
- To: Kevin Atkinson <kevina at users dot sourceforge dot net>
- Subject: Re: Amortized Analysis
- From: Raja R Harinath <harinath at cs dot umn dot edu>
- Date: Sat, 07 Jul 2001 17:09:08 -0500
- Cc: David Sankel <camio at yahoo dot com>, <libstdc++ at gcc dot gnu dot org>
- References: <Pine.LNX.4.30.0107071705520.2329-100000@kevins-linux.atkinson.inet>
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