remove from array

[Frits van Bommel]

Thorsten wrote:
>> <totaly untested code>
>>
>> T[] Remove(T)(T[] arr, int i)
>> {
>>    return i==arr.length-1 ? arr[0..$-1] : arr[0..i] ~ arr[i+1 .. $];
>> }
> 
> Sorry, I tried that, and it is too expensive !!
> Because it creates about 3 temporary instances.

Nonsense.
First of all, only one of the last two clauses is even evaluated.
And second, only the second clause allocates, and even then only once. 
Slicing an array doesn't create a copy, it just creates a new (length, 
pointer) pair. Only the '~' allocates, and this is not a temporary but 
the return value.

That function might be improved a bit by also returning a plain slice 
for the case i == 0, but with that change it's perfectly fine as long as 
copy-on-write is acceptable.

If you are certain no copies of the original array (including 
overlapping arrays) will be kept, you can use something like your 
suggestion:

> I would say :
> 
> void Remove(T)(inout T[] arr, int i)
> {
>   for(uint j = i;j < arr.length-1;++j)
>     arr[j] = arr[j+1];
>   arr.length = arr.length - 1;
> }
> 
> can someone accelerate this ???

Using memmove to replace the loop has already been suggested, that 
should usually be fast.
Though consider checking if the removed element is closer to the 
beginning of the array, and if so moving the first part instead of the 
second part followed by "arr = arr[1 .. $]":
---
// warning: untested code
void Remove(T)(inout T[] arr, int i)
{
   if (i < (arr.length / 2)) {
     for(uint j = i; j > 0; --j)
       arr[j] = arr[j-1];
     arr = arr[1 .. $];
   } else {
     for(uint j = i; j < arr.length-1; ++j)
       arr[j] = arr[j+1];
     arr.length = arr.length - 1;
   }
}
---
where the for loops may also be replaced by memmove.
This should perform less memory operations for first-half removals.
However, this has the nasty side effect that using ~= on the resulting 
array will _reallocate_.