Suggestion: Operator `in` for slices
Dukc
ajieskola at gmail.com
Sun Dec 19 09:59:41 UTC 2021
On Saturday, 18 December 2021 at 20:17:51 UTC, Quirin Schroll
wrote:
>> 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
`range.save.dropExactly(index).front` 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