D 中的简单 Set 实现？

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 中添加和删除元素。这可行，但我收到编译错误：

错误：模板 std.container.RedBlackTree!(string).RedBlackTree.removeKey(U) if (isImplicitlyConvertible!(U,Elem)) 与任何函数模板声明都不匹配

错误：模板 std.container.RedBlackTree!(string).RedBlackTree.removeKey(U) if (isImplicitlyConvertible!(U,Elem)) 无法从参数类型推导出模板函数！()(string

I不需要红黑树（任何没有重复的东西），而且速度也不太重要，我可以做这样的事情：

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，这不会不起作用，因为你的树保存的是字符串，而不是字符。如果您处理的是整数或任何其他非数组类型的 RedBlackTree，则不会遇到此类问题。

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

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

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

Answer 2

据我所知没有。

最好的选择是仅使用键的哈希表 (bool[key] yourTable;) 并忽略这些值。

Answer 3

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

Answer 4

改进 Mehrdad 使用 bool[key] 的建议，您可以使用 byte[0][key] 避免一些空间浪费。 byte[0] 是一个大小为零的静态数组，因此它是一种不使用空间的类型。用法：

byte[0][string] mySet;

// Insert an element.
mySet["foo"] = (byte[0]).init;

// Lookup
assert("foo" in mySet);

// Remove
mySet.remove("foo");