Bidirectional range dilemma
Peter Alexander
peter.alexander.au at gmail.com
Sun Jan 13 04:05:25 PST 2013
I'm repeatedly hitting a range API problem in my combinatorics
library. Many of the ranges require (potentially sizeable)
internal buffers to maintain their current state (permutations,
set partitions, power sets etc.) Also, many of these ranges are
bidirectional. What this means is they have to store *two*
buffers, one for the front, and one for the back.
This is a problem because 90% of the time you'll only iterate
forward, and of the remaining 10%, 9% is just iterating
backwards, and maybe 1% of the time you want to iterate from both
the front and back in the same iteration. This means that 99% of
the time, having two buffers is just wasted memory. Of course,
I'm plucking these numbers from the air, but you get the idea.
To make matters worse, thanks to the lack of logical const
there's no way the buffers can be lazily allocated on first use.
The only (ugly) solution I can come up with is to create three
different ranges, e.g.
ForwardPermutations
ReversePermutations
BidirectionalPermutations
(or equivalently, one range with an iteration policy).
I'd rather not do that. Any ideas on how to resolve this?
More information about the Digitalmars-d
mailing list