www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - D idom for removing array elements

reply albert-j <djftgls ifdflv.com> writes:
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]);
Jan 26
next sibling parent reply Nicholas Wilson <iamthewilsonator hotmail.com> writes:
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]);
filter. auto c = a.filter!(x => !b.canFind(x)).array;
Jan 26
parent Stefan Koch <uplink.coder googlemail.com> writes:
On Thursday, 26 January 2017 at 11:44:27 UTC, Nicholas Wilson 
wrote:
 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]);
filter. auto c = a.filter!(x => !b.canFind(x)).array;
He wanted to remove elements. This will allocate a freaking new array. And do N function calls to build it. This is WORSE!
Jan 26
prev sibling next sibling parent reply Dukc <ajieskola gmail.com> writes:
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.
Jan 26
parent reply albert-j <djftgls ifdflv.com> writes:
On Thursday, 26 January 2017 at 13:21:38 UTC, Dukc wrote:

 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).
It does look much faster than my solution. Will it also work correctly and fast for arrays of custom objects? How should opCmp() be defined if objects don't have a meaningful ordering? The order of elements in the original array does not matter.
Jan 26
next sibling parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Thursday, 26 January 2017 at 23:10:02 UTC, albert-j wrote:
 On Thursday, 26 January 2017 at 13:21:38 UTC, Dukc wrote:

 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).
It does look much faster than my solution. Will it also work correctly and fast for arrays of custom objects? How should opCmp() be defined if objects don't have a meaningful ordering? The order of elements in the original array does not matter.
To me it looks rather slow. please benchmark!
Jan 26
parent reply Dukc <ajieskola gmail.com> writes:
On Friday, 27 January 2017 at 05:48:27 UTC, Stefan Koch wrote:
 To me it looks rather slow.
 please benchmark!
void main() { import std.stdio, std.algorithm, std.range, std.array, std.datetime; int[] a = [1, 2, 3, 4, 5, 6, 7, 4].cycle.take(2000).array; int[] b = [3, 4, 6].cycle.take(2000).array; void originalMethod() { auto c = a.remove!(x => b.canFind(x)); assert(c[0 .. 4] == [1, 2, 5, 7]); } void WilsonMethod() { auto c = a.filter!(x => !b.canFind(x)).array; assert(c[0 .. 4] == [1, 2, 5, 7]); } void myMethod() { auto sortedB = sort(b.dup); auto c = a . filter!(i => !sortedB.contains(i)) . array ; assert(c[0 .. 4] == [1, 2, 5, 7]); } auto r = benchmark!(originalMethod, WilsonMethod, myMethod)(1); foreach(result; r) result.writeln; } resulted in: TickDuration(28085) TickDuration(42868) TickDuration(1509) So, you were correct that the original method is better than Wilsons filter. My method is much better for large arrays I tested here. But what I think you were afraid of is that it needlessly wastes performance by allocating a new array, and I agree. Also, as I said, it could be made O(n).
Jan 27
next sibling parent reply Dukc <ajieskola gmail.com> writes:
On Friday, 27 January 2017 at 08:15:56 UTC, Dukc wrote:
 My method is much better for large arrays I tested here.
Trough, considering the size of the arrays the performance difference should be even greater, like 1000X better instead of 15X better so it's definitely not that great.
Jan 27
parent reply cym13 <cpicard openmailbox.org> writes:
On Friday, 27 January 2017 at 08:30:41 UTC, Dukc wrote:
 On Friday, 27 January 2017 at 08:15:56 UTC, Dukc wrote:
 My method is much better for large arrays I tested here.
Trough, considering the size of the arrays the performance difference should be even greater, like 1000X better instead of 15X better so it's definitely not that great.
Note that if the set of values to be excluded isn't smaller than the haystack then using partition is way faster and your method is the slowest of all. If the order of the array matters stable partition can be used but is slower than the original method. Added test cases and benchmark results: void partitionMethod() { auto c = a.partition!(v => b.canFind(v)); // Sort to recover the order assert(sort(c[0..4]).array == [1, 2, 5, 7]); } void stablePartitionMethod() { auto c = a.partition!(v => b.canFind(v), SwapStrategy.stable); assert(c[0..4] == [1, 2, 5, 7]); } benchmark!(originalMethod, WilsonMethod, myMethod, partitionMethod, stablePartitionMethod)(1) .each!writeln; With "a" of length 4000 and "b" of length 4000: /* int[] a = [1, 2, 3, 4, 5, 6, 7, 4].cycle.take(4000).array; int[] b = [3, 4, 6].cycle.take(4000).array; */ TickDuration(51482830) TickDuration(43634792) TickDuration(1085159) // myMethod is faster TickDuration(44216820) // 3rd TickDuration(42920567) // 2nd With "a" of length 400000 and "b" of length 3: /* int[] a = [1, 2, 3, 4, 5, 6, 7, 4].cycle.take(400000).array; int[] b = [3, 4, 6]; */ TickDuration(312038) // 2nd TickDuration(541912) TickDuration(606883) TickDuration(190662) // partitionMethod is way faster TickDuration(418751) // 3rd
Jan 27
parent cym13 <cpicard openmailbox.org> writes:
On Friday, 27 January 2017 at 15:39:57 UTC, cym13 wrote:
 On Friday, 27 January 2017 at 08:30:41 UTC, Dukc wrote:
 [...]
