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".
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk