Thread overview |
---|
March 29, 2015 Adding sets to the language. | ||||
---|---|---|---|---|
| ||||
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. |
March 29, 2015 Re: Adding sets to the language. | ||||
---|---|---|---|---|
| ||||
Posted in reply to w0rp | The signatures only had 'private' in there because I copy and pasted them out of something I was working on. (Because they work.) |
March 29, 2015 Re: Adding sets to the language. | ||||
---|---|---|---|---|
| ||||
Posted in reply to w0rp | 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.
|
March 29, 2015 Re: Adding sets to the language. | ||||
---|---|---|---|---|
| ||||
Posted in reply to w0rp | 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
|
March 29, 2015 Re: Adding sets to the language. | ||||
---|---|---|---|---|
| ||||
Posted in reply to 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?
|
March 29, 2015 Re: Adding sets to the language. | ||||
---|---|---|---|---|
| ||||
Posted in reply to weaselcat | 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. |
March 29, 2015 Re: Adding sets to the language. | ||||
---|---|---|---|---|
| ||||
Posted in reply to Nordlöw | 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
|
Copyright © 1999-2021 by the D Language Foundation