Creating an array of unique elements

[Guilherme Vieira]

On Mon, Dec 27, 2010 at 12:14 PM, Guilherme Vieira <n2.nitrogen at gmail.com>wrote:

> Ah, yeah. I think you're right. Set is exactly what I need, and the fact
> that it works with hashes is even better. A pity D still doesn't have it,
> since it looks very useful, but thanks for your response. I'll take a look
> at your implementation later.
>
> Is there any prevision for sets in core D or Phobos?
>
> --
>
> Atenciosamente / Sincerely,
> Guilherme ("n2liquid") Vieira
>
>
> On Mon, Dec 27, 2010 at 11:39 AM, spir <denis.spir at gmail.com> wrote:
>
>> 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
>>
>>
Eek..! sorry for top-posting.

-- 
Atenciosamente / Sincerely,
Guilherme ("n2liquid") Vieira
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d-learn/attachments/20101227/13468c0e/attachment.html>