Note that if the set of values to be excluded isn't smaller than the haystack then using partition is way faster and your method is the slowest of all. If the order of the array matters stable partition can be used but is slower than the original method. [...]
I forgot to say that the main reason to use partition is that it's easy to use it to remove the elements of the array in place: auto r = a.partition!(v => !b.canFind(v)); a.length -= r.length; It just puts the "bad" elements at the end and changes the length of the array.
Jan 27
prev sibling next sibling parent reply albert-j <djftgls ifdflv.com> writes:
On Friday, 27 January 2017 at 08:15:56 UTC, Dukc wrote:

 TickDuration(28085)
 TickDuration(42868)
 TickDuration(1509)
Thank you, this is very helpful. I am also wondering why the standard library doesn't have convenience functions for this, e.g. like Java's removeAll? Now there's more typing than necessary for a relatively common task.
Jan 27
parent reply Dukc <ajieskola gmail.com> writes:
On Friday, 27 January 2017 at 10:20:19 UTC, albert-j wrote:
 I am also wondering why the standard library doesn't have 
 convenience functions for this, e.g. like Java's removeAll? Now 
 there's more typing than necessary for a relatively common task.
That might be a good addition considering how well it can be optimized compared to a naive implementation. Of course, D version of that would accept ranges as input, not only collections.
Jan 27
parent cym13 <cpicard openmailbox.org> writes:
On Friday, 27 January 2017 at 11:56:02 UTC, Dukc wrote:
 On Friday, 27 January 2017 at 10:20:19 UTC, albert-j wrote:
 I am also wondering why the standard library doesn't have 
 convenience functions for this, e.g. like Java's removeAll? 
 Now there's more typing than necessary for a relatively common 
 task.
That might be a good addition considering how well it can be optimized compared to a naive implementation. Of course, D version of that would accept ranges as input, not only collections.
Just to follow up, I've been playing a bit and the fastest I've got so far is: #!/usr/bin/env rdmd import std.conv; import std.stdio; import std.array; import std.range; import std.datetime; import std.algorithm; void main() { int[] a = [1, 2, 3, 4, 5, 6, 7, 4].cycle.take(2000).array; int[] b = [3, 4, 6].cycle.take(2000).array; void originalMethod() { auto c = a.remove!(x => b.canFind(x)); assert(c[0 .. 4] == [1, 2, 5, 7]); } void WilsonMethod() { auto c = a.filter!(x => !b.canFind(x)).array; assert(c[0 .. 4] == [1, 2, 5, 7]); } void myMethod() { auto sortedB = sort(b.dup); auto c = a . filter!(i => !sortedB.contains(i)) . array ; assert(c[0 .. 4] == [1, 2, 5, 7]); } void partitionMethod() { auto c = a.partition!(v => b.canFind(v)); // Sort to recover the order assert(sort(c[0..4]).array == [1, 2, 5, 7]); } void stablePartitionMethod() { auto c = a.partition!(v => b.canFind(v), SwapStrategy.stable); assert(c[0..4] == [1, 2, 5, 7]); } void newPartitionMethod() { auto sortedB = sort(b.dup).uniq.array; auto c = a.partition!(v => sortedB.assumeSorted.contains(v)); assert(c[0 .. 4] == [1, 2, 5, 7], c[0..4].to!string); } void newStablePartitionMethod() { auto sortedB = sort(b.dup).uniq.array; auto c = a.partition!(v => sortedB.assumeSorted.contains(v), SwapStrategy.stable); assert(c[0 .. 4] == [1, 2, 5, 7], c[0..4].to!string); } benchmark!(originalMethod, WilsonMethod, myMethod, partitionMethod, stablePartitionMethod, newPartitionMethod, newStablePartitionMethod)(1) .each!writeln; } /* Results (one of many runs, considered characteristic): * TickDuration(18129442) // originalMethod * TickDuration(28536187) // WilsonMethod * TickDuration(845396) // myMethod * TickDuration(29936970) // partitionMethod * TickDuration(33447345) // stablePartitionMethod * TickDuration(548226) // newPartitionMethod * TickDuration(597183) // newStablePartitionMethod */
Jan 28
prev sibling parent reply albert-j <djftgls ifdflv.com> writes:
On Friday, 27 January 2017 at 08:15:56 UTC, Dukc wrote:

 void main()
 {   import std.stdio, std.algorithm, std.range, std.array, 
 std.datetime;
     int[] a = [1, 2, 3, 4, 5, 6, 7, 4].cycle.take(2000).array;
     int[] b = [3, 4, 6].cycle.take(2000).array;

     void originalMethod()
     {   auto c = a.remove!(x => b.canFind(x));
         assert(c[0 .. 4] == [1, 2, 5, 7]);
     }

     void WilsonMethod()
     {   auto c = a.filter!(x => !b.canFind(x)).array;
         assert(c[0 .. 4] == [1, 2, 5, 7]);
     }

     void myMethod()
     {   auto sortedB = sort(b.dup);
         auto c = a
         .   filter!(i => !sortedB.contains(i))
         .   array
         ;
         assert(c[0 .. 4] == [1, 2, 5, 7]);
     }

     auto r = benchmark!(originalMethod, WilsonMethod, 
 myMethod)(1);
     foreach(result; r) result.writeln;
 }
