Retrieving the traversed range

Peter Alexander peter.alexander.au at gmail.com
Wed Aug 25 06:55:29 PDT 2010


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).



More information about the Digitalmars-d mailing list