Hi Dave, ----- Mensaje original ----- De: David Abrahams <dave@boost-consulting.com> 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