On Tue, 29 Mar 2011 23:02:35 -0400, dsimcha <dsim...@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
