Re: [boost] Re: boost::filter_iterator Model

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2004-12-11 20:46:12

----- Mensaje original -----
De: Sylvain Pion <Sylvain.Pion_at_[hidden]>
Fecha: Sábado, Diciembre 11, 2004 11:25 pm
Asunto: Re: [boost] Re: boost::filter_iterator Model

[...]
> 
> I can't find anything in the standard that says that the cost 
> should be
> amortized over the full traversal of the std::set.

The only reference I'm aware of about complexity guarantees
for iterators is in [lib.iterator.requirements], 24.1.8:

"All the categories of iterators require only those
functions that are realizable for a given category in
constant time (amortized). Therefore, requirement tables
for the iterators do not have a complexity column."

Admittedly, this quote does not state against which
sequence the complexity must be amortized. From my
point of view, the intended meaning is that the
amortization is done wrt to full traversal: otherwise,
even STL iterators cannot be compliant, as your
example prove.
When working with infinite sequences, "full traversal"
does not make sense, but it's obvious how to cover
this case with limit considerations.

Maybe this is a good question for comp.std.c++?

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo

PS: I think the std is rather sloppy in this issue.

> And it's possible to find sub-ranges which take non-bounded 
> average time
> to traverse, when the size of the std::set increases :
> - take the range [ (begin+end)/2 - n ; (begin+end)/2 + n ] in an 
> std::set  of size() = 2^(2^n).  This is a sequence of ranges of 
> size 2n, and which
>  take at least O(2^n) to traverse, and so definitely not constant 
> time  amortized [over the length of the range]...
> 
> When considering an amortized cost/complexity, it refers to sequences,
> whose lengths grow to infinity, but here nothing specifies which 
> sequenceswe are considering.  And if you allow any kind of 
> infinite sequences, then
> set::iterator does not have the required complexity, from the 
> example above :(
> 
> What am I missing ?
> 
> -- 
> Sylvain
> _______________________________________________
> Unsubscribe & other changes: 
> http://lists.boost.org/mailman/listinfo.cgi/boost