Boost logo

Boost :

From: David Abrahams (dave_at_[hidden])
Date: 2004-12-11 15:01:23


Sylvain Pion wrote:
> 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 the right way to understand the complexity guarantee?
I'm really asking. Consider std::set. As the size of the set grows, the
average cost of incrementing an iterator grows without bound. In case
that's not obvious, think of the middle of a balanced binary tree, where
an iterator has to make 2 logN steps through the tree to move between
elements.

>> 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".

This is tricky territory. It certainly warrants a note in the
documentation, but I'm not exactly sure what to say.

-- 
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