On Sat, Oct 10, 2015 at 09:52:22AM +0300, Andrei Alexandrescu via Digitalmars-d wrote: > On 10/10/15 12:58 AM, Eric Niebler wrote: > >Trying to express algorithms without any clear abstraction of > >"position within range" (independent of ranges) is hard and awkward, > >and occasionally causes algorithms to be less efficient. > > I agree that ranges are a weaker basis than iterators. But it's not > necessarily that a notion of position is the only way out. > > Ranges can be made as strong a basis by adding the O(1) primitives > r1.before(r2) and r1.after(r2) that return the prefix/suffix following > r2 within r1. With those I hope to be able to show easily that > algorithms needing "iterator in the middle" can be redone.
I assume .before would be implemented in a specialization of forward ranges, and .after in a specialization of bidirectional ranges? > I think I need to sit down and define these primitives (albeit they > aren't used that frequently) and use them in a few fundamental > algorithms to just close the matter once and for all. [...] It would also fix the current bug in nextPermutation that claims that it supports bidirectional ranges, when in fact it requires random access ranges, precisely because reversing the last n elements requires the "iterator in the middle" construct. T -- Gone Chopin. Bach in a minuet.