www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - 'in' for plain arrays?

reply spir <denis.spir gmail.com> writes:
Hello,

Is there an equivalent of 'in' for (non-associative) arrays? Cannot find an=
y '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 =E2=98=A3

spir.wikidot.com
Dec 02 2010
parent reply =?UTF-8?B?UGVsbGUgTcOlbnNzb24=?= <pelle.mansson gmail.com> writes:
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.
Dec 02 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
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
Dec 02 2010
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
 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
Dec 02 2010
prev sibling parent reply =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
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
Dec 02 2010
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
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
Dec 02 2010
prev sibling parent reply spir <denis.spir gmail.com> writes:
On Thu, 02 Dec 2010 08:54:43 -0800
Ali =C3=87ehreli <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.
=20
 I think Walter's is a good point. If 'in' searches among keys for AAs;=20
 for arrays, it would be implemented trivially as
=20
      (index >=3D 0) && (index < array_length)


That's not the point...


 I think that expression allows for negative index values too. And yes, I=


=20

 had to check before posting as I can't be sure about the integer=20
 promotion rules. :)
=20
 If 'in' were to search among the values of arrays, then it wouldn't have=


=20

 the same meaning with AAs.


Yes-no. In an ordered set (read: many uses of arrays), elements conceptuall=
y 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 ty=
pe to do the job. (I have one prototype in stock, if interesting for Phobos=
).


Denis
-- -- -- -- -- -- --
vit esse estrany =E2=98=A3

spir.wikidot.com
Dec 03 2010
parent =?UTF-8?B?QWxpIMOHZWhyZWxp?= <acehreli yahoo.com> writes:
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
Dec 03 2010