From: Sylvain Pion (Sylvain.Pion_at_[hidden])
Date: 2004-12-12 05:23:06
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.
> PS: I think the std is rather sloppy in this issue.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk