Suggestion: Operator `in` for slices

Dukc ajieskola at
Sun Dec 19 09:59:41 UTC 2021

On Saturday, 18 December 2021 at 20:17:51 UTC, Quirin Schroll 
>> Nah, the general rule against it is due to speed/computational 
>> complexity. The `in` operator on AAs has a speed of O(log n) 
>> or O(1). `in` on slices would exceed that being O(n).
> How is that even a criterion? `foreach` on arrays has O(n) 
> complexity as well. You cannot say it's okay for `foreach` 
> because it obviously has to be that way.

`foreach` is not supposed to give that guarantee. `in` is. Just 
like the indexing operator (`range[index]`). That does not say 
you can't define a function that checks for an element in O(n) 
time, but it should be called something else than `in` then.

It's the same reason as why we don't define `range[index]` as 
`` for all forward ranges that 
do not explicitly declare `opIndex`. It's not that you can't 
index a range like that, but that we usually want a compile error 
rather than silent O(n) indexing if we are expecting O(1) or 
O(log n) indexing.

> The same can be said for linear search. It doesn't take a 
> genius that searching an unordered structure cannot be better 
> than O(n) in the worst case.

But it isn't always immediately clear to the reader what the type 
of the data structure is.

More information about the Digitalmars-d mailing list