Thanks for the replies Andrei, Steven. It's a bit disappointing that there is no solution to this, although I think you already know what I'll suggest as a solution :) (cursors/iterators)
It's quite funny really, because I had decided to drop the whole iterator thing and just accept that the occassional small performance/memory drop wasn't that big of an issue. In order to try an appreciate ranges more I decided to try my hand at writing a generic combinatorics library. Unfortunately, the first function I tried to write (nextPermutation) requires exactly what I have described here (you need to search for an out-of-order pair then reverse the end of the range after that pair)! Doing the popBackN thing you described changes nextPermutation's average case performance from O(1) to O(n) (well, I think it's O(1), I haven't really done the math yet, but it seems right at a glance).
