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

[Jonathan M Davis]

On Thursday, February 14, 2013 14:31:36 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.

And Walter and Andrei both seem to think that having expensive postlbits is a 
design mistake. The range stuff sort of tries to support it with the move* 
primitives, but Andrei's been wanting to argue for just assuming that 
postblits are cheap. And Walter was actually arguing at one point for making 
it illegal (probably by getting rid of postblit all together - I don't 
remember the details). Plenty of the rest of us don't agree, but to some 
extent, it is true that having an expensive postblit is asking for it. On a 
related note, we still need a solution for dealing with const postblits 
(probably be introducing copy constructors - IIRC Andrei was considering 
phasing out postblits in favor of copy constructors, which would be 
unnecessary, but we do need a way to deal with deep copying const structs 
which hold reference types which need to be deep copied.

> 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.

auto ref is the current solution for templated functions, but we do need a 
more general solution. DIP25 got created in part due to discussions on that, 
but it probably needs to be fully sorted out before we can fully sort out the 
const& solution.

- Jonathan M Davis