Arrays are sufficient for ArrayLists? Really??

[Timon Gehr]

Mehrdad wrote:
> Timon:
> > What about:
> void removeAt(T)(ref T[] arr, size_t index)
> {
>    foreach (i, ref item; arr[1 .. index+1])
>         item = arr[i - 1];
>     arr = arr[1 .. $]; //note how no valid data is beyond the end of the array
> }
>
> Clever, but if you do this with a big enough number of items, you'll
> exhaust all memory. Be careful. :P

Total memory usage is at most 2 times the maximum size the array reaches during
its lifetime. Test it.
Arguably, this is not a very good guarantee, because you might have multiple
arrays that oscillate from big to small with some offset.
But I was only trying to improve on runtime.

Btw: removing an element always takes linear time. relocating happens only
straight after removal and takes, well, linear time. In an asymptotic view, your
implementation performs optimally, while never using too much memory.

Timon