Creating an array of unique elements

[spir]

On Mon, 27 Dec 2010 05:22:14 -0200
Guilherme Vieira <n2.nitrogen at gmail.com> wrote:

> 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).

(Take my words with precaution because I don not know D very well myself.)

Hello Guilherme. If I understand your purpose correctly, what you're trying to define is a set, not an array, in the common sense of the terms in programming. To ensure uniqueness, you'd need to check whether the element exits already, which can only be very slow using an array (O(n)): you need to traverse the array element per element. Sets instead are build using data structures that allow this check to be far faster, by looking up a given element in a more clever way.

There is no builtin Set type in D yet. The simplest way (and maybe the best) would be use associative arrays where keys would be actual elements and values just fake. (e in set) would tell you what you need. Depending on your requirements, trying to put an existing element would just put it again with no change, or should throw an error. In the latter case, you need to check it yourself or build a wrapper type (struct or class) around builtin associative arrays.

For instance:
    Existence[Element] set;
    Element[] elements = ['a','c','e'];
    Element[] values = ['a','b','c','d','e'];
    foreach (element ; elements)
        set[element] = EXISTS;
    // Note: 'in' actually return a pointer to element.
    foreach (value ; values)
        writeln(cast(bool)(value in set));

Note: I have a Set type in stock at https://bitbucket.org/denispir/denispir-d/src/b543fb352803/collections.d, but wonder whether it's really necessary given the above. But you can have a look to see how it's done (this would give you some hints about "language methods" called 'opSomething', see TDPL's index).


Denis
-- -- -- -- -- -- --
vit esse estrany ☣

spir.wikidot.com