Red black trees

[Frits van Bommel]

Walter Bright wrote:
> 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.

Yeah, but it's also there in std::set<> (at least in GNU's 
implementation IIRC) wasting space.

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


Well, I suppose the user is likely to be some library class anyway:

struct Tuple(Key, Value) { ... }

class Map(Key, Value) : RedBlackTree!(Tuple(Key, Value)) {
	// Some extra methods
}



Will you at least consider something like this:

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