On Tue, Oct 08, 2019 at 08:42:22PM +0000, mipri via Digitalmars-d-learn wrote:
> On Tuesday, 8 October 2019 at 10:48:45 UTC, Jonathan M Davis wrote:
> > The result of this is that code like
> >
> > stack.popBack();
> > stack ~= foo;
> > stack ~= bar;
> > stack.popBack();
> > stack ~= baz;
> >
> > will end up allocating all over the place. Every time you
> > append to the array after shrinking it, you're going to end up
> > with the GC allocating a new block of memory instead of
> > appending in place.
> >
>
> Thanks as well! I thought the code I posted would only allocate when
> the array ran out of capacity. And I see how, even if that's worked
> around with assumeSafeAppend, it becomes a bad idea to define the
> stack functions against `ref T[]` as this makes it too easy for other
> code to slice the array and cause the bugs that assumeSafeAppend
> allows.
IMO, the best way to implement a stack using built-in arrays is to wrap
the array inside a struct that separately keeps track of the last
element. Something like this:
// Warning: untested code
struct Stack(T) {
private T[] impl;
private size_t idx;
...
void push(T t) {
if (impl.length <= idx)
impl.length = ...; //expand by some amount
impl[idx++] = t;
}
T pop() in(idx > 0) {
// ... optional: reduce impl.length if idx /
// .length ratio smalle than some threshold.
return impl[idx--];
}
}
T
--
LINUX = Lousy Interface for Nefarious Unix Xenophobes.
