FIFO stack

[Steven Schveighoffer]

On Thu, 27 Oct 2011 08:00:31 -0400, Nick Sabalausky <a at a.a> wrote:

> "Dominic Jones" <dominic.jones at qmul.ac.uk> wrote in message
> news:j89arh$2ua3$1 at digitalmars.com...
>>> Also an plain array is a good stack. :)
>>
>> I'd rather not use a plain array because (I assume) that when I push
>> or pop using arrays, a swap array is created to resize the original.
>> If this is not the case, then an array will certainly do.
>> -Dominic
>
> The matter of using D's arrays as a LIFO is discussed the other branch of
> this thread (ie, you can do it, but it's slow because a "pop then push"  
> will
> reallocate and copy), but as far as a FIFO: That may actually be  
> reasonable
> to do as an array:
>
> Decreasing the length of an array (from either end) is a trivial matter  
> that
> never allocates or copies. Appending to the end *usually* doesn't involve
> allocating. So the only issue I see it that the FIFO will "march" across
> memory. I guess that's probably not a problem as long as the GC knows it  
> can
> reclaim the stuff you've popped off (Does it do that? Ie, if you do "x =
> x[10..$];" and there's no other references, is the GC smart enough to
> reclaim those first ten spots? I guess I would assume so.)

No, the granularity is on memory blocks.  Once you slice off those first  
10 elements, and you have no references to them, they become dead weight.

But, as you append to the end, it will eventually outgrow its block, and  
the dead weight is *not* carried to the new block, so it will then be  
reclaimed.  There are exceptions (such as when a block tacks on more  
pages).

-Steve