set - D中的简单集实现？

Question

我在D的标准库中钓鱼，以寻找Set实现，但我仅发现以下内容:

BinaryHeap

RedBlackTree

如果我只能弄清楚如何使用它们，这两种方法都可以正常工作。我从RedBlackTree开始(因为我已经熟悉它们的工作原理)，这就是我想到的:

auto rbt = redBlackTree!string();
foreach(s; setOfStrings) {
    rbt.insert(s);
}

foreach(s; rbt) {
    if (s[0 .. 3] == "sth") {
        rbt.removeKey(s);
    }
}

我知道我可以在第一个foreach中完成条件，但这只是一个示例，表明我需要从Set中添加和删除元素。这可以工作，但是会出现编译错误:

Error: template std.container.RedBlackTree!(string).RedBlackTree.removeKey(U) if (isImplicitlyConvertible!(U,Elem)) does not match any function template declaration

Error: template std.container.RedBlackTree!(string).RedBlackTree.removeKey(U) if (isImplicitlyConvertible!(U,Elem)) cannot deduce template function from argument types !()(string

我不需要一棵红黑树(任何没有重复的东西)，速度也不是很重要。我可以做这样的事情:

string[] arr;
foreach(s; setOfStrings) {
    // check for duplicate code here...

    arr ~= s;
}
for(int i = 0; i < arr.length; i++) {
    if (s[0 .. 3] == "sth") {
        arr = arr[0 .. i] ~ arr[i + 1 .. $];
        i++;
    }
}

标准库中是否有用于简单Set的东西？

Answer 1

RedBlackTree是Phobos的set实现。您使用removeKey遇到的问题是可变参数。要删除一个键数组或多个键(例如removeKey(arr)或removeKey(key1, key2, key3))。 string是一个不可改变的字符数组，因此它尝试使用removeKey而不是char实例化string，这是行不通的，因为您的树包含字符串，而不是chars。如果您处理的是int或其他任何非数组类型的RedBlackTree，则不会出现此类问题。

您需要为它提供一个字符串数组或直接实例化它，即removeKey([s])或removeKey!string(s)。

顺便说一句，std.container已经根据其数据结构而不是其用途来命名其容器类型。因此，当您说不需要一棵红黑树时，那是不正确的。你要一套。您只是不关心它的实现方式。实现集合的两种典型方法涉及使用红黑树或哈希表。因此，RedBlackTree为您提供了一种设置方法。它只是以其数据结构命名，而不是如何使用它，因此，如果要在std.container中查找容器名称Set，就不会找到它。

编辑:为此存在一个bug report，并且已提交修复程序。因此，在将来的dmd版本中，应该可以将string传递给removeKey，而不必直接实例化它或将string传递到数组内部。