So a while back I saw Andrei Alexandrescu's talk on ranges vs iterators and was inspired. So I rewrote a portion of the STL to use ranges to see if what he was saying was correct and how things worked out. I've finished a bunch of range traits and functions, a vector and list container, and have been working through the usual standard algorithms (find, search, unique, ect...) and came across a weird problem. Before I get to the question though a quick review of how I implemented ranges.
Working with ranges is closer to working with the raw containers than iterators interface-wise. You have Empty() to test if there are elements in the range. PopFront() and PopBack() remove the first/last element from the range. Front() and Back() are used to access the first/last element. There's also a Slice() function which allows me to take a subrange of the range. One thing to note is that ranges cannot be 'enlarged'.
In the D programming language there's a function called findSplit() http://dlang.org/phobos/std_algorithm.html#findSplit which I was trying to implement. With iterators this is a simple single pass algorithm regardless of the iterator type (ie. the iterators can be forward, bidirectional, random, any way it works easily). With ranges I can implement the algorithm with random ranges (ie. the type of range that one would get from a vector) as the Slice() function is constant time for random ranges. Slice() is linear for bidirectional ranges (the type of range used to traverse a list), which makes the findSplit() algorithm take essentially multiple passes (which for such an essential algorithm is unacceptable).
I can't think of any way to do this algorithm cleanly and efficiently with ranges, but it seems Andrei succeeded. Am I missing something? Or is this a fundamental problem with ranges? Any thoughts/ideas are welcome.