Creating an array of unique elements

[Dmitry Olshansky]

On 27.12.2010 10:22, Guilherme Vieira wrote:
> Hi, guys. — said the shy newcomer.
>
> I've started reading The D Programming Language just yesterday and I'm 
> making my first attempts to dig into D now. I must say I'm loving the 
> language beyond recognition. I never thought there was a language out 
> there that had everything I ever wanted in C++ (I even considered 
> developing my own language before knowing D!).
>
> Right now I'm wondering how's the best way to create a dynamic array 
> object which will only accept "unique" elements (i.e., elements != 
> from the existing elements in the array).
>
> I wanted a class that kept all the functionality of an array (e.g. 
> being the right range types so that they can be passed to 
> std.format.formatValue and trigger the right specialization) for 
> maximum integration with the standard library. I thought about writing 
> a class template privately containing an array and redirecting 
> everything but the assignment/insertion operations to it. All ways of 
> placing an object that was already there should throw an exception, 
> but everything else should work the same.
>
> Doing it this way is a lot of work for a simple thing, so some sort of 
> internal alert in me tell me I might just be "doing-it-wrong". I want 
> to know what your ideas are.
>
> I want some way to achieve this sort of thing:
>
>     import myproject.helpers.UniqueArray;
>
>     void main()
>     {
>         auto a0 = [1, 2, 3];
>
>         // I'm not yet sure how to go about the constructor, since:
>
>         auto a1 = UniqueArray!(int)(a0[1 .. $]); // error: should not
>     be able to internally hold reference to
>

I suspect the best would be to copy whatever got passed to constructor, 
since to provide such contracts UniqueArray needs to own data.  Also you 
could use fancy homogeneous variadic function for ctor:

this(T[] args...){
     _payload = args.dup;//assume member _payload holds internal array
}
Then
auto a = UniqueArray!(int)(1,2,3,4);//fills array with elements [1,2,3,4]
auto a = UniqueArray!(int)([5,6,7]); //works with the same signature

>                                                  // a raw array since
>     this could be used to break the "unique
>                                                  // elements" contract
>     promise of UniqueArray
>                                                  // copy of elements
>     can be considered, but I'd rather
>                                                  // have clients copy
>     the array themselves so that they
>                                                  // know it is happening
>
>         auto a2 = UniqueArray!(int)(a0[1 .. $].dup); // should be fine
>     if D had some sort of non-const
>                                                      // rvalue
>     reference support, but I think it does not;
>                                                      // am I wrong?
>
>         auto a3 = UniqueArray!(int)(a0[1 .. $].idup); // semantically
>     pleasing at first sight, but
>                                                       // suboptimal:
>     the constructor would have to copy
>                                                       // the passed
>     array again to get rid of immutability
>
>         auto a4 = bestOptionOutOf(a1, a2, a3); // (:
>
>         a4[1 .. $] = [3, 4, 5]; // ok: would first construct a
>     UniqueArray out of the rvalue (thus ensuring
>                                 // "uniqueness" of elements) and then
>     would work like a usual slice
>                                 // assignment
>
>         a4 ~= 5; // throws exception: 5 is already in the array!
>         a4 ~= 6; // ok: 6 is not there
>
>     writeln(a4); // ok, output: [2, 3, 4, 5, 6]
>                      // could just implement UniqueArray.toString()
>     for this to work, but making UniqueArray
>                      // properly model the ranges an array models
>     solves this problem and others at the same
>                      // time
>
>         auto a5 = a4.dup; // all properties of an array, such as dup
>     here, should hold and overall
>                           // the object should behave as one would
>     expect from an array
>
>         int[] a6 = a5; // error: obviously shouldn't work since a6
>     could then be used to break the
>                        // UniqueArray contract
>
>     }
>
>
> What do you think?
>
> -- 
> Atenciosamente / Sincerely,
> Guilherme ("n2liquid") Vieira


-- 
Dmitry Olshansky