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

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2004-12-12 09:56:00

----- Mensaje original -----
De: Sylvain Pion <Sylvain.Pion_at_[hidden]>
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