Hi:
   In Dlang where is strange design. The in expression can only use to associative array, why array can not use in expression.

On Thursday, 24 October 2019 at 12:58:11 UTC, lili wrote:
> Hi:
>    In Dlang where is strange design. The in expression can only use to associative array, why array can not use in expression.

Checking for the presence of an item in an array requires a linear search. You can do it with std.algorithm.searching.canFind:

https://dlang.org/phobos/std_algorithm_searching.html#.canFind

On Thursday, October 24, 2019 7:04:56 AM MDT Paul Backus via Digitalmars-d- learn wrote:
> On Thursday, 24 October 2019 at 12:58:11 UTC, lili wrote:
> > Hi:
> >    In Dlang where is strange design. The in expression can only
> >
> > use to associative array, why array can not use in expression.
>
> Checking for the presence of an item in an array requires a linear search. You can do it with std.algorithm.searching.canFind:
>
> https://dlang.org/phobos/std_algorithm_searching.html#.canFind

In particular, the reason that linear search is considered unacceptable for
in is so that generic code can rely on its performance. The idea is that
types shouldn't implement the in operator unless they can do so with
O(log n) or better (O(log n) being what it costs to get to an item in a
balanced binary tree like a red-black tree). That way, when you calculate
the complexity of any algorithm using in, you can assume that it's O(log n)
at worst. Having it be O(n) instead (like it would be for an array) would
drastically increase the complexity of the algorithm and make it take much
longer when processing a large number of items. And the standard library
provides functions like canFind or find for finding elements in an array, so
having in work with arrays wouldn't add any functionality. It would
basically just change the syntax you'd use for finding an element in an
array.

- Jonathan M Davis

On Thursday, 24 October 2019 at 22:40:31 UTC, Jonathan M Davis wrote:
> On Thursday, October 24, 2019 7:04:56 AM MDT Paul Backus via Digitalmars-d- learn wrote:
>> On Thursday, 24 October 2019 at 12:58:11 UTC, lili wrote:
>> > Hi:
>> >    In Dlang where is strange design. The in expression can only
>> >
>> > use to associative array, why array can not use in expression.
>>
>> Checking for the presence of an item in an array requires a linear search. You can do it with std.algorithm.searching.canFind:
>>
>> https://dlang.org/phobos/std_algorithm_searching.html#.canFind
>
> In particular, the reason that linear search is considered unacceptable for
> in is so that generic code can rely on its performance. The idea is that
> types shouldn't implement the in operator unless they can do so with
> O(log n) or better (O(log n) being what it costs to get to an item in a
> balanced binary tree like a red-black tree). That way, when you calculate
> the complexity of any algorithm using in, you can assume that it's O(log n)
> at worst. Having it be O(n) instead (like it would be for an array) would
> drastically increase the complexity of the algorithm and make it take much
> longer when processing a large number of items. And the standard library
> provides functions like canFind or find for finding elements in an array, so
> having in work with arrays wouldn't add any functionality. It would
> basically just change the syntax you'd use for finding an element in an
> array.
>
> - Jonathan M Davis

 This reason somewhat farfetched， Think about that if this reason is right， the operator overload can not use。 because same operator on different type expression same mean but different implementation and complexity。 so why operator overload can don't care about implementation but 'in' operator need。

On Thursday, October 24, 2019 8:40:59 PM MDT lili via Digitalmars-d-learn wrote:
> On Thursday, 24 October 2019 at 22:40:31 UTC, Jonathan M Davis
>
> wrote:
> > On Thursday, October 24, 2019 7:04:56 AM MDT Paul Backus via
> >
> > Digitalmars-d- learn wrote:
> >> On Thursday, 24 October 2019 at 12:58:11 UTC, lili wrote:
> >> > Hi:
> >> >    In Dlang where is strange design. The in expression can
> >> >
> >> > only
> >> >
> >> > use to associative array, why array can not use in expression.
> >>
> >> Checking for the presence of an item in an array requires a linear search. You can do it with std.algorithm.searching.canFind:
> >>
> >> https://dlang.org/phobos/std_algorithm_searching.html#.canFind
> >
> > In particular, the reason that linear search is considered
> > unacceptable for
> > in is so that generic code can rely on its performance. The
> > idea is that
> > types shouldn't implement the in operator unless they can do so
> > with
> > O(log n) or better (O(log n) being what it costs to get to an
> > item in a
> > balanced binary tree like a red-black tree). That way, when you
> > calculate
> > the complexity of any algorithm using in, you can assume that
> > it's O(log n)
> > at worst. Having it be O(n) instead (like it would be for an
> > array) would
> > drastically increase the complexity of the algorithm and make
> > it take much
> > longer when processing a large number of items. And the
> > standard library
> > provides functions like canFind or find for finding elements in
> > an array, so
> > having in work with arrays wouldn't add any functionality. It
> > would
> > basically just change the syntax you'd use for finding an
> > element in an
> > array.
> >
> > - Jonathan M Davis
>
>   This reason somewhat farfetched， Think about that if this reason
> is right， the operator overload can not use。 because same
> operator on different type expression same mean but different
> implementation and complexity。 so why operator overload can don't
> care about implementation but 'in' operator need。

