从D中的数组中删除所有出现的给定值

Question

假设我有一个数组.我想删除数组中具有给定值的所有元素.有谁知道如何做到这一点？我试图删除的值可能会多次出现,并且数组不一定要排序.我宁愿原地过滤数组而不是创建一个新数组.例如,2从数组中删除值[1, 2, 3, 2, 4]应该产生结果[1, 3, 4].

这是我能想到的最好的事情:

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);

这似乎不必要地复杂和低效.有更简单的方法吗？我查看了标准库中的std.algorithm模块,希望找到一些有用的东西,但看起来像我想做的一切都有问题.以下是我尝试过的一些不起作用的例子:

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);

那么,如何在不知道它们出现的索引的情况下从数组中删除所有出现的值？

Answer 1

std.algorithm.filter非常接近你想要的东西:你的第二次尝试是好的.

您需要将其分配给新变量或在其上使用array()函数.

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

要么

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

第一个不创建新数组.它只是提供迭代过滤掉的给定事物.

第二个将为新数组分配内存以保存内容.您必须导入std.array模块才能工作.

Answer 2

在http://dlang.org/phobos/std_algorithm.html中查找函数remove .有两种策略 - 稳定和不稳定取决于您是否希望其余元素保持其相对位置.两种策略都在适当的位置运行并且具有O(n)复杂性.不稳定版本的写入次数较少.