Suggestion: Operator `in` for slices
Dennis
dkorpel at gmail.com
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:
```D
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