On Sun, 13 Feb 2011 09:29:14 -0500, Lutger Blijdestijn
<[email protected]> wrote:
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.
Yes, thank you. RedBlackTree is certainly not well-used, so it is bound
to have lots of usability issues.
-Steve
