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

[Steven Schveighoffer]

On Fri, 15 Feb 2013 13:02:39 -0500, Dan <dbdavidson at yahoo.com> wrote:

> On Friday, 15 February 2013 at 17:42:30 UTC, Steven Schveighoffer wrote:
>> 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).
>
> Yes. But isn't opCmp still more work than just a<b?

It depends:

bool less(int a, int b)
{
   return a < b;
}

In assembly (pardon my ignorance of asm syntax):

ld a AX;
sub AX, b;
jneg L1; // jump if AX is less than zero
ld AX 0;
ret;
L1:
ld AX 1;
ret;

With opcmp:

int opCmp(int a, int b)
{
    return a - b;
}

Which simplifies the assembly significantly.  Note we don't have to  
shoehorn the result into a bool (which must be 0 or 1).

For other cases, such as a complex struct, less might be more efficient.   
And really, when it comes down to it, it all depends on how you use it.   
If most of the time you are using a < b or b < a, then less certainly can  
be more efficient (but not necessarily).  But if you want to do <=, ==, or  
>=, then opCmp can be more efficient.

-Steve