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.

The signatures only had 'private' in there because I copy and pasted them out of something I was working on. (Because they work.)

On Sunday, 29 March 2015 at 09:17:17 UTC, w0rp wrote:
> 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.)

I also just realised that the ranges over the associative arrays are maybe @system because you can't guarantee that the associative array won't be modified while you're iterating over it.

I'll shut up now.

w0rp:

> Every now and then I want a set type,

I think you can implement good enough sets in Phobos, do you agree?

But you can't do the same with tuples. So I prefer sets in Phobos and tuples in the language.

Bye,
bearophile

On Sunday, 29 March 2015 at 14:23:10 UTC, bearophile wrote:
> w0rp:
>
>> Every now and then I want a set type,
>
> I think you can implement good enough sets in Phobos, do you agree?
>
> But you can't do the same with tuples. So I prefer sets in Phobos and tuples in the language.
>
> Bye,
> bearophile

+1 for tuples in language, it's one of the few things that would become far more useful as a core language feature.


Is std.container in need of more containers?

On Sunday, 29 March 2015 at 19:32:48 UTC, weaselcat wrote:
> Is std.container in need of more containers?

These

https://github.com/economicmodeling/containers

have Phobos-compatible license (Boost) and, with some work, I guess some of them could be merge into std.container, in your case *hashset.d is what you're looking for.

On Sunday, 29 March 2015 at 19:39:36 UTC, Nordlöw wrote:
> On Sunday, 29 March 2015 at 19:32:48 UTC, weaselcat wrote:
>> Is std.container in need of more containers?
>
> These
>
> https://github.com/economicmodeling/containers
>
> have Phobos-compatible license (Boost) and, with some work, I guess some of them could be merge into std.container, in your case *hashset.d is what you're looking for.

looks like they all rely on std.allocator which has been stagnating for a long time