D idom for removing array elements

Dukc via Digitalmars-d-learn digitalmars-d-learn at puremagic.com
Thu Jan 26 05:21:38 PST 2017


On Thursday, 26 January 2017 at 08:22:09 UTC, albert-j wrote:
> What is the D idiom for removing array elements that are 
> present in another array?
>
> Is this the right/fastest way?
>
> int[] a = [1, 2, 3, 4, 5, 6, 7, 4];
> int[] b = [3, 4, 6];
> auto c = a.remove!(x => b.canFind(x));
> assert(c == [1, 2, 5, 7]);

import std.stdio, std.algorithm, std.range, std.array;
int[] a = [1, 2, 3, 4, 5, 6, 7, 4];
int[] b = [3, 4, 6];
auto sortedB = sort(b.dup);
auto c = a
.   filter!(i => !sortedB.contains(i))
.   array
;
assert(c == [1, 2, 5, 7]);

If arrays get large, this should be more efficient since it 
performs O(n * n.log) instead of O(n * n).

On the other hand you could also just use assumeSorted if b is 
already sorted, as in this case. But if you do, I still recommend 
adding an assert to check the range truly is sorted when 
debugging.

It can be made to perform O(n) by sorting both a and b, but then 
you need to figure a way to return a back to normal order after 
filtering. I tried, and found it to be so hard I didn't bother.


More information about the Digitalmars-d-learn mailing list