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