Don't use arrays as stacks

[Steven Schveighoffer]

On Tue, 27 Sep 2011 00:22:02 -0400, Nick Sabalausky <a at a.a> wrote:

> "Steven Schveighoffer" <schveiguy at yahoo.com> wrote in message
>>> [1] Why is the capacity set to zero instead of the actual length of
>>> four? I'm not certain, but my guess is that zeroing the value is
>>> slightly faster than copying the length. Either that, or perhaps it has
>>> to do with the fact that the slice doesn't actually "own" the data.
>>
>> It was an arbitrary decision, but actually serves as an important
>> differentiator.  0 simply means "any append to this array will
>> reallocate".  capacity == length would mean the same thing, but has the
>> distinction of knowing that the length is the actual block length.
>
> Or rather that the *end* of the array is the *end* of the actual block,
> right? (Since the array could also have some of first X elements sliced
> off.)

Yes, that's a better description.

>>> One caveat about this method: If you save a slice of the stack, pop
>>> elements off the stack, and then push new values back on, the old slice
>>> you took will likely [4] reflect the new values, not the original ones.
>> ...
>>> [4] I say "likely" instead of "definitely" because of an unfortunate
>>> indeterminism inherent in D's array/slice system. This quirk is
>>> explained in the "Determinism" section of Steven Schveighoffer's  
>>> article
>>> mentioned above.
>>
>> Actually, with the new functions capacity, assumeSafeAppend, and  
>> reserve,
>> most of the "non-determinism" is mitigated.  In your case, however, you
>> know you have control of the stack, and all its data, popping and  
>> pushing
>> will *definitely* overwrite the old value.
>>
>
> But when the stack grows past its currently-allocated size and it needs  
> to
> expand (ex: from 1024 to 1500, in order to accomodate that 1025th  
> element),
> there's still a chance it would get moved to a different memory location,
> right? In which case, if you then pop all the way back to 900, and then  
> push
> 100 or so back again, *now* any slice that *had* been pointing to the
> original, say, [920..970] will no longer be pointing to the new values,
> they'll still be pointing to the old values, right?
>
> So, for instance, you can't take an instance on my Stack struct, do "foo  
> =
> stack[0..10]", and then say "foo is guaranteed to always point to the  
> bottom
> 10 elements of stack (at least until you change foo)". Right? That's  
> what I
> was referring to with that footnote [4]. To make that kind of guarantee,
> you'd have to specifically code the Stack class so that all slices of the
> Stack get updated whenever the Stack's data gets moved.

There's never a guarantee that a slice will always point at the current  
values.  There can't be, because you can never guarantee it will not be  
reallocated on expansion.

But what I thought you were talking about is popping values off, and then  
pushing values on, without exceeding the capacity.  In fact, you would be  
guaranteed the slice contains the newer values, even if a reallocation  
occurs, since you have to push values into the slice before exceeding the  
capacity.

The situation you describe in this reply is, take a slice, push elements  
on exceeding capacity, then pop elements back, then push elements on.   
Quite different :)

You could create a "stack slice" which instead of pointing at the memory,  
points at the stack aggregate itself (which would actually have to be  
heap-allocated), and have the lower and upper bounds.  Then a "slice" of  
that type would continue to point at the current data.

-Steve