Suggestion: Operator `in` for slices

Dennis dkorpel at
Sat Dec 18 20:46:06 UTC 2021

On Saturday, 18 December 2021 at 18:47:33 UTC, Adam Ruppe wrote:
> The `in` operator on AAs has a speed of O(log n) or O(1). `in` 
> on slices would exceed that being O(n).

Who do people keep repeating that?

- Worst case time complexity of the `in` operator in AA's is 
actually O(n). This can easily happen in practice when your 
`toHash` has a poor implementation, which I have had before

- In custom types you can overload the `in` operator to something 
with arbitrarily bad time complexity.

- Despite scaling with O(n), a linear scan is pretty fast. You 
can probably scan your entire RAM in a matter of seconds.

The whole "it ruins performance guarantees" so far seems 
completely hypothetical and is not something that came from 
experience with actual code.

The problem with `in` for slices to me is that it would be 
inconsistent with how it works for AAs, where `in` searches for a 
*key* and returns a pointer to a *value*. The same for slices 
would look like this:
T* opIn(size_t i, T[] arr)
     return i >= arr.length ? null : &arr[i];

void main()
     int[3] a = [10, 20, 30];
     assert((10 in a) == null); // index 10 is out of bounds
     assert((2 in a) == &a[2]);

But people suggest `in` to search a *value* in a slice.

I've once overloaded the `in` operator for a custom 2D array type 
used to represent a maze in which path finding was done. There it 
was useful for bounds checking since writing comparisons with 
`width` and `height` all the time is cumbersome. I wouldn't mind 
giving `in` this meaning so you can do easy bounds checks in 
slices as well, but I think it will be to confusing for newcomers 
expecting `in` to work like in Python.

More information about the Digitalmars-d mailing list