Arrays are sufficient for ArrayLists? Really??

[Steven Schveighoffer]

On Mon, 16 May 2011 15:12:17 -0400, Timon Gehr <timon.gehr at gmx.ch> wrote:


>> 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.

You need to do arr.assumeSafeAppend();  Otherwise, the runtime is not  
aware of your invalidation of the last element.

>
> 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 ~=.

Yes, this should solve the problem, depending on the situation.   
Essentially, as long as you are not keeping other references to the array  
you expect to be updated properly (this solution "moves" the original  
pointer to the right each time), it should work.

-Steve