More uses of operator "in"

[Jonathan M Davis via Digitalmars-d-learn]

On Tuesday, October 28, 2014 18:38:18 via Digitalmars-d-learn wrote:
> To answer your question: Computational (or memory) complexity is
> not an implementation detail, because it has a very noticeable
> effect. Therefore, one should not hide an O(n) or worse operation
> behind a harmless looking expression. It's not a technical
> requirement, of course, but a convention that makes a lot of
> sense IMO.
>
> D is relatively consistent in this respect. Not only does it
> apply to `in` and the aforementioned indexing and slicing, but
> there's also the convention that ranges shouldn't provide
> operations they cannot implement cheaply. For example, a
> singly-linked list shouldn't provide `back` and `popBack()`
> primitives, because while it is possible to implement them, they
> would be expensive, which could surprise an unsuspecting user.

Indeed. And the other thing that needs to be taken into account is generic
code. A function templated on type T which uses in on that type can rely on
in being O(lg n) at the worst, whereas if in worked with something like
arrays, then it would suddenly be O(n), which could have a huge impact on
performance depending on where the function was used. This is why both C++ and
D provide the computational complexity of the operations on their standard
container types and in some cases require that a particular operation have no
worse than a particular complexity. Without that, algorithms can't make
guarantees about their complexity, and it could have very negative impact on
the performance of some programs.

- Jonathan M Davis