A case for valueless AA's?

[Jonathan M Davis]

On 2011-03-30 07:42, David Nadlinger wrote:
> On 3/30/11 3:59 PM, dsimcha wrote:
> > == Quote from David Nadlinger (see at klickverbot.at)'s article
> > 
> >> On 3/30/11 5:02 AM, dsimcha wrote:
> >>> […] Furthermore, most programs will probably want a hash set.
> >> 
> >> First of all, I agree that we really want to have a hash set in Phobos.
> >> I think that a first implementation wouldn't even need to support
> >> advanced operations like union, intersection, etc., but we should really
> >> have some kind of set in the standard library which doesn't look plain
> >> ugly (recently, I quickly needed some set implementation and abused AAs
> >> for it, but this isn't a serious option).
> > 
> > I was thinking an easy implementation of sets would be to abuse AAs using
> > the void[0][KeyType] trick under the hood.  We could even make a type
> > that wraps any AA conforming to the canonical compile time interface and
> > makes a set, using this trick.
> 
> Yes, that's what I was thinking about as well, and I really think just
> using AAs under the hood would be fine for an initial implementation.
> 
> I'm considering writing up a patch for std.container myself (at least I
> certainly will if my Thrift project was accepted, because I'd rather
> target a »canonical« HashSet implementation there), but as I am unsure
> about what design to use (final classes?), I refrained from it so far.

The containers in std.container are supposed to be final classes and implement 
any of the functions in the table which they can implement within the required 
Big O complexity. The exact set of functions may change over time as usage 
shows things that need to improve, but what's there is what is currently 
expected. Currently (in git), RedBlackTree is the only one which is a class, 
and glancing at it, I see that I forgot to make it final when I turned it into 
a class, so I'm going to have to go and fix that (but at least it's a class 
now). The others still need to be turned into classes.

- Jonathan M Davis