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

From: Rene Rivera (grafikrobot_at_[hidden])
Date: 2006-10-31 10:00:58

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.

> Many
> operations benefit from the posibility of fast iteration through
> m_next and m_prev. For example: begin() and end() are O(1).

If you want constant time for begin() and end() you could store 
references to them in the container and update them as needed over time.

>> * I suspect you don't need the m_height either. But I don't know what
>> you are using it for yet.
> 
> For balance. IMO, the logic of re-balancing becomes simpler by having
> m_height instead of the usual {-1,0,+1}.

Right, AVL balancing... In my version I implemented a balancing that 
uses the count/width directly obviating the need for extra coloring 
information.

>> * In my rank tree implementation the only extra field per node is the
>> count, what you call width (as separate node and total). If I remember
>> correctly in CLRS they describe the possibility of the count not
>> directly reflecting the subtree+1 size to allow for sparse trees. I
>> suspect that you can remove the need for the different m_node_width and
>> m_total_width, using one only, by deducing the m_node_width from "count
>> - left_count - right_count".
> 
> The width is based on the same concept as count, but they are not
> related at all. Note that W might be float, for example.

I don't see how making it a float invalidates the calculation as it's 
the rank statistic invariant. Are you not using that invariant? If not, 
what is your invariant?

> I might deduce m_total_width from m_node_width by recursing through
> the whole subtree every time. Obviously, this would spoil the whole
> thing.

Hm, I guess you aren't using the rank invariant then.

>> * I don't see how not having a static allocator prevents moving nodes
>> across equally typed containers.
> 
> It shouldn't, but it depends on how correct is the allocator class. I
> read in the documentation of SGI that allocators must be fully static,
> allowing deallocation of something by a different object of that one
> used for allocation (perhaps even destructed in the meantime). Is this
> true for _all_ std and boost allocators too?

The pertinent passage is 20.1.5p4:

Implementations of containers described in this International Standard 
are permitted to assume that their Allocator template parameter meets 
the following two additional requirements beyond those in Table 32.

        — All instances of a given allocator type are required to be 
interchangeable and always compare equal to each other.

>> * You should use the allocator types instead of making types out of the
>> value type directly.
> 
> I don't understand. Do you mean the rebind trick? I thought this was
> the standard way.

I meant that instead of:

     typedef T & reference;
     typedef const T & const_reference;

You use:

     typedef typename A::reference reference;
     typedef typename A::const_reference const_reference;

>> * You have a variety of C style casts, and you happen to be casting
>> "this". That's frowned upon, and truthfully I can't see why you do it.
> 
> I'll change them to C++ casts.

Hopefully you mean static_cast<>.

-- 
-- Grafik - Don't Assume Anything
-- Redshift Software, Inc. - http://redshift-software.com
-- rrivera/acm.org - grafik/redshift-software.com
-- 102708583/icq - grafikrobot/aim - grafikrobot/yahoo