std.container.RedBlackTree versus C++ std::set

[Steven Schveighoffer]

On Fri, 15 Feb 2013 12:11:55 -0500, monarch_dodra <monarchdodra at gmail.com>  
wrote:

> Also keep in mind that "a < b" is implemented as two calls to  
> "a.opCmp(b)", and "a.opCmp(b)" is itself usually implemented as two  
> calls to "something < something else" (!)

Huh?

a < b is implemented as a.opCmp(b) < 0, not two calls to a.opCmp(b).

HOWEVER, when you get to the point of executing a == b, it's implemented  
as !(a < b) && !(b < a), which could more efficiently be rewritten as  
a.opEquals(b) or a.opCmp(b) == 0.

In the case of red black tree however, the nature of traversal makes it so  
that you only have the redundant call once (when you have found the  
insertion spot, you already have called one half, you just have to call  
the other half).

For dcollections, I don't accept a < b, I accept the int-returning compare  
function (which I think is pass by ref, so shouldn't have this problem).   
The std.container.RedBlackTree is a port of the same code, but adapted to  
the more phobos-style functions.

-Steve