using a binary tree container

[Steven Schveighoffer]

On Sun, 13 Feb 2011 09:29:14 -0500, Lutger Blijdestijn  
<lutger.blijdestijn at gmail.com> 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