A case for valueless AA's?

[Steven Schveighoffer]

On Tue, 29 Mar 2011 23:02:35 -0400, dsimcha <dsimcha at yahoo.com> wrote:

> On 3/29/2011 8:37 PM, Jonathan M Davis wrote:
>> We now have std.container.RedBlackTree, which can be used as a set, but  
>> it is
>> a tree rather than a hash table.
>>
>> - Jonathan M Davis
>
> This isn't a very good set.  It doesn't even support basic set  
> primitives like intersection, difference, union, etc.

std.container.RedBlackTree supports the standard methods, and not much  
else.  I am not the architect for std.container, so I did not want to add  
methods that might some day be superseded by further additions to the  
std.container regime.

dcollections does support these primitives, so the code already exists, I  
just am not sure of the interface Andrei wants.

> Furthermore, most programs will probably want a hash set.  A tree set is  
> only better when you don't have a good hash function or worst case  
> performance is more important than average case.

A tree-based set's advantage over hash-based is that it's ordered.  This  
means things like insertions and deletions do not affect ranges, whereas  
an insertion in a hash set can cause a rehash.

In addition to that, an ordered set provides excellent slicing ability  
(dcollections supports this).

So it depends on your needs.  Tree sets are definitely lower performing, I  
think Hashes win out pretty much there.

> I'm not saying there's anything wrong with RedBlackTree.  It's a  
> perfectly good data structure to implement a set on top of.  It's just  
> that it's not a "real" set type because it's not meant to be.

I found that the primitives in RedBlackTree suffice to make a set except  
for intersection, which cannot be done in a generic fashion with high  
performance.  This function exists in dcollections, and can easily be  
added to std.container.RedBlackTree.

-Steve