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

From: Martin Knoblauch Revuelta (mkrevuelta_at_[hidden])
Date: 2006-10-31 12:48:45

On 10/31/06, Rene Rivera <grafikrobot_at_[hidden]> wrote:
> Martin Knoblauch Revuelta wrote:
> > On 10/31/06, Rene Rivera <grafikrobot_at_[hidden]> wrote:

> 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 do. They are in the m_prev and m_next pointers of the dummy node.
Additionally, the implementation is simpler this way.

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

Are you mathematically sure that this ensures the AVL balance
constraints and doesn't require unnecessary rotations? Interesting.
This calls for an experiment (I'm a skeptic, as you see ;-)

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

I'm not sure of what you mean with "rank invariant" but I guess I'm
using it for the count, the index operator, iterators... but not for
the NPSV thing. That's why I call it "Non-Proportional...".

> >> * I don't see how not having a static allocator prevents moving nodes
> >> across equally typed containers.
> > [..]
> 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.

Great! Then I will get rid of the static allocator.

> >> * You should use the allocator types instead of making types out of the
> >> value type directly.
> > [..]
> 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;

Ok. Thanks ;-)

> >> * 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<>.

Of course. The m_parent member of the dummy node is also used: it
stores a NULL pointer. Only dummy nodes have this pointer set to NULL.
By checking this, I can ensure that the cast will be ok.

Thanks,

Martin