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

[Ivan Kazmenko]

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

Thank you all for assistance, I've finally pinned it down!  It's 
the default magic "a < b" that devours the most copies of my 
precious structs!  Once I change the declaration:

-----
alias RedBlackTree !(element) container;
-----

to

-----
bool lessfun (ref element a, ref element b)
{
	return a < b;
}

alias RedBlackTree !(element, lessfun) container;
-----

... I get only exactly 3 * LIMIT postblit constructor calls, 
which is 300,000 instead of 11,389,556.  While I still want to 
find where the excess 200,000 calls originate from, this is 
definitely asymptotically better than before: O (n) versus O (n 
log n) calls.  And it is now less of a bottleneck in my original 
program.

This raises the question to the default behavior of 
std.functional.binaryFun.  Sure, for integers, class references 
and small types, the current way is the best.  On the other hand, 
for large structs and maybe some other complex objects that obey 
value semantics, it seems it would be beneficial to, given a 
string like "a < b", produce a function taking arguments by 
reference and not by value.  Maybe there is some simple criterion 
(size of type greater than size_t - seems bad? type is a struct - 
better?) which can be used with static if to generate "(ref a, 
ref b)" instead of "(a, b)" version by default.  Of course, all 
that could only work if there is a more detailed hierarchy of 
binary functions, at least a binaryFunConst taking const 
arguments.

-----
Ivan Kazmenko.