How to make it work with std.container.array?
Jan 28
parent reply cym13 <cpicard openmailbox.org> writes:
On Saturday, 28 January 2017 at 10:46:29 UTC, albert-j wrote:
 On Friday, 27 January 2017 at 08:15:56 UTC, Dukc wrote:

 void main()
 {   import std.stdio, std.algorithm, std.range, std.array, 
 std.datetime;
     int[] a = [1, 2, 3, 4, 5, 6, 7, 4].cycle.take(2000).array;
     int[] b = [3, 4, 6].cycle.take(2000).array;

     void originalMethod()
     {   auto c = a.remove!(x => b.canFind(x));
         assert(c[0 .. 4] == [1, 2, 5, 7]);
     }

     void WilsonMethod()
     {   auto c = a.filter!(x => !b.canFind(x)).array;
         assert(c[0 .. 4] == [1, 2, 5, 7]);
     }

     void myMethod()
     {   auto sortedB = sort(b.dup);
         auto c = a
         .   filter!(i => !sortedB.contains(i))
         .   array
         ;
         assert(c[0 .. 4] == [1, 2, 5, 7]);
     }

     auto r = benchmark!(originalMethod, WilsonMethod, 
 myMethod)(1);
     foreach(result; r) result.writeln;
 }
How to make it work with std.container.array?
Here is an example: import std.container.array; alias ArrI = Array!int; auto removeAll(ArrI a, ArrI b) { import std.array; import std.range; import std.algorithm; auto sortedB = sort(b[]).uniq.array; auto c = a[].partition!(v => sortedB.assumeSorted.contains(v), SwapStrategy.stable); return ArrI(c); } void main() { import std.stdio; auto a = ArrI(1, 2, 3, 4, 5, 6, 7, 4); auto b = ArrI(3, 4, 6); a.removeAll(b)[].writeln; } Note especially how you slice an Array to access its data.
Jan 28
parent reply albert-j <djftgls ifdflv.com> writes:
On Saturday, 28 January 2017 at 11:54:58 UTC, cym13 wrote:
 
