On Thursday, October 11, 2012 18:45:36 Rizo Isrof wrote:
> Hi,
> 
> Why the `in` expression can only be applied to associative arrays and cannot be used with static or dynamic arrays as it is possible with, _e.g._, Python?
> 
> The following code is not legal:
> ----
> int[] a = [1,2,3,4,5];
> if (1 in a) { }
> ----
> Are there any technical explanation for this limitation?

Because that would mean than in was O(n), whereas it's generally assumed to be at least o(log n) (which is what you'd get in a balanced binary tree such as red-black tree). AA's do it in O(1), so they're okay, but dynamic arrays can't do better than O(n). And if you can't rely on a certain algorithmic complexity for an operation, then it becomes problematic for generic code. std.container specifically lists the complexity requirements for every function in there which is standard across containers, and any container which can't define such a function in the required complexity, doesn't define that function.

There has been some discussion of allowing in on dynamic or static arrays in some restricted cases where the array is known at compile time, but nothing has come of it as of yet. Regardless, there's pretty much no way that arrays in general will ever work with in, because it would be too inefficent.

You can use std.algorithm.find or std.algorithm.canFind. e.g.

int[] a = [1, 2, 3, 4, 5];

if(canFind(a, 1))
{
 ...
}

- Jonathan M Davis

Jonathan M Davis:

> Because that would mean than in was O(n), whereas it's generally assumed to be
> at least o(log n) (which is what you'd get in a balanced binary tree such as
> red-black tree). AA's do it in O(1), so they're okay, but dynamic arrays can't do better than O(n).

Time ago the built-in associative arrays of D used a search tree to solve hash collisions. But today they use linked lists for that purpose. This means to unlike the past today an adversary is able to create keys that turn AA search into O(n) searches. This is not theory.

Bye,
bearophile

On Fri, 12 Oct 2012 19:18:31 +0200
"Jonathan M Davis" <jmdavisProg@gmx.com> wrote:

> On Thursday, October 11, 2012 18:45:36 Rizo Isrof wrote:
> > Hi,
> > 
> > Why the `in` expression can only be applied to associative arrays and cannot be used with static or dynamic arrays as it is possible with, _e.g._, Python?
> > 
> > The following code is not legal:
> > ----
> > int[] a = [1,2,3,4,5];
> > if (1 in a) { }
> > ----
> > Are there any technical explanation for this limitation?
> 
> Because that would mean than in was O(n), whereas it's generally
> assumed to be at least o(log n) (which is what you'd get in a
> balanced binary tree such as red-black tree).

Another explanation is that 'in' searches the keys, ie indexes, not the values. So making it search the values on an array would arguably be inconsistent.

Fortunately, like Jonathan said, there's this which is pretty close:
if(a.canFind(1))