Re: [boost] [proposal] Sequence container with O(log n) random access_and_ O(log n) insertion/removal (wherever)

From: Joaquín Mª López Muñoz (joaquin_at_[hidden])
Date: 2006-10-31 10:24:25

Rene Rivera ha escrito:

> Martin Knoblauch Revuelta wrote:
> > On 10/31/06, Rene Rivera <grafikrobot_at_[hidden]> wrote:
>
> >> * There's no need for the m_next and m_prev fields. You can do inorder,
> >> preorder, postorder, and others without them.
> >
> > Yes, I could, but operators ++ and -- would become O(log n).
>
> I beg to differ. All those traversals can be implemented O(1) per
> iteration. This is the case for all binary trees.

Umm, it is *amortized* O(1), as allowed by 24.1/8. Without amortization
being taken into account, ++ and -- have a worst case complexity O(log n),
if I'm not missing something. Although not explicitly stated in the standard,
the amortization here has to be done for a complete traversal from begin
to end.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo