Boost logo

Boost :

From: Sylvain Pion (Sylvain.Pion_at_[hidden])
Date: 2004-12-11 11:39:44


On Sat, Dec 11, 2004 at 09:00:05AM -0500, David Abrahams wrote:
> > 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).

But N/M does not have to be bounded by a constant when N grows.

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

That's too much for me.
I tend to think that it's stretching what users might expect when they see
"constant time amortized operation".

-- 
Sylvain

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