Adding sets to the language.

w0rp via Digitalmars-d digitalmars-d at puremagic.com
Sun Mar 29 02:17:16 PDT 2015


Every now and then I want a set type, but I have to either use my 
own library for it, or use a commonly known associative array 
trick. I really think (unordered hash) sets should be part of the 
standard library. While I was working on something else, I 
thought of one way of adding them to the standard library, maybe 
in the sort of core place associative arrays live in.

Define the following alongside the associative arrays.

// An alias for spelling it out.
// I shall count down the seconds to someone saying,
// "This should be named HashSet instead."
private alias Set(V) = void[0][V];

// Allow for set.contains(value) returning a boolean.
// The parameter types here may differ.
@nogc @safe pure nothrow
private bool contains(T, U)(const(void[0][T]) set, auto ref 
const(U) value)
if(is(const(U) : const(T))) {
     return (value in set) !is null;
}

// Allow for adding values with set.add(value)
// I think I got the types right here.
@safe pure nothrow
private void add(T, U)(ref void[0][T] set, auto ref U value)
if(is(U : T)) {
     set[value] = (void[0]).init;
}

// Allow for using sets as output ranges.
alias put = add;

Now people who are writing void[0][T] themselves for sets, or who 
have their own aliases, can use the two new functions to make 
their code look a little nicer.

Now I'll get into a list of perhaps related desires and gripes.

1. When the value type is void[0], perhaps associative arrays 
could do something special, if they don't already.
2. I would like the compiler to output Set!T in error messages 
instead of void[0][T].
3. I'm using 2.066 still, and some things like byKey aren't @safe 
and so on. These things need to have attributes set. (As always, 
opApply probably lacks one of @nogc, @safe, pure, nothrow because 
of the delegate types.)
4. I couldn't get the sets to be recognised as an output range no 
matter what I hammered in for the 'put' function. I don't know 
what's going on there.
5. When I used my alias Set!T as the parameter types for the 
functions above instead of void[0][T], type deduction failed. 
This could be a problem.
6. The key types for associative arrays really ought to be 
required to be immutable with immutable(T)[] being allowed too. 
You can allow mutable lookups with a copy and so on, but that 
doesn't work, because changing the hash for the object will make 
the second lookup fail.


More information about the Digitalmars-d mailing list