std.container specifically discusses the expected, worse-case complexity of (i.e. Big-O complexity) all of the various container-related functions - including the in operator:

https://dlang.org/phobos/std_container.html

As such, anyone writing an algorithm using any of those functions can rely on the worst-case complexity of each operation and accurately calculate the overall, worst-case complexity of their algorithm. Sure, someone could choose to overload the in operator in a manner which does not follow those rules, but it's considered bad practice to do so, and no official implementation of any kind is going to provide a function with a worse complexity than what std.container lays out - and that includes operators for the built-in types like a dynamic array. This is basically the same approach that C++ takes with its STL containers and their related operations.

- Jonathan M Davis

On 10/24/2019 05:58 AM, lili wrote:
> Hi:
>     In Dlang where is strange design. The in expression can only use to
> associative array, why array can not use in expression.

In addition to the big O surprise, there is another important issue that may be seen as either for or against supporting the 'in' operator for arrays: With associative arrays, 'in' takes the keys; since keys are index values for arrays, the in operator would be trivially


  return (key < __length
          ? &__ptr[key]
          : null);

Given the two differences, 'in' does not make sense on arrays:

- Big O is different

- One wants to use keys for associative arrays but (likely) values for arrays

Ali

On Friday, 25 October 2019 at 05:17:35 UTC, Ali Çehreli wrote:
> - Big O is different

No it isn't. Worst case lookup of an associative array lookup is O(n) too. It can easily be 'achieved' by having a key type with:
```
size_t toHash() const scope pure {
    return 0;
}
```

The fact that std.container specifies a worst-case time complexity for operations on its data structures doesn't mean every other type has to comply to those too.
I can overload the 'in' operator on my types to something that takes exponential time if I want, just like "+" can also be overloaded to a linear time operation on e.g. BigInt.

> - One wants to use keys for associative arrays but (likely) values for arrays

Then we implement `in` to look for values in arrays, just like users would expect.

On Friday, 25 October 2019 at 09:25:21 UTC, Dennis wrote:
> I can overload the 'in' operator on my types to something that takes exponential time if I want, just like "+" can also be overloaded to a linear time operation on e.g. BigInt.

Worth noting that `opIn` is a D1 operator overload, and thus deprecated as of 2.088.0.

On Friday, 25 October 2019 at 15:52:50 UTC, Paul Backus wrote:
> On Friday, 25 October 2019 at 09:25:21 UTC, Dennis wrote:
>> I can overload the 'in' operator on my types to something that takes exponential time if I want, just like "+" can also be overloaded to a linear time operation on e.g. BigInt.
>
> Worth noting that `opIn` is a D1 operator overload, and thus deprecated as of 2.088.0.

That wasn't mentioned though? Does it reverse the arguments so
that the writeln() examples below can be more naturally ordered?

  #! /usr/bin/env rdmd
  import std.stdio;

  struct X {
      string data;

      bool opBinary(string op)(char p) if (op == "in") {
          foreach (c; data)
              if (p == c) return true;
          return false;
      }
  }

  void main() {
      auto x = X("hi there");
      writeln(x in 'i');
      writeln(x in '?');
  }

On Thursday, 24 October 2019 at 12:58:11 UTC, lili wrote:
> Hi:
>    In Dlang where is strange design. The in expression can only use to associative array, why array can not use in expression.

I don't see much of a problem why this couldn't be implemented as long as the user understands the limitations of it. In real life, linear searches are often completely acceptable when the number of items are in a few hundreds or less of them. Depends on the use case of course.

Many has answered because of search complexity but one thing is that use case with associative arrays is to have unique keys. This is not the case for arrays which allows duplicates which not to seldom the case. Naturally an implementation would take the first hit and return that object. Why it isn't implemented for arrays, I suspect it has to do more that the search can be ambiguous as the array allows duplicates. Still I think a linear search in an array should be implemented based on a first hit search.