Could we reserve void[T] for builtin set of T ?

Jonathan M Davis via Digitalmars-d digitalmars-d at puremagic.com
Fri Apr 1 08:39:05 PDT 2016


On Friday, April 01, 2016 12:57:12 matovitch via Digitalmars-d wrote:
> On Friday, 1 April 2016 at 12:45:23 UTC, Jonathan M Davis wrote:
> > As it stands, if someone wants a set with Phobos, we have
> > RedBlackTree in std.container. So, we actually have sets
> > already. But all of that will presumably be getting an overhaul
> > with what Andrei has been up to.
>
> I don't know about the implementation of redblack tree in phobos,
> but I am willing to bet on a large performance drawback if you
> compare it against an optimized hash table (for example using
> robin-hood open addressing techniques). And I guess it is for
> sorted set (like a heap) with O(log N) insertion and deletion
> (although this may be just a theoretical worry)...Furthermore,
> the template constraint indicate the need of a less predicate
> which you may not need or want to define.

RedBlackTree is a red-black-tree, so it's a sorted set with whatever pros
and cons come with that. Having a hash set would have different pros and
cons. Ideally, we would have both, and I expect that we will eventually, but
at the moment, we just have RedBlackTree, but that's more than nothing, and
it's exactly what would be needed for many use cases even if a hash set were
available.

- Jonathan M Davis



More information about the Digitalmars-d mailing list