----- Mensaje original ----- De: Sylvain Pion <Sylvain.Pion@sophia.inria.fr> 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