----- Mensaje original ----- De: Sylvain Pion <Sylvain.Pion@sophia.inria.fr> Fecha: Domingo, Diciembre 12, 2004 11:23 am Asunto: Re: [boost] Re: boost::filter_iterator Model

On Sun, Dec 12, 2004 at 02:46:12AM +0100, JOAQUIN LOPEZ MU?Z wrote:

...

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.

My example prooves it for rb-trees, but they could be made compliant : just add a doubly-linked list linking the tree leaves, in parallel to the rb-tree, and use it for traversing.

Good catch. This is plain constant time, which leaves the question of what "amortized" meant in the first place. (Incidentally, you can get this in Boost.MultiIndex if you combine an ordered and a sequenced index.)

...

PS: I think the std is rather sloppy in this issue.

I agree.

-- Sylvain _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost