Removing elements from dynamic arrays?

[Chris Nicholson-Sauls]

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