D中的简单集实现？

Question

我正在D标准库中寻找Set实现,我只发现了这些:

• 二叉堆
• 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(串).RedBlackTree.removeKey(U)如果(!isImplicitlyConvertible(U,ELEM))不匹配任何函数模板声明

错误:!模板std.container.RedBlackTree(串).RedBlackTree.removeKey(U)如果(!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++;
    }
}

标准库中是否有任何简单的Set？

Answer 1

RedBlackTree是Phobos的设定实施.你遇到的问题removeKey是它是可变的.它将需要一组键移除或多个键(例如removeKey(arr)或removeKey(key1, key2, key3)).string是immmutable字符数组,因此它试图实例removeKey与char替代string,这是不行的,因为你的树持有的字符串,而不是字符.如果您处理的RedBlackTree是int或任何其他非数组类型,则不会出现此类问题.

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

顺便说一下,std.container已经开始根据数据结构命名其容器类型而不是它们的用途.所以,当你说你不需要一棵红黑树时,那是不对的.你想要一套.你根本不在乎它是如何实现的.实现集合的两种典型方法涉及使用红黑树或哈希表.所以,RedBlackTree给你一种方法来设置一套.它只是以它的数据结构命名,而不是你如何使用它,所以如果你Set在std.container中寻找一个容器名,你就不会找到它.

编辑:存在此错误报告,并已提交修复程序.因此,在将来的dmd版本中,应该可以传递一个stringto removeKey而不必直接实例化它或传入string一个数组内部.