"in" everywhere

Tomek Sowiński just at ask.me
Thu Oct 7 15:14:26 PDT 2010


bearophile napisał:

> Another solution is to support the "in" operator for dynamic arrays too,
> and define a new attribute, like @complexity(), plus an Enum that allows
> to specify the worst case complexity. So associative arrays are annotated
> with @complexity(O.linear), while the function that searches for
> items/substrings in arrays/strings is @complexity(O.constant). At
> compile-time the generic code is then able to query the computational
> complexity of the "in" operator implementation. The problem is that the
> compiler today can't enforce functions annotated with
> @complexity(O.constant) to actually not perform a linear search (but I
> don't think it's a problem, today if the Range protocol asks an operation
> to not be worse than O(n ln n) the compiler doesn't enforce it).

Good idea. It would make a nice use case for user-defined attributes in D3. Making the 
language aware of @complexity specifically doesn't buy much, all you need is:

__traits(getAttribute, opIn, @complexity).bigOh == O.constant

-- 
Tomek


More information about the Digitalmars-d mailing list