Red black trees
Frits van Bommel
fvbommel at REMwOVExCAPSs.nl
Thu Oct 26 17:26:40 PDT 2006
Walter Bright wrote:
> Frits van Bommel wrote:
>> 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
>> }
>
> I use associative arrays, and I never use them like that <g>.
Well, that's not ideal code obviously, but it was shorter to type into
my newsreader :P. You get the idea, you can use RedBlackTrees with a
special value type to implement maps.
> They
> always have a key/value. Shouldn't rbtrees be simply an alternate
> container that has the same interface, but has different operating
> characteristics?
I myself never considered RedBlackTrees as associative arrays, just as a
data structure that can be used to implement them. But also to implement
sets (or bags (multisets) and multimaps if you allow duplicates).
>> 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?
>
> You could do that, though I'd call the result something else (like the
> Set type you mentioned).
But I think it should be possible to implement a Set using a
RedBlackTree without wasting space in the nodes.
And I think the code wouldn't be so much different, so a few 'static
if(is(Value == void))' would likely avoid quite a bit of code duplication.
More information about the Digitalmars-d
mailing list