How to use sets in D?

[Paul Backus]

On Tuesday, 8 February 2022 at 21:08:47 UTC, tastyminerals wrote:
> https://forum.dlang.org/post/mailman.1072.1581112984.31109.digitalmars-d-learn@puremagic.com
>
> On Friday, 7 February 2020 at 22:03:00 UTC, H. S. Teoh wrote:
>> On Fri, Feb 07, 2020 at 07:37:08PM +0000, mark 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.
[...]
>
> Can you please explain what does `bool[E]` mean? And how does 
> the code with aliasing void[0] and then using enum even work?

`bool[E]` means an [associative array][1] with keys of type `E` 
and values of type `bool`. Since a `bool` value takes up 1 byte 
in memory, using a `bool[E]` associative array to store a set of 
`E` values means that for every value in your set, you will have 
to allocate an extra 1 byte for the `bool` in addition to the 
bytes required for the `E` itself.

In most cases, 1 extra byte is not going to matter very much, so 
that's not a big deal. But if you really, really want to avoid 
allocating any extra bytes, you can use `void[0]` in place of 
`bool`, since a `void[0]` takes up 0 bytes in memory. (The `void` 
part has no special significance here--you could also use 
`int[0]` or `char[0]`, for example.)

The `alias` and the `enum` just make the code a little nicer to 
read by letting you write `Unit` instead of `void[0]` and `unit` 
instead of `void[0].init`. You could get rid of them and the code 
would work exactly the same way; it'd just be a little bit uglier:

     void[0][E] mySet;

     mySet[...] = void[0].init;
     mySet.remove(...);
     // etc.

The name "unit" comes from the concept of a [unit type][2] in 
theoretical computer science.

[1]: https://dlang.org/spec/hash-map.html
[2]: https://en.wikipedia.org/wiki/Unit_type