On Saturday, 23 March 2013 at 13:55:57 UTC, H. S. Teoh wrote:
Alternatively, you should not shrink the array, but keep
another counter on how much of the array is being used,
so that you can reuse the space immediately without
risking reallocation. Here's an example array-based
stack implementation that does this: <...>
That looks good. However, I'd relocate on shrinking too if we
use less than say one fourth of the space. Consider, for
example, one million values constantly moving between one million
stacks; the worst case space usage would be million-squared if we
only grow the internal arrays but never shrink them. Or would
that be a very rare usage pattern requiring a custom
implementation anyway?
My problem was that I thought D2 is mature enough to have a
working stack out-of-the-box. I initially searched for a stack
in std.container, found none there, and then realized a dynamic
array could do. Well, it surely does the job, but with a quirk
(assumeSafeAppend sufficed for my usage) which is not obvious at
all for a newcomer like me. So, it seems to me that such a
container (on top of an array) would be useful in Phobos.
-----
Ivan Kazmenko.
