On Tuesday, 24 December 2013 at 11:57:04 UTC, 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);
}
---
I think you are missing the point of what happens if the step is
not 1 (or if the passed in type can have fractional input). EG:
iota(0, 105, 10);
or
iota(0, 10.5);
In this case, "back" should be 100, and not 95. To compute back,
you need to be able to evaluate length, and to add length*inc to
front.
