> 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