I am trying to wrap my head around lazy evaluation during filtering/mapping, but there's something I don't understand. I want to create an array, square some elements, remove some elements from original array and add the squared ones to the original array: import std.stdio, std.algorithm, std.array; int[] arr; foreach (i; 0..10) arr ~= i; writeln("Original array: ",arr); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] -- OK auto arrMap = arr.filter!(x => x > 5).map!(x => x^^2); writeln("arrMap: ", arrMap); // [36, 49, 64, 81] -- OK int[] toRemove = [1, 2, 9]; arr = arr.remove!(x => toRemove.canFind(x)).array; writeln("Original array after removal: ", arr); // [0, 3, 4, 5, 6, 7, 8] -- OK arr ~= arrMap.array; writeln("Original array after removal and concatenation: ", arr); // [0, 3, 4, 5, 6, 7, 8, 64, 49, 64, 81] -- what? The last result is not what I wanted. I would expect [0, 3, 4, 5, 6, 7, 8] and [36, 49, 64, 81] concatenated into [0, 3, 4, 5, 6, 7, 8, 36, 49, 64, 81], but something else is happening here. It looks like arr = arr.remove!.... is messing things up, but why?
Jan 29
next sibling parent reply Jordan Wilson <wilsonjord gmail.com> writes:
On Sunday, 29 January 2017 at 21:41:57 UTC, albert-j wrote:
 On Saturday, 28 January 2017 at 11:54:58 UTC, cym13 wrote:
 [...]
I am trying to wrap my head around lazy evaluation during filtering/mapping, but there's something I don't understand. I want to create an array, square some elements, remove some elements from original array and add the squared ones to the original array: [...]
You need to do something like this: auto arrMap = arr.filter!(x => x > 5).map!(x => x^^2).array; It's because arrMap is lazy evaluated.
Jan 29
parent reply Jordan Wilson <wilsonjord gmail.com> writes:
On Sunday, 29 January 2017 at 23:42:40 UTC, Jordan Wilson wrote:
 On Sunday, 29 January 2017 at 21:41:57 UTC, albert-j wrote:
 On Saturday, 28 January 2017 at 11:54:58 UTC, cym13 wrote:
 [...]
I am trying to wrap my head around lazy evaluation during filtering/mapping, but there's something I don't understand. I want to create an array, square some elements, remove some elements from original array and add the squared ones to the original array: [...]
You need to do something like this: auto arrMap = arr.filter!(x => x > 5).map!(x => x^^2).array; It's because arrMap is lazy evaluated.
Specifically: arr ~= arrMap.array; will cause arrMap to be evaluated again using whatever arr is. So instead of: auto arrMap = arr.filter!(x => x > 5).map!(x => x^^2); // mutate arr arr ~= arrMap.array; you would want: auto arrMap = arr.filter!(x => x > 5).map!(x => x^^2).array; // mutate arr arr ~= arrMap;
Jan 29
parent albert-j <djftgls ifdflv.com> writes:
On Sunday, 29 January 2017 at 23:48:40 UTC, Jordan Wilson wrote:

 You need to do something like this:
 auto arrMap = arr.filter!(x => x > 5).map!(x => x^^2).array;

 It's because arrMap is lazy evaluated.
So does it mean that I cannot assign FilterResult and MapResult to a variable and safely use it later, because underlying array may change meanwhile? Since I am dealing with large arrays, I thought I'd save some memory by not calling .array on MapResult.
Jan 29
prev sibling parent reply ag0aep6g <anonymous example.com> writes:
On Sunday, 29 January 2017 at 21:41:57 UTC, albert-j wrote:
     int[] arr;
     foreach (i; 0..10)
         arr ~= i;

     writeln("Original array: ",arr);
     // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] -- OK

     auto arrMap = arr.filter!(x => x > 5).map!(x => x^^2);
arrMap is a range. The filter and map operations only happen when the range is iterated. The array on which arrMap operates is the memory that is referred to by arr. If you change the values in that memory before evaluating arrMap, the result will be affected. However, `filter` also does something on creation: it skips to the first element that passes the predicate. I.e., it skips to 6 in your code. Or rather, it skips to the memory location where 6 is stored at the time. Since it happens on creation, that skipping will not be re-evaluated when you iterate over arrMap multiple times.
     writeln("arrMap: ", arrMap);
     // [36, 49, 64, 81] -- OK
Note that the values are computed while printing to the screen. They're not stored anywhere.
     int[] toRemove = [1, 2, 9];
     arr = arr.remove!(x => toRemove.canFind(x)).array;
Removing works by overwriting the array with only the wanted values and discarding the rest. The case at hand in detail: * Look at arr[0]. It's 0. That's not in [1, 2, 9], so it's copied to arr[0]. * Look at arr[1]. It's 1. That's in [1, 2, 9], so it's discarded. * Look at arr[2]. It's 2. That's in [1, 2, 9], so it's discarded. * Look at arr[3]. It's 3. That's not in [1, 2, 9], so it's copied to arr[1]. * arr[4] through arr[8] are not in [1, 2, 9] either, so they're copied to arr[2] through arr[6]. * arr[9] is in [1, 2, 9], so it's not copied. Note that arr[7] through arr[9] have not been overwritten. So you've got this in arr: [0, 3, 4, 5, 6, 7, 8, 7, 8, 9]. The last three values are then sliced off, because three values have been removed. Those values are still there in memory, though. The array's new length just stops before them.
     writeln("Original array after removal: ", arr);
     // [0, 3, 4, 5, 6, 7, 8] -- OK

     arr ~= arrMap.array;

     writeln("Original array after removal and concatenation: ", 
 arr);
     // [0, 3, 4, 5, 6, 7, 8, 64, 49, 64, 81] -- what?
