About the in expression, Why can't use with array.

[Jonathan M Davis]

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