How to use sets in D?

[H. S. Teoh]

On Tue, Feb 08, 2022 at 09:08:47PM +0000, tastyminerals via Digitalmars-d-learn wrote:
[...]
> > bool[E] works just fine.
> > 
> > The bool does take up 1 byte, though, so if you're *really* want to
> > optimize that away, you could do this:
> > 
> > 	alias Unit = void[0];
> > 	enum unit = Unit.init;
> > 
> > 	// Look, ma! A bona fide set!
> > 	Unit[E] mySet;
> > 
> > 	mySet[...] = unit;
> > 	mySet.remove(...);
> > 	... // etc.
> > 
> > Or you can wrap void[0][E] in a nice user-defined type that gives
> > nice set-like syntax.  But IMO, this is all overkill, and adds
> > needless complexity. Just use bool[E] or std.container.rbtree. :-D
[...]
> Can you please explain what does `bool[E]` mean?

E is whatever key type you want to use. String, or integer ID, or
whatever you want to put in your set.


> And how does the code with aliasing void[0] and then using enum even
> work?

The alias is a workaround for a syntactic limitation in D, because you
cannot write `mySet[someKey] = void[0].init;` without a syntax error. So
we use the alias to give `void[0]` a name that we can refer to in
assignment statements, so that we can assign its values to the AA.

As for `void[0]` itself, it's just a zero-element static array of an
indeterminate type. The whole point is to create something that occupies
0 bytes. The actual type doesn't actually matter; you could have used
int[0] and it'd work too.  (You can't use an empty struct because empty
structs have size 1.)  By using a zero-sized value type for the AA, we
effectively turn it into a set: it only stores keys.  Well, technically
it stores values of zero size too, but since it's zero-sized, it's as if
the value isn't there, and it incurs zero memory overhead. (Whereas an
empty struct would likely occupy an entire machine word, rounded up from
size 1.)

But as I said, this is overkill for something so trivial. Using
`bool[E]` or an RBTree works just fine.


T

-- 
Javascript is what you use to allow third party programs you don't know anything about and doing you know not what to run on your computer. -- Charles Hixson