How to use sets in D?
H. S. Teoh
hsteoh at quickfur.ath.cx
Tue Feb 8 21:42:06 UTC 2022
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;
> > enum unit = Unit.init;
> > // Look, ma! A bona fide set!
> > Unit[E] mySet;
> > mySet[...] = unit;
> > mySet.remove(...);
> > ... // etc.
> > Or you can wrap void[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 and then using enum even
The alias is a workaround for a syntactic limitation in D, because you
cannot write `mySet[someKey] = void.init;` without a syntax error. So
we use the alias to give `void` a name that we can refer to in
assignment statements, so that we can assign its values to the AA.
As for `void` 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 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
But as I said, this is overkill for something so trivial. Using
`bool[E]` or an RBTree works just fine.
More information about the Digitalmars-d-learn