Boost logo

Boost :

From: David Abrahams (dave_at_[hidden])
Date: 2004-12-11 09:00:05

Sylvain Pion wrote:
> On Sat, Dec 11, 2004 at 12:38:27AM -0500, David Abrahams wrote:
>> Okay, I buy it.
> You forgot that you already bought it 18 months ago :)
> See the thread starting at :
> Probably a note in the documentation concerning this "non-intuitive"
> fact would help.

Probably a simple fix to the library would help more.

> Another note : filter_iterator's complexity may not match the requirements
> of iterators (increment in constant time amortized), depending on the
> predicate's behavior.

That's a tricky question, which is why it's been left unanswered. You
might look at it this way: for any filter and sequence of length N there
are some constant number of elements M that will pass the filter. If
the cost of traversing the unfiltered sequence is O(N) then so is the
cost of traversing the filtered sequence. But N/M is a constant, so
it's also N/M O(M) and therefore also O(M).

Is that stretching the definition of an iterator? I'm not sure.

Dave Abrahams
Boost Consulting

Boost list run by bdawes at, gregod at, cpdaniel at, john at