Arrays are sufficient for ArrayLists? Really??

[Timon Gehr]

> 1. Are you sure you need an array rather than a linked list?
>
> Yes. I'm only asking about a functionality already present in every other
language I know (C++'s vector.erase,
> C#'s List.RemoveAt, Java's removeAt) so it's not something out of the blue. ;)
>
> 2. The garbage collector guarantees amortized constant runtime for insertion at
the back of the array.
>
> The problem is that that is _only_ true if the array is NOT a slice of another
array!
>
> As an example, let's say I define:
>
> void removeAt(T)(ref T[] arr, size_t index)
> {
>    foreach (i, ref item; arr[index .. $ - 1])
>         item = arr[i + 1];
>     arr = arr[0 .. $ - 1];
> }
>
> and then I have:
>
> auto arr = [1, 2, 3];
> arr.removeAt(0);
> arr ~= 4;
>
> The last statement ***WILL*** cause a reallocation, so that doesn't help.

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
}

I did not test it but in theory this should give you the amortized constant
guarantee for ~=.

Timon