On 4/4/22 7:15 PM, Enjoys Math wrote:
https://forum.dlang.org/post/eih04u$1463$1...@digitaldaemon.com
A version of the code that takes `T which` as a parameter instead of
`int index`.
```
// remove an item from an array
template drop(T)
{
T drop( inout T[] arr, T which )
Note to reader: this is D1 code, so `inout` was equivalent to `ref`.
{
int i;
T result;
for (i=0; i < arr.length; i++)
{
if (arr[i] == which)
{
result = arr[i];
break;
}
}
debug if ( which >= arr.length)
I think this is a bug, it should be `i` you are testing.
throw new Exception(str.format("Attempt to drop the %s of value
%s from an array, but it was not found.", typeid(T), which));
}
this looks like a stray brace?
for (; i < arr.length; i++)
{
arr[i] = arr[i + 1];
}
arr.length = arr.length - 1; >
return result;
}
}
```
It has worse case complexity O(2n) = O(n) whereas the other one can run
in half as long minimally and sometimes just as long (but still O(n)),
but usually one needs to linear search for the entry first.
No, it's O(n) straight up, you are only iterating the entire array once.
As others mentioned, std.algorithm.remove can do this now. I'm not
entirely sure of the benefit of returning the thing you tried to remove,
though I suppose if the parameter defines equality with some extra data
that isn't considered, maybe that does help you see what was removed?
I'd implement it probably like this (for D2):
```d
auto drop(T)(ref T[] arr, T which)
{
import std.algorithm, std.range;
auto f = arr.find(which);
debug if(f.empty) throw ...;
auto result = arr.front;
arr = arr.remove(&f[0] - &arr[0]); // god I hate this
return result;
}
```
Still O(n).
-Steve
