On Friday, 1 April 2016 at 15:39:05 UTC, Jonathan M Davis wrote:
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
Indeed, just wanted to point that out. (I guess that's why the
set was introduced before the unordered one in the c++ stl as
well). I feel like containers are an old topic. Last time I asked
I was told : wait for the allocators. What is the advancement on
this side ? Are there any plan at writing more containers for
phobos ? (I know that I am in the bad position of
complaining...but if there is no obstacle...I am ready to write a
draft of hashset in D, although surely not to phobos standards)
