Removing elements from dynamic arrays?

[Steven Schveighoffer]

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