Re: std way to remove multiple indices from an array at once

[Nicholas Wilson via Digitalmars-d-learn]

On Thursday, 21 December 2017 at 00:23:08 UTC, Steven 
Schveighoffer wrote:
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

isn't that n log(m), where n is length of array and m is length 
of indices?

If indices is sorted with no duplicates and random access then 
you can do it in linear time.

int i;
int ii;
int[] indicies = ...;
arr = arr.filter!((T t)
{
    scope(exit) i++;
    if (i == indicies[ii])
    {
        ii++;
        return false;
    }
    return true;
}).array;