using a binary tree container

[Lutger Blijdestijn]

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.