Efficiency of using array as stack

[Ivan Kazmenko]

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.