Now, you've created arrMap before calling `remove`, so it still uses the old length for its underlying array. But it sees the new values, because `remove` has updated them in place. That means, it sees the values mentioned above: [0, 3, 4, 5, 6, 7, 8, 7, 8, 9]. Except, `filter` has already skipped the first six elements. So arrMap sees this: [8, 7, 8, 9]. Square those values and you get [64, 49, 64, 81], which is what you see. Generally, I'd say don't alter the underlying range/array between creating and evaluating a range, nor during evaluation. `filter` is most probably not the only range that misbehaves in that situation. Instead of mixing lazy ranges with the eager, in-place `remove`, you can use filter again: ---- void main() { import std.array: array; import std.algorithm: canFind, filter, map; import std.range: chain; import std.stdio: writeln; int[] arr; foreach (i; 0..10) arr ~= i; immutable int[] toRemove = [1, 2, 9]; arr = chain( arr.filter!(x => !toRemove.canFind(x)), arr.filter!(x => x > 5).map!(x => x^^2), ).array; writeln(arr); /* prints "[0, 3, 4, 5, 6, 7, 8, 36, 49, 64, 81]" */ } ----
Jan 29
next sibling parent albert-j <djftgls ifdflv.com> writes:
On Monday, 30 January 2017 at 00:17:51 UTC, ag0aep6g wrote:
 [...]
Great explanation, thank you!
Jan 29
prev sibling parent reply albert-j <djftgls ifdflv.com> writes:
On Monday, 30 January 2017 at 00:17:51 UTC, ag0aep6g wrote:

 Removing works by overwriting the array with only the wanted 
 values and discarding the rest.
But then why do I get this: import std.stdio, std.algorithm, std.array; int[] arr; foreach (i; 0..10) arr ~= i; // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] writeln("&arr[0]:", &arr[0]); // prints "7F56FAE93000" arr = arr.remove!(x => x > 5).array; writeln("&arr[0]:", &arr[0]); // prints "7F56FAE92020" writeln("arr:",arr); // prints: "[0, 1, 2, 3, 4, 5]" It looks like arr.remove allocates new memory and copies the data there.
Jan 30
parent reply cym13 <cpicard openmailbox.org> writes:
On Monday, 30 January 2017 at 08:50:14 UTC, albert-j wrote:
 On Monday, 30 January 2017 at 00:17:51 UTC, ag0aep6g wrote:

 Removing works by overwriting the array with only the wanted 
 values and discarding the rest.
But then why do I get this: import std.stdio, std.algorithm, std.array; int[] arr; foreach (i; 0..10) arr ~= i; // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] writeln("&arr[0]:", &arr[0]); // prints "7F56FAE93000" arr = arr.remove!(x => x > 5).array; writeln("&arr[0]:", &arr[0]); // prints "7F56FAE92020" writeln("arr:",arr); // prints: "[0, 1, 2, 3, 4, 5]" It looks like arr.remove allocates new memory and copies the data there.
No, remove works in-place, you are the one specifically asking for a reallocation here: instead of arr = arr.remove!(x => x>5).array; write arr.remove!(x => x>5); Complete example: import std.stdio; import std.format; import std.algorithm; void main(string[] args) { int [] arr = [0, 1, 2, 3, 4, 5]; auto before = arr.ptr; arr.remove!(x => x>5); auto after = arr.ptr; assert(before == after, "%s %s".format(before, after)); }
Jan 30
parent reply cym13 <cpicard openmailbox.org> writes:
On Monday, 30 January 2017 at 10:30:22 UTC, cym13 wrote:
 On Monday, 30 January 2017 at 08:50:14 UTC, albert-j wrote:
 On Monday, 30 January 2017 at 00:17:51 UTC, ag0aep6g wrote:

 Removing works by overwriting the array with only the wanted 
 values and discarding the rest.
