[Feature Request] Adding to D lang "set" built-in

H. S. Teoh hsteoh at quickfur.ath.cx
Sun May 6 15:11:07 PDT 2012


On Sat, May 05, 2012 at 07:14:27PM +0200, bioinfornatics wrote:
> Dear, i hope i will got some answer from druntime/phobos dev .
> A set is an array of unique element:
> >>> set( 1, 5, 7, 1, 7)
> give this array => [1, 5, 7]
> 
> Currently in D the hack it is to use an associative array with any
> value.
> byte[size_t] a = [ 1:0, 5:0, 7:0, 1:0, 7:0 ];
> 
> then it is easy to have a set in D just add a syntax or a built-in where
> use associative array without using value.
> 
> I hope really this little feature and seem really easy to add
[...]

It's not too hard to implement something like this yourself. One of the
first projects I did when I started learning D was to implement an
integer set (basically a bit array). It supports full set operations,
like union, intersection, difference, optimized filling with first n
numbers, foreach, etc.. Some of the operations use bit-twiddling tricks
to maximize performance.

The only flaw is that it's essentially just a bit array, so it only
works well for sets whose elements are relatively small numbers. If you
want sparse sets, you may be better off adapting D's AA implementation
to have an AA that consists of just keys. Basically, you still have the
hash table and buckets, just without the value field in each slot. (I
wonder if it's possible for the new AA implementation to support this by
specifying void as the value type.)


T

-- 
Klein bottle for rent ... inquire within. -- Stephen Mulraney


More information about the Digitalmars-d mailing list