Re: [Boost-users] [Iterator] filter_iterator over greedy?

Subject: Re: [Boost-users] [Iterator] filter_iterator over greedy?
From: Sebastian Redl (sebastian.redl_at_[hidden])
Date: 2013-01-07 10:02:44

On 07.01.2013, at 14:49, Robert Jones wrote:

> Hi Folks,
> 
> Somewhat to my surprise this code, simply creating a filter_iterator, evaluates the predicate
> until an element satisfying the predicate is found. This seems wrong to me. Shouldn't evaluation
> of the predicate be delayed until the filter_iterator is dereferenced?

That's not a good idea.

a) Dereferencing is a const operation. On the most basic level, this means that the inner iterator must be mutable. When you add C++11's multi-threading guarantees and expectations, though, you'll find that the standard library may assume that dereferencing the same iterator concurrently from multiple threads is safe [1]. This means that you would have to make that lazy start-seeking thread-safe yourself. Since you don't know anything about the underlying iterator, pretty much the only way to do that is to carry a mutex with the iterator and lock it on that operation. And you would have to create a mutex every time you copy the iterator. Iterators are supposed to be small and cheap to copy - an iterator containing a mutex is neither.
b) Equality testing has the same issue. It should be const, but it needs to first make sure both iterators are "canonical" (don't point to a filtered-out element), or this assert might fail:
iterator b = a;
*a; // could advance the underlying iterator
assert(b == a);
c) You need to test the predicate on every single dereference operation. Unless you want to keep *another* piece of state around that tells you whether you've already tested the current position. Then you need to test that. And you also need to test on every comparison. So you get two calls to the predicate for every element in a simple iterator read loop.

So yeah, not a good idea.

[1] http://herbsutter.com/2013/01/01/video-you-dont-know-const-and-mutable/