Why must a bidirectional range also be a forward range?

Joseph Rushton Wakeling joseph.wakeling at webdrake.net
Thu Sep 19 09:31:32 UTC 2019


Hello folks,

A question that occurred to me while implementing a new data 
structure recently, which I'm not sure I've ever seen a reason 
for.

Why must bidirectional ranges also be forward ranges (as opposed 
to just input ranges)?

It doesn't seem to me that the `save` property is inherently 
required to iterate backwards over a range -- just the `back` and 
`popBack` methods.

It makes sense that, for bidirectionality, the range needs to be 
deterministic, so that iterating backward gives the exact same 
elements as iterating forward, just in reverse order.  But it 
seems strange to require the `save` property in order to 
automatically assume deterministic behaviour.

For context, the use-case I have is a data structure which stores 
an internal buffer as an array.  A robust `save` method would 
therefore have to duplicate the array (or at least the active 
subset of its contents).  This means a fresh heap allocation per 
`save`, which has some nasty implications for phobos algorithms 
that eagerly `.save` when they can.

So, I'd rather not implement `save` in this case.  But there is 
nothing that blocks implementing `back` and `popBack`; yet I 
can't use these with any of the functionality that requires 
bidirectionality, because the current `isBidirectionalRange` 
check requires `save`.

So what gives?  Are there some reasons for the `save` requirement 
on bidirectional ranges that I'm missing?  And regardless, any 
advice on how to handle my particular use-case?

Thanks & best wishes,

       -- Joe


More information about the Digitalmars-d-learn mailing list