std.range.iota enhancement: supporting more types (AKA issue 10762)

H. S. Teoh hsteoh at quickfur.ath.cx
Tue Dec 24 07:39:24 PST 2013


On Tue, Dec 24, 2013 at 11:57:03AM +0000, Jakob Ovrum wrote:
> On Tuesday, 24 December 2013 at 11:47:12 UTC, Francesco Cattoglio
> wrote:
> >Correct, but there's no way to compute "back" with less than O(n)
> >complexity, unless division by increment is available. (Actually,
> >I think we can achieve O(log n) with multiplication alone, but I
> >think it might be lots of work with very little benefits)
> >I should have specified better: we need to provide `back', and
> >Andrei suggested that no primitive should be more than complex
> >than O(1).
> 
> Implement `back` is really trivial.
> 
> Simplified example:
> ---
> auto iota(T)(T start, T end)
> {
>     static struct Result
>     {
>         T start, end;
> 
>         bool empty() @property { return start == end; }
>         T front() @property { return start; }
>         void popFront() { ++start; }
>         T back() @property { return end; }
>         void popBack() { --end; }
>         // etc
>     }
> 
>     return Result(start, --end);
> }
> ---

This code is wrong for iota(1.0, 9.5), because .back must be of the form
start + n*step for some integer n, but in this case end is not an
integral multiple of step away from start. (It's not only wrong for
.back, it also won't terminate because start==end will never hold.)


T

-- 
I think the conspiracy theorists are out to get us...


More information about the Digitalmars-d mailing list