D中的简单集合实现？

Question

我在D的标准库中四处寻找一套实现，而我只找到了以下这些：

• BinaryHeap
• RedBlackTree

如果我能找到如何使用它们的话，这两种方法都会很好。我从RedBlackTree开始(因为我已经熟悉了它们的工作方式)，这就是我想出的：

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

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

我知道我可以在第一个过程中完成这个条件，但这只是一个示例，说明我需要从集合中添加和删除元素。这是可行的，但我会得到编译错误：

错误:模板std.container.RedBlackTree!(string).RedBlackTree.removeKey(U) if (isImplicitlyConvertible!(U，Elem))与任何函数模板声明不匹配 错误:模板std.container.RedBlackTree!(string).RedBlackTree.removeKey(U) if (isImplicitlyConvertible!(U，Elem))无法从参数类型(字符串)推断模板函数

我不需要一棵红黑树(没有副本的任何东西)，而且速度也不太重要。我可以这样做：

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++;
    }
}

标准库中有一套简单的东西吗？

Answer 1

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

您需要做的是给它一个字符串数组，或者直接实例化它，即removeKey([s])或removeKey!string(s)。

顺便说一句，std.container选择了根据其数据结构而不是它们的用途命名其容器类型的路线。所以，当你说你不需要一棵红黑树时，这是不完全正确的。你想要一套。你只是不在乎它是如何实现的。实现集合的两种典型方法包括使用红黑树或哈希表。因此，RedBlackTree给出了一种拥有集合的方法。只是它以其数据结构命名，而不是如何使用它，所以如果您在std.container中查找容器名称std.container，您将找不到它。

编辑：为此存在一个错误报告，并且已经提交了一个修复程序。因此，在dmd的未来版本中，应该可以将string传递给removeKey，而不必直接实例化它或在数组中传递string。

Answer 2

就我所知没有。

您最好的选择是只使用按键(bool[key] yourTable;)的哈希表，然后忽略这些值。

Answer 3

我至少知道一个：http://www.dsource.org/projects/dcollections