Why function template 'among' is of complexity O(1) and not O(n)?

Chris Williams yoreanon-chrisw at yahoo.co.jp
Wed Feb 19 17:41:24 PST 2014


On Thursday, 20 February 2014 at 00:36:38 UTC, anonymous wrote:
> On Wednesday, 19 February 2014 at 22:46:45 UTC, Chris Williams
> wrote:
>> When the template writes out the definition of the function, 
>> if the parameters can be interpreted during compile-time, then 
>> the foreach ( O(n) ) will be run by the compiler to detect the 
>> correct parameter and the function will be written out as just 
>> as a return statement in the body, without the loop. So during 
>> runtime, the function would have an O(1) runtime.
>
> That's an optimization the compiler may do, but it's not
> guaranteed. And `among` is not special in this regard.

I think "expected to do" is probably the better phrasing at the 
moment. Traits/annotations would be largely unusable unless 
foreach was able to behave as a static construct. And since there 
is no way for one to declare "static foreach", the only way 
foreach can be used for running over traits, is for the compiler 
to detect constant values in the parameters to the statement.


More information about the Digitalmars-d-learn mailing list