6

我在 D 的标准库中四处寻找 Set 实现，我只找到了这些：

  • 二叉堆
  • 红黑树

如果我能弄清楚如何使用它们，它们都可以正常工作。我从 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

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

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 的内容？

4

4 回答 4

7

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

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

顺便说一句，std.container 已经根据它们的数据结构而不是它们的用途来命名其容器类型。所以，当你说你不需要红黑树时，这并不完全正确。你想要一套。你只是不在乎它是如何实现的。实现集合的两种典型方法涉及使用红黑树或哈希表。所以，RedBlackTree给你一种方法来拥有一套。只是它以它的数据结构命名，而不是你可能如何使用它，所以如果你Set在 std.container 中寻找容器名称，你不会找到它。

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

于 2011-12-11T02:30:31.523 回答
4

从来没听说过。

最好的办法是只使用键 ( bool[key] yourTable;) 的哈希表并忽略值。

于 2011-12-11T01:54:58.713 回答
1

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

于 2011-12-11T02:02:57.930 回答
1

改进 Mehrdad 的 using 建议bool[key]，您可以通过 using 避免一些空间浪费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");
于 2011-12-11T17:37:44.970 回答