Removing elements from dynamic arrays?

[David Medlock]

Chris Nicholson-Sauls wrote:
> Bill Baxter wrote:
> 
>> David Medlock wrote:
>>
>>> Bill Baxter wrote:
>>>
>>>> How do I remove an element from a dynamic array?
>>>>
>>>>    int[] a = [1,2,3,4,5];
>>>>
>>>> I tried every syntax I could think of:
>>>>
>>>>    a[3] = void;
>>>>    a[3..4] = void;
>>>>    a[3..4] = a[3..3];
>>>>    a[3] = [];
>>>>    a[3..4] = [];
>>>>    delete a[3];
>>>>    delete a[3..4];
>>>>
>>>> The last one compiles, but fills a[0] with garbage.
>>>>
>>>> I hope the answer isn't:
>>>>
>>>>    a = a[0..3] ~ a[4..length];
>>>>
>>>> Thanks!
>>>> --bb
>>>
>>>
>>>
>>>
>>>  From my personal tools library...
>>>
>>> // remove an item from an array
>>> template drop(T)
>>> {
>>>   T drop( inout T[] arr, int which )
>>>   {
>>>     debug if ( which>=arr.length)
>>>         throw new Exception(str.format("Attempt to drop position %s 
>>> from size %s",which,arr.length));
>>>     T result = arr[which];
>>>     int max = arr.length-1;
>>>     for (; which < max; which++ ) arr[which]=arr[which+1];
>>>     arr.length= max;
>>>     return result;
>>>   }
>>> }
> 
> 
> Something you might find interesting/indicative -- I wrote a little test 
> program to time your function versus that found in Cashew, and with the 
> slicing expression above.  Output:
> 
> # Array length: 10000
> # Iterations removing middle element: 5000
> #  ---------- Slice syntax: a[0 .. mid] ~ [mid + 1 .. a.length]
> # <Benchmark array removals> Baseline 3.460000
> #  ---------- CashewUtils: a.removeIndex(mid)
> # <Benchmark array removals> Time 2.970000 & 1.164983 versus baseline
> #  ---------- Drop: version 1
> # <Benchmark array removals> Time 0.270000 & 12.814815 versus baseline
> #  ---------- Drop: version 2
> # <Benchmark array removals> Time 0.390000 & 8.871795 versus baseline
> 
> Drop v2 was an attempt of mine at rewriting your .drop() that, 
> obviously, falls a little short of the original in performance.  I also 
> find it odd that Cashew's .removeIndex() is actually timing a little 
> master than the slice expression, because that's actually it is: a 
> wrapper around that very same expression.  *confused*  Anyhow, clearly 
> your .drop() is running very fast!  I actually expected the opposite, 
> and am surprised/impressed.
> 
> Maybe you should release it into Cashew?  ;)  And maybe I should put 
> more into benchmarking the entire Cashew array module.  There might be a 
> few more placed it could be sped up.
> 
>>>
>>> Even though it returns the array, it modifies it in place.
>>>
>>> -DavidM
>>
>>
>>
>> Thanks David, this seems like the best answer in terms of efficiency, 
>> although I suppose the
>>     a = a[0..3] ~ a[4..length];
>> could theoretically be pretty similar depending how the compiler 
>> implements it.
>>
>>
>> There really should be syntax in the language or at least functions 
>> like the above in the standard library for this (and for removing 
>> slices). 
> 
> 
> # import cashew.utils.array;
> #
> # int[] foo = ... ;
> # foo.remove(3U);
> # foo.removeRange(2U, 7U);
> # foo.removeSub(foo[1 .. 5]);
> etc.
> 
> That's why I maintain those.  Hopefully, eventually, it does spawn a 
> standard library module.  (I'm always looking for ways to further 
> optimize them, but I do want to keep them fairly simple.)
> 
> -- Chris Nicholson-Sauls

Its public domain.  Free to use in any way you wish.

-DavidM

For giggles I posted the conditional version(also public domain):

// remove items based on a predicate. returns number of items removed
template drop_if(T)
{
   int drop_if( T[] arr, bool delegate(T)pred )
   {
     int count = 0, dest=0;
     foreach( int index, T val ; arr )
     {
       if ( pred(val) ) { count++; continue; }
       if ( dest !=index ) arr[index] = dest;
       dest++;
     }
     return count;
   }
}