EDIT 2011.10.27: I'll cut to the chase: You can do it in D, it'll work, but it will be slow because whenever you pop and then push, it will reallocate and copy. And stacks do that frequently. For more details and a solution, read on:
The D programming language has fantastic array features. The ease of using D's arrays makes it very tempting to use them as stacks:
int[] stack = [1, 2, 3];
stack ~= 7; // Push
auto x = stack[$-1]; // Peek
stack = stack[0..$-1]; // Pop (Uses slicing, so it *doesn't* copy any data)
Brilliant! Right? It is, as long as you want an array. But if what you really want is a stack (that is, whenever you'll be doing a lot of pushing and popping), then this is unnecessarily slow. Why? Because of excess allocations.
"Poppycock! Arrays have a reserve capacity which prevents excess allocations."
Yes, but slicing can get in the way of that. Consider this example of using an array as a stack:
import std.stdio;
void info(ref int[] stack)
{
writefln("length %s, capacity %s", stack.length, stack.capacity);
}
void push(ref int[] stack)
{
stack ~= 7;
write("Push: ");
stack.info();
}
void pop(ref int[] stack)
{
stack = stack[0..$-1];
write("Pop: ");
stack.info();
}
void main()
{
int[] stack = [1, 2, 3];
stack.info();
stack.push();
stack.push();
stack.pop();
stack.push();
stack.pop();
stack.pop();
stack.push();
}
That produces the following output with DMD 2.055 Windows:
length 3, capacity 3
Push: length 4, capacity 7
Push: length 5, capacity 7
Pop: length 4, capacity 0
Push: length 5, capacity 7
Pop: length 4, capacity 0
Pop: length 3, capacity 0
Push: length 4, capacity 7
The first three lines look ok: The stack starts with three elements and no extra reserve space. A fourth element is added, but there isn't enough room, so it bumps the capacity up to 7. So there's four elements, with room for three more. Then, when a fifth element is added (sans Bruce Willis, unfortunately), there's already enough space for it, so we get that fifth element without another allocation. Joy!
Then we pop an element off...and the capacity plummets to zero?! WTF?! The reason for this is aliasing. For all the array knows, we might still have a reference somewhere to the full original array, including that fifth element:
int[] stack = [1, 2, 3, 7, 7];
auto stackOriginal = stack;
stack = stack[0..$-1]; // Pop
assert(stack == [1, 2, 3, 7]);
assert(stackOriginal == [1, 2, 3, 7, 7]);
Suppose we now append another value to the stack:
stack ~= 20;
assert(stack == [1, 2, 3, 7, 20]);
assert(stackOriginal == [1, 2, 3, 7, 7]);
In this case, the append must allocate new memory and copy the old data into it. Otherwise, it would clobber the last value of stackOriginal with 20. In other words: After being popped, the stack can no longer guarantee it will still be able to accommodate up to 7 elements without allocating, so its capacity is set to zero [1].
The end result is: Slicing an array is fast, and appending is usually fast [2], but slicing the end off and then appending is slow. But since that's how a stack is normally used, arrays make for slow stacks.
How can you have a fast stack? By handling an array's length and capacity manually. The basic principle works like this:
int[] stack = new int[100];
stack[0..3] = [1, 2, 3];
size_t stackLength = 3;
// Push
stackLength++;
stack[stackLength-1] = 7;
// Peek
auto x = stack[stackLength-1];
// Pop
stackLength--;
That's not as nice, but fortunately those details can be hidden in a templated struct that provides the same syntax as arrays. I've already written such a struct, available in my SemiTwist D Tools project. It's perhaps not as fully-featured as it could be, but it should work in most cases as a drop-in replacement for an array. When I dropped it into the parsing engine for my Goldie Parsing System I got an instant 5x-6x boost in parsing speed [3].
So don't use a plain old array when you want a stack. A proper stack will give you far better performance and memory usage.
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.
Note that Phobos's development has been accelerating for the past year or so, so I wouldn't be surprised to see a superior stack implementation in std.container sometime in the not-so-distant future.
For more information about D's arrays and slicing, see Steven Schveighoffer's award-winning article, D Slices.
[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. Update 2011.09.26: Steven has explained why it's zero.
[2] If you're doing a lot of appending, you may be better off using D's Appender.
[3] This figure is parsing speed alone, not lexing and parsing combined. Your mileage may vary.
[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.
Read more