Removing all occurrences of a given value from an array in D

Question

Suppose that I have an array. I want to remove all the elements within the array that have a given value. Does anyone know how to do this? The value I am trying to remove may occur more than once and the array is not necessarily sorted. I would prefer to filter the array in-place instead of creating a new array. For example, removing the value 2 from the array [1, 2, 3, 2, 4] should produce the result [1, 3, 4].

This is the best thing I could come up with:

T[] without(T)(T[] stuff, T thingToExclude) {
    auto length = stuff.length;
    T[] result;
    foreach (thing; stuff) {
        if (thing != thingToExclude) {
            result ~= thing;
        }
    }
    return result;
}

stuff = stuff.without(thingToExclude);
writeln(stuff);

This seems unnecessarily complex and inefficient. Is there a simpler way? I looked at the std.algorithm module in the standard library hoping to find something helpful but everything that looked like it would do what I wanted was problematic. Here are some examples of things I tried that didn't work:

import std.stdio, std.algorithm, std.conv;

auto stuff = [1, 2, 3, 2, 4];
auto thingToExclude = 2;

/*  Works fine with a hard-coded constant but compiler throws an error when
    given a value unknowable by the compiler:
    variable thingToExclude cannot be read at compile time */
stuff = filter!("a != " ~ to!string(thingToExclude))(stuff);
writeln(stuff);

/*  Works fine if I pass the result directly to writeln but compiler throws
    an error if I try assigning it to a variable such as stuff:
    cannot implicitly convert expression (filter(stuff)) of type FilterResult!(__lambda2,int[]) to int[] */
stuff = filter!((a) { return a != thingToExclude; })(stuff);
writeln(stuff);

/*  Mysterious error from compiler:
    template to(A...) if (!isRawStaticArray!(A)) cannot be sliced with [] */
stuff = to!int[](filter!((a) { return a != thingToExclude; })(stuff));
writeln(stuff);

So, how can I remove all occurrences of a value from an array without knowing the indexes where they appear?

Answer 1

std.algorithm.filter is pretty close to what you want: your second try is good.

You'll want to either assign it to a new variable or use the array() function on it.

auto stuffWithoutThing = filter!((a) { return a != thingToExclude; })(stuff);
// use stuffWithoutThing

or

stuff = array(filter!((a) { return a != thingToExclude; })(stuff));

The first one does NOT create a new array. It just provides iteration over the thing with the given thing filtered out.

The second one will allocate memory for a new array to hold the content. You must import the std.array module for it to work.

Answer 2

Look up function remove in http://dlang.org/phobos/std_algorithm.html. There are two strategies - stable and unstable depending on whether you want the remaining elements to keep their relative positions. Both strategies operate in place and have O(n) complexity. The unstable version does fewer writes.