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