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

From: Sylvain Pion (Sylvain.Pion_at_[hidden])
Date: 2004-12-11 17:25:40

On Sat, Dec 11, 2004 at 09:58:17PM +0100, JOAQUIN LOPEZ MU?Z wrote:
> De: David Abrahams <dave_at_[hidden]>
> [...]
> > 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.
> 
> This is not correct, IMHO. Consider a set::iterator
> doing a full traversal from begin to end. From the
> rb-tree point of view, this is equivalent to visiting
> the whole tree in an inorder fashion. And it is easy
> to see that every node will get hopped from at most
> three times:
>  - when visiting its left subtree.
>  - when visiting its right subtree.
>  - when leaving to an upper level.
> 
> So the total number of hops is bounded by 3*N, and the
> average cost of incrementing is constant, which is
> the same as to say that increment complexity is
> amortized constant, as required by the std.

I can't find anything in the standard that says that the cost should be
amortized over the full traversal of the std::set.
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 sequences
we 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