std.collection lets rename it into std,ridiculous.

[H. S. Teoh]

On Mon, Feb 20, 2012 at 09:33:51AM +0100, a wrote:
> >here's a stack:
> >
> >	T[] stack;
> >	void push(elem) {
> >		stack ~= elem;
> >	}
> >	T pop() {
> >		T elem = stack[$-1];
> >		stack = stack[0..$-1];
> >		return elem;
> >	}
> 
> Won't this reallocate every time you pop an element and then push a
> new one?
[..]

Nope, it doesn't. That's the power of D slices. When you create a
dynamic array, the GC allocates a certain amount of memory, let's call
it a "page", and sets the array to point to the beginning of this
memory. When you append to this array, it simply uses up more of this
memory. No reallocation actually occurs until the page is used up, at
which point the GC allocates a larger page to store the array in.

This scheme means that this code is very efficient for small stacks,
because there's no repeated allocation/deallocation (which if you ever
played with malloc/free, you'd know are expensive), just updating a few
pointers. For large stacks, the reallocations only take place
occasionally, so even in that case performance is still pretty good.


T

-- 
If you want to solve a problem, you need to address its root cause, not just its symptoms. Otherwise it's like treating cancer with Tylenol...