Dynamic Arrays as Stack and/or Queue

H. S. Teoh hsteoh at quickfur.ath.cx
Tue Oct 8 21:21:49 UTC 2019


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.


More information about the Digitalmars-d-learn mailing list