On 10/31/06, Rene Rivera <grafikrobot@gmail.com> wrote:
Martin Knoblauch Revuelta wrote:
On 10/31/06, Rene Rivera <grafikrobot@gmail.com> 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