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

[Rob T]

On Thursday, 14 February 2013 at 19:31:36 UTC, Steven 
Schveighoffer wrote:
> On Thu, 14 Feb 2013 13:45:30 -0500, Rob T <alanb at ucora.com> 
> wrote:
>
>> When I look at the std.container source code, it seems that 
>> the payload element is passed by value multiple times 
>> unnecessarily, so to minimize copy construction you'll have to 
>> implement element as a class and implement a dup function for 
>> it.
>>
>> I expect performance will increase substantially even with the 
>> extra heap allocations.
>>
>> Alternatively, you can implement your own version of 
>> RedBlackTree with pass by ref optimizations for insertion of 
>> struct elements.
>
> If it was pass by ref, then rbt.insert(5) would not work.  And 
> in fact, I wouldn't want things passed by ref if the element is 
> int.  I have to admit, I did not consider expensive postblits 
> when I designed it.  Almost all my testing is with integer 
> types.

You can make it work by implementing two insert functions, one 
with pass by ref and one with pass by value. The pass by value 
implementation simply calls the pass by ref version, and 
everything from there is pass by ref where it makes sense as an 
optimization.

I understand the implementation difficulties, because we have 
multiple situations to consider and optimize for, such as simple 
POD which can often pass by value efficiently, but then we have 
complex structs that do not pass by value efficiently and should 
be passed by ref instead, but there's no way to detect this 
easily (I suppose you could try looking at the size and adjust 
the pass-by method somehow, but ...), and finally if you accept a 
class then you have different needs because a class is a pointer 
not a POD value, again I suppose you can detect if a class is 
being passed and adjust the implementation but that introduces 
more complexity ...

In some ways this is where C++ got it right from a consistency 
POV, where a class is no different from a struct, so whatever 
works for a class also works for a struct. In D, structs and 
classes operate in fundamentally different ways making 
implementing generics more difficult to do.

> Unfortunately, D is in this state where taking a ref parameter 
> means strictly lvalue.  So passing rvalues will not work.  D 
> does not have the notion that C++ has where const type& can 
> accept both rvalue and lvalue.  We desperately need something 
> similar.
>
> -Steve

Yes, I agree.

--rt