Boost logo

Boost :

From: Rene Rivera (grafikrobot_at_[hidden])
Date: 2006-10-31 10:34:32

Joaquín Mª López Muñoz wrote:
> 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.

Yes, sorry, I meant amortized time :-)

-- Grafik - Don't Assume Anything
-- Redshift Software, Inc. -
-- rrivera/ - grafik/
-- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo

Boost list run by bdawes at, gregod at, cpdaniel at, john at