Thomas Witt wrote:
Bob Bell wrote:
Hi-
I was wondering what the rationale was for boost::filter_iterator not modeling anything more than a forward traversal iterator.
Cost.
Recently I was trying to use filter_iterator in a situation where I needed bidirectional traversal, but got stymied by this. Is there something about the notion of filtering that precludes bidirectionality? Or is this something that could be made to work?
In order to be able to be bidirectional the filter iterator would need at least another member, the beginning of the sequence and another ctor parameter, again the beginning of the sequence.
Is this so that when iterating backwards you can stop before "running off the beginning?" I'm in the unenviable position of not being able to use boost at work, but I needed some of the functionality of the iterator library, so I ended up implementing a subset of it myself. When it came to filter iterators, I implemented them as bidirectional. Initially, I had the extra iterators you mention, but I ended up getting rid of them. My reasoning was like this: Consider this forward loop: while (b != e) { // use *b; ++b; } Incrementing b will, internally, dereference its base iterator and call its filter function to determine when it's encountered a new element in the filtered pseudo-sequence. However, it must be prevented from incrementing past e. So b also carries a second, "sentinel" base iterator (that must be initialized to the same sentinel carried by e); when incrementing, if b reaches the sentinel, it doesn't dereference and test, it just stops. This makes sure that b will become equal to e, and the loop will terminate. Now consider a typical reverse loop, where we decrement backwards through [b, e): while (b != e) { --e; // use *e; } No "begin sentinel" is required to make this loop behave as expected. When b is created, it will point to the first element of the filtered pseudo-sequence; this means that eventually, e will become equal to b, and the loop will terminate. In fact, it seems that without a begin sentinel, uses of b and e are just as well-defined (or undefined) as equivalent ordinary iterators. For example, for an ordinary sequence [b, e), --b is well-defined only if there is something dereferencable there. For a filter iterator lacking a begin sentinel, the same thing is true. What do you think?
This is a non negligible cost that users that are ok with fwd iterators most likely don't want to pay.
If there's still some requirement to have the extra cost for bidirectionality (i.e., if there's a flaw in my analysis above), I wonder if there isn't some metaprogramming trickery that could make the cost exist for only those who need bidirectionality, while those who need only forward iteration don't pay. Not that I'm volunteering to write it. ;-) Bob