All geek questions in one place

Easy installation in D?

I fished in the standard D library, which was looking for an implementation of Set, and I just found:

  • binary heap
  • Redblacktree

Both of them will work fine if I could only figure out how to use them. I started with RedBlackTree (because I'm already familiar with how they work), and here 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 that I could fulfill the condition in the first foreach, but this is just an example showing that I need to add and remove elements from Set. This will work, but I get compilation errors:

Error: std.container.RedBlackTree! Template (string) .RedBlackTree.removeKey (U) if (isImplicitlyConvertible! (U, Elem)) does not match the function template declaration

Error: std.container.RedBlackTree! Template (string) .RedBlackTree.removeKey (U) if (isImplicitlyConvertible! (U, Elem)) cannot derive a template function from argument types! () (string

I do not need a red-black tree (all without duplicates), and speed is not 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 simple typing?

+6
source share
4 answers

RedBlackTree - Phobos suite implementation. The problem you are facing with removeKey is that it is a variable. This will take either an array of keys to delete, or several keys (for example, removeKey(arr) or removeKey(key1, key2, key3) ). string is an array of immmutable chars, so it tries to create an removeKey instance with char instead of string , which does not work because your tree contains strings, not characters. You would not have such a problem if you were dealing with RedBlackTree for int or any other type without an array.

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

By the way, std.container went the way of naming its container types based on their data structure, and not what they are used for. So, when you say that you do not need a red-black tree, this is not entirely correct. You want a set. You just don't care how it is implemented. Two typical ways to implement sets include using a red-black tree or a hash table. So, RedBlackTree gives you one way to have a kit. It's just that it was named after the data structure, and not how you could use it, so if you are looking for the name of the Set container in std.container, you will not find it.

EDIT : An error report exists for this, and a fix has been submitted. Thus, in a future version of dmd, it should be possible to pass string to removeKey without the need to directly instantiate or pass string inside the array.

+7
source

Not that I knew.

It is best to use a hash table with the keys ( bool[key] yourTable; ) and ignore the values.

+4
source

By improving Mehrdad’s suggestion for using bool[key] , you can avoid wasting space with byte[0][key] . byte[0] is a static array with zero size, so it does not use a space. Using:

 byte[0][string] mySet; // Insert an element. mySet["foo"] = (byte[0]).init; // Lookup assert("foo" in mySet); // Remove mySet.remove("foo");
+1
source

Source: https://habr.com/ru/post/903540/

More articles:


All Articles