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
