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

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2004-12-11 15:58:17

Hi Dave,

----- Mensaje original -----
De: David Abrahams <dave_at_[hidden]>
Fecha: Sábado, Diciembre 11, 2004 9:01 pm
Asunto: [boost] Re: boost::filter_iterator Model
[...]
> 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.

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