But then why do I get this: import std.stdio, std.algorithm, std.array; int[] arr; foreach (i; 0..10) arr ~= i; // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] writeln("&arr[0]:", &arr[0]); // prints "7F56FAE93000" arr = arr.remove!(x => x > 5).array; writeln("&arr[0]:", &arr[0]); // prints "7F56FAE92020" writeln("arr:",arr); // prints: "[0, 1, 2, 3, 4, 5]" It looks like arr.remove allocates new memory and copies the data there.
No, remove works in-place, you are the one specifically asking for a reallocation here: instead of arr = arr.remove!(x => x>5).array; write arr.remove!(x => x>5); Complete example: import std.stdio; import std.format; import std.algorithm; void main(string[] args) { int [] arr = [0, 1, 2, 3, 4, 5]; auto before = arr.ptr; arr.remove!(x => x>5); auto after = arr.ptr; assert(before == after, "%s %s".format(before, after)); }
Meh. Forget that, bad memory. remove isn't working in-place. However slapping ".array" is still asking explicitely for reallocation, so just forget it. Here is a code that works: import std.conv; import std.stdio; import std.format; import std.algorithm; void main(string[] args) { int [] arr = [8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]; auto before = arr.ptr; arr = arr.remove!(x => x>5); auto after = arr.ptr; assert(arr == [0, 1, 2, 3, 4, 5], arr.to!string); assert(before == after, "%s %s".format(before, after)); }
Jan 30
parent reply albert-j <djftgls ifdflv.com> writes:
On Monday, 30 January 2017 at 10:45:03 UTC, cym13 wrote:

 Meh.

 Forget that, bad memory. remove isn't working in-place. However 
 slapping ".array" is still asking explicitely for reallocation, 
 so just forget it. Here is a code that works:

 import std.conv;
 import std.stdio;
 import std.format;
 import std.algorithm;

 void main(string[] args) {
     int [] arr = [8, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

     auto before = arr.ptr;
     arr = arr.remove!(x => x>5);
     auto after  = arr.ptr;

     assert(arr == [0, 1, 2, 3, 4, 5], arr.to!string);
     assert(before == after, "%s %s".format(before, after));
 }
OK, got it. Can you do removal without reallocation with std.container.array? Array!int arr; foreach (i; 0..10) arr ~= i;
Jan 30
parent reply albert-j <djftgls ifdflv.com> writes:
On Monday, 30 January 2017 at 12:31:33 UTC, albert-j wrote:

 OK, got it. Can you do removal without reallocation with 
 std.container.array?

     Array!int arr;
     foreach (i; 0..10) arr ~= i;
Sorry, sent too early. arr = arr[].remove!(x=> x > 5); //Doesn't work withouth calling .Array!int
Jan 30
parent ag0aep6g <anonymous example.com> writes:
On 01/30/2017 01:33 PM, albert-j wrote:
 On Monday, 30 January 2017 at 12:31:33 UTC, albert-j wrote:

 OK, got it. Can you do removal without reallocation with
 std.container.array?

     Array!int arr;
     foreach (i; 0..10) arr ~= i;
Sorry, sent too early. arr = arr[].remove!(x=> x > 5); //Doesn't work withouth calling .Array!int
Looks like it can't be done in that straight-forward manner. But you can do the `remove` and then update just `arr`'s length: ---- void main() { import std.container: Array; import std.algorithm: equal, remove; Array!int arr; foreach (i; 0..10) arr ~= i; const oldAddress = &arr[0]; arr.length = arr[].remove!(x=> x > 5).length; assert(equal(arr[], [0, 1, 2, 3, 4, 5])); /* holds */ assert(&arr[0] is oldAddress); /* holds */ } ---- Maybe std.container.Array can be improved somehow to simplify this. But I'm not sure about the details.
Jan 30
prev sibling parent Dukc <ajieskola gmail.com> writes:
On Thursday, 26 January 2017 at 23:10:02 UTC, albert-j wrote:
 Will it also work correctly and fast for arrays of custom 
 objects? How should opCmp() be defined if objects don't have a 
 meaningful ordering? The order of elements in the original 
 array does not matter.
Two options: either define opCmp for the custom objects, or define ordering for the sort algorithm (see std.algorithm in phobos documentation)
Jan 27
prev sibling parent Jordan Wilson <wilsonjord gmail.com> writes:
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]);
If you don't care about array a being mutated, then I think what you have is best (although I would suggest that if you don't care about a being mutated, just reassign the results back to a again). Otherwise, I think you need to allocate a new array, so the other answers using filter are good.
Jan 26