D idom for removing array elements

ag0aep6g via Digitalmars-d-learn digitalmars-d-learn at puremagic.com
Sun Jan 29 16:17:51 PST 2017


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]" */
}
----


More information about the Digitalmars-d-learn mailing list