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 :
> http://lists.boost.org/MailArchives/boost/msg47144.php
>
> 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
http://www.boost-consulting.com

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk