On Tuesday, 24 December 2013 at 11:30:32 UTC, Jakob Ovrum wrote:
On Tuesday, 24 December 2013 at 11:25:04 UTC, Francesco
Cattoglio wrote:
There's a catch: if we want bidirectional, we need the last
element of the range.
Are you sure you understand bidirectional ranges correctly? Any
range that has the `back` property and `popBack` method are
bidirectional.
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).
