Simple Set implementation in D?

Question

I was fishing around in D's standard library looking for a Set implementation, and I only found these:

• BinaryHeap
• RedBlackTree

These both would work fine, if I could only figure out how to use them. I started with the RedBlackTree (because I'm already familiar with how they work), and this is what I came up with:

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

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

I know I could have done the condition in the first foreach, but it's just an example showing that I need to add and remove elements from the Set. This would work, but I get compile errors:

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

I don't need a red-black tree (anything without duplicates), and speed isn't too important. I could do something like this:

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

Is there anything in the standard library for a simple Set?

Answer 1

RedBlackTree is Phobos' set implementation. The problem that you're running into with removeKey is the fact that it's variadic. It will take either an array of keys to remove or multiple keys (e.g. removeKey(arr) or removeKey(key1, key2, key3)). string is an array of immmutable chars, so it tries to instantiate removeKey with char instead of string, which doesn't work, because your tree holds strings, not chars. You wouldn't have this sort of problem if you were dealing with a RedBlackTree of ints or any other non-array type.

What you need to do is either give it an array of strings or to instantiate it directly i.e. removeKey([s]) or removeKey!string(s).

By the way, std.container has gone the route of naming its container types based on their data structure rather than what they're used for. So, when you say that you don't need a red-black tree, that's not quite right. You want a set. You just don't care how it's implemented. The two typical ways to implement sets involve using either a red-black tree or a hash table. So, RedBlackTree gives you one way to have a set. It's just that its named after its data structure, not how you might use it, so if you're looking for a container name Set in std.container, you're not going to find it.

EDIT: A bug report exists for this, and a fix has been submitted. So, in a future release of dmd, it should be possible to pass a string to removeKey without having to directly instantiate it or pass the string in inside an array.

Answer 2

Not that I know of.

Your best bet is to just use a hashtable by the keys (bool[key] yourTable;) and ignore the values.

Answer 3

I know of at least one: http://www.dsource.org/projects/dcollections

Answer 4

Improving on Mehrdad's suggestion of using bool[key], you can avoid some space wastage by using byte[0][key]. byte[0] is a static array of size zero, so it's a type that uses no space. Usage:

byte[0][string] mySet;

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

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

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