Hello,

Is there an equivalent of 'in' for (non-associative) arrays? Cannot find any 'contains' function.
(Wouldn't it be nice to have in work for all arrays? What is the reason why it only works with AAs?)

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

spir.wikidot.com

On 12/02/2010 01:07 PM, spir wrote:
> Hello,
>
> Is there an equivalent of 'in' for (non-associative) arrays? Cannot find any 'contains' function.
> (Wouldn't it be nice to have in work for all arrays? What is the reason why it only works with AAs?)
>
> Denis
> -- -- -- -- -- -- --
> vit esse estrany ☣
>
> spir.wikidot.com
>

It doesn't exist for performance reasons, I think.

Use std.algorithm.canFind, which doesn't have the best name, but works as expected.

Pelle M.:

> It doesn't exist for performance reasons, I think.

It's not a matter of performance. Walter thinks that "in" on AAs searches on keys. And the "keys" of a dynamic array are its indices. And searching for indices in a dynamic array is not so useful. Therefore no "in" for dynamic/static arrays. I think this line of thought is not practical, and Python gets this better.

Bye,
bearophile

> It's not a matter of performance.

Well, it's also a matter of performance. The "in" done on arrays is a linear search and I think Andrei thinks that "in" must be sublinear instead.

Bye,
bearophile

bearophile wrote:
> Pelle M.:
>
>> It doesn't exist for performance reasons, I think.
>
> It's not a matter of performance. Walter thinks that "in" on
> AAs searches on keys. And the "keys" of a dynamic array are its
> indices. And searching for indices in a dynamic array is not so
> useful. Therefore no "in" for dynamic/static arrays. I think
> this line of thought is not practical, and Python gets this
> better.

I think Walter's is a good point. If 'in' searches among keys for AAs; for arrays, it would be implemented trivially as

    (index >= 0) && (index < array_length)

I think that expression allows for negative index values too. And yes, I had to check before posting as I can't be sure about the integer promotion rules. :)

If 'in' were to search among the values of arrays, then it wouldn't have the same meaning with AAs.

Ali

Ali Çehreli:

> If 'in' were to search among the values of arrays, then it wouldn't have the same meaning with AAs.

But it's useful and the different semantics is very easy to remember and use.

Bye,
bearophile

On Thu, 02 Dec 2010 08:54:43 -0800
Ali Çehreli <acehreli@yahoo.com> wrote:

> bearophile wrote:
>  > Pelle M.:
>  >
>  >> It doesn't exist for performance reasons, I think.
>  >
>  > It's not a matter of performance. Walter thinks that "in" on
>  > AAs searches on keys. And the "keys" of a dynamic array are its
>  > indices. And searching for indices in a dynamic array is not so
>  > useful. Therefore no "in" for dynamic/static arrays. I think
>  > this line of thought is not practical, and Python gets this
>  > better.
> 
> I think Walter's is a good point. If 'in' searches among keys for AAs; for arrays, it would be implemented trivially as
> 
>      (index >= 0) && (index < array_length)

That's not the point...

> I think that expression allows for negative index values too. And yes, I had to check before posting as I can't be sure about the integer promotion rules. :)
> 
> If 'in' were to search among the values of arrays, then it wouldn't have the same meaning with AAs.

Yes-no. In an ordered set (read: many uses of arrays), elements conceptually are their own keys. We must have a simple way to express membership test -- even if possibly costly for large arrays. Else, we need a builtin Set type to do the job. (I have one prototype in stock, if interesting for Phobos).


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

spir.wikidot.com

spir wrote:
> On Thu, 02 Dec 2010 08:54:43 -0800
> Ali Çehreli <acehreli@yahoo.com> wrote:
>
>> bearophile wrote:
>>  > Pelle M.:
>>  >
>>  >> It doesn't exist for performance reasons, I think.
>>  >
>>  > It's not a matter of performance. Walter thinks that "in" on
>>  > AAs searches on keys. And the "keys" of a dynamic array are its
>>  > indices. And searching for indices in a dynamic array is not so
>>  > useful. Therefore no "in" for dynamic/static arrays. I think
>>  > this line of thought is not practical, and Python gets this
>>  > better.
>>
>> I think Walter's is a good point. If 'in' searches among keys for AAs;
>> for arrays, it would be implemented trivially as
>>
>>      (index >= 0) && (index < array_length)
>
> That's not the point...
>
>> I think that expression allows for negative index values too. And yes, I
>> had to check before posting as I can't be sure about the integer
>> promotion rules. :)
>>
>> If 'in' were to search among the values of arrays, then it wouldn't have
>> the same meaning with AAs.
>

> Yes-no. In an ordered set (read: many uses of arrays),

I disagree with that. Arrays are for consecutive elements, usually unordered. The index is their position in the collection.

> elements
> conceptually are their own keys. We must have a simple way to
> express membership test -- even if possibly costly for large
> arrays. Else, we need a builtin Set type to do the job. (I have
> one prototype in stock, if interesting for Phobos).

Agreed but that's a completely different data structure. Sets cannot satisfy the O(1) operations of arrays.

I was responding related to D's arrays, which are not sets.

Ali