About std.container.RedBlackTree

[bearophile]

Sorry for being so late with my answer. I am busy for some days.

Steven Schveighoffer:

>I don't really know what to do about fixing it.

It's not your fault. The forward reference errors I've found with RedBlackTree are so bad that in the end I've created a different algorithm that doesn't use a search tree.


>I probably should just avoid using auto,

Good.


>not being able to declare a red black tree as a global variable is a huge limitation.<

Also as instance variable for a struct.


> RedBlackTree must be initialized with a constructor.  Otherwise, your root  
> node is null.  I chose this path instead of checking for null on every  
> function.

This is OK, given your original design choice of using PIMPL.


> auto t = RedBlackTree!int.create();
> Please bugzillize this

OK.


> The function names must be consistent across containers, because the point  
> is that complexity and semantic requirements are attached to the function  
> name.  The function names were decided long ago by Andrei, and I don't  
> think insert is a bad name (I believe std::set and std::map in C++ STL  
> uses insert).

Python set uses "add", I prefer it for a set :-) But "insert" is acceptable.


>> redBlackTree(1, 2, 3)
> Yes, this should be done.  Please make a bugzilla report.  In fact, this  
> can extend to all std.container types.

OK. I will create a single bugzilla report for RedBlackTree.


> It helped me find bugs, but is  
> mostly no-longer needed unless I try some more optimizations.
> Please ignore the function.  I will make sure the comment is not ddoc'd.

Please hide it, but don't remove it from the module :-)


>> With:
>> struct RedBlackTree(T, alias less="a < b", bool allowDuplicates=false,  
>> bool withLength=false)
>
> The reason for this is to keep it a reference-type (pImpl style), but I  
> realize that I can easily fix this (I can just make the root node contain  
> a length field).  Please file a bugzilla to add length.

OK. The withLength template argument plus some static ifs allow to have zero overhead for people that don't need the O(1) length. I think withLength is better true on default, because removing the length is an optimization...


> I have done this in dcollections, and it helps immensely in node-based  
> containers.

I agree, I have seen similar things (D1 programs that become twice faster, etc), that's why I have suggested it.


> It is not clear to me how std.container will incorporate  
> these types of things, so Andrei and I decided to just defer it for now.

A template trait...


> What about changing the predicate?  I know it will likely violate the  
> requirements of a strict ordering, but it should probably work.

I am not sure it will work, but in the end I have used a very different solution.

Implementing an approximate (floating point) hash with a search tree is a common enough need, so you may add something like that approxInsert() as an free templated function in the std.collections module :-)


> Yes, the intention is that you can create a map type in this fashion.  If  
> you define a predicate, then it is up to you to ensure the predicate makes  
> sense for you.

OK. Then probably this important explanation (and example too, if you want) must be added to the RedBlackTree docs.


> Thank you for your detailed analysis!

You are welcome. And thank you for implementing this important collection.

Bye,
bearophile