std way to remove multiple indices from an array at once

Steven Schveighoffer schveiguy at yahoo.com
Thu Dec 21 00:23:08 UTC 2017


On 12/20/17 6:01 PM, aliak wrote:
> Hi, is there a way to remove a number of elements from an array by a 
> range of indices in the standard library somewhere?
> 
> I wrote one (code below), but I'm wondering if there's a better way?
> 
> Also, can the below be made more efficient?
> 
> auto without(T, R)(T[] array, R indices) if (isForwardRange!R && 
> isIntegral!(ElementType!R) && !isInfinite!R) {
>      T[] newArray;
>      ElementType!R start = 0;
>      foreach (i; indices) {
>          newArray ~= array[start .. i];
>          start = i + 1;
>      }
>      newArray ~= array[start .. $];
>      return newArray;
> }
> 
> // Usage
> long[] aa = [1, 2, 3, 4]
> aa = aa.without([1, 3])
> 
> Thanks!

I'm assuming here indices is sorted? Because it appears you expect that 
in your code. However, I'm going to assume it isn't sorted at first.

Now:

import std.range;
import std.algorithm;

auto indices = [1,2,3,4];
aa = aa.enumerate.filter!(a => !indicies.canFind(a[0])).map(a => 
a[1]).array;

Now, this is going to be O(n^2), but if indices is sorted, you could use 
binary search:

auto sortedIdxs = indices.assumeSorted; // also could be = indices.sort()

arr = arr.enumerate.filter!(a => !sortedIdxs.contains(a[0])).map(a => 
a[1]).array;

Complexity would be O(n lg(n))

It's not going to be as good as hand-written code, complexity wise, but 
it's definitely shorter to write :)

-Steve


More information about the Digitalmars-d-learn mailing list