Red black trees

[Walter Bright]

Frits van Bommel wrote:
> Walter Bright wrote:
>> clayasaurus wrote:
>>> I'd also like to add, that if you do give me the heads up that you 
>>> would like to see this to phobos, give me time to...
>>
>> I'd like to:
>>
>> 1) change RedBlackTree to take two type arguments: Key and Value 
>> types. The user needn't see the Node type at all.
> 
> I don't know, wouldn't adding an explicit value type waste space when 
> it's not needed?

It's almost always needed, it's there in the C++ std::map<>, and it 
eliminates the need for the user to have to know anything about the 
.Node class.

> You can always easily fake Key/Value by specializing T for a 'struct 
> Tuple(Key, Value)' with comparison operators forwarded to the key, can't 
> you?

Yes, but that's more work for the user.

> Though you could also allow Value to be void and specialize the node 
> type for that so it doesn't contain a Value in that case. Maybe even 
> make void the default type for Value?