From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2004-12-11 15:58:17
----- 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
- 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
Boost list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk