Does D have a Queue and Stack container?

[H. S. Teoh]

On Sun, Jan 13, 2013 at 09:02:38PM +0100, Peter Alexander wrote:
> On Sunday, 13 January 2013 at 19:55:28 UTC, Damian wrote:
> >As per title, it would be awesome if someone could link me to
> >these. I'm quite suprised that D does not already contain these..
> >are there any plans for them joining Phobos?
> 
> Well, a stack is just an array.
> 
> int[] stack;
> stack ~= 1;
> stack ~= 2;
> assert(stack.back == 2);
> stack.popBack();
> assert(stack.back == 1);
> stack.popBack();
> assert(stack.empty);
> 
> If you want strict stack semantics (i.e. *only* allow access to the
> top/back) then you could trivially write a wrapper around an array
> that does this.
[...]

One does have to be careful about performance though: once you pop the
back of an array, appending to the array again will reallocate the
entire array (because the runtime can't tell if something else is
referencing the slice beyond the end of the array). So if you have a
sequence of pop, push, pop, push, ..., it will reallocate the array
every time you push, which is pretty disastrous performance-wise.

The workaround is to use assumeSafeAppend before pushing to the end of
the array -- and make sure there aren't any other slices referencing it,
'cos otherwise other parts of your program may suddenly get unexpected
results. :)


T

-- 
Живёшь только однажды.