Dominic Jones wrote:
> Hello,
>
> I have a list of strings and I want to determine whether or not a
> particular string in the is in that list. Assuming I should store the list
> of strings in a binary tree to facilitate fast searching, I had a look at
> the std.container documentation and found RedBlackTree, but the
> documentation for it has no examples. May someone offer an example of how
> to use it?
>
> Thank you,
> Dominic Jones
I tried it out and it's simple to use but I stumbled upon some issues. (See
below) As others have commented, regular AA's will work fine for this
purpose too. Probably the best reason why you would choose a RedBlackTree
over AA is when you also need them sorted, this you get for free. A tree is
also likely to consume less memory, which may or may not matter.
Example:
import std.stdio;
import std.container;
void main()
{
auto stuff = ["foo", "bar"];
/* using make instead of the constructor ensures the code will work
when RedBlackTree will become a class: */
auto set = make!(RedBlackTree!string)(stuff);
/* iterates in order: */
foreach( value; set )
writeln(value);
set.stableInsert("baz");
/* the 'in' operator returns bool, not a pointer to the element like
builtin aa's do: */
assert( "baz" in set );
}
Now for the issues, this doesn't work but it should:
auto set = make!(RedBlackTree!string)("foo", "bar");
Error: template std.container.RedBlackTree!(string).RedBlackTree.__ctor(U)
if (isImplicitlyConvertible!(U,Elem)) does not match any function template
declaration
Error: template std.container.RedBlackTree!(string).RedBlackTree.__ctor(U)
if (isImplicitlyConvertible!(U,Elem)) cannot deduce template function from
argument types !()(string,string)
...
I couldn't see any function to remove a single element from the tree and
std.algorithm.remove doesn't work. Removing a range also doesn't work for
strings:
set.remove(stuff);
Error: function std.container.RedBlackTree!(string).RedBlackTree.remove
(Range r) is not callable using argument types (string[])
Error: cannot implicitly convert expression (stuff) of type string[] to
Range
I'll file these issues soon, when I have the time.
