Boost logo

Boost :

From: Beman Dawes (bdawes_at_[hidden])
Date: 2005-02-17 20:45:23

At 11:11 AM 2/15/2005, Howard Hinnant wrote:

>On Feb 15, 2005, at 9:49 AM, David Abrahams wrote:
>>> Absolutely, all designs have certain irreducible overhead - I didn't
>>> mean to imply otherwise. In the case of std::map, one should expect
>>> an instance to be on the large-ish side. Also, one should expect the
>>> per node overhead to be two pointers and probably another word for
>>> the tree balancing algorithm.
>> You don't need any storage for rebalancing. Typical map nodes have 3
>> pointers: parent, left child, and right child.
>If it is a red-black tree, you need to store the color of each node.
>This information requires 1 bit, which can easily be padded to a word.
>If it is a AVL tree, each node needs to store its tilt. This
>information requires 2 bits.
>Or is there a new technique I'm about to learn about? :-)

I don't know of any 100% portable technique, but on many platforms pointers
to heap allocated memory within a node never have one or more of the
low-order bits on. This opens those bits up to be used as color or similar
flags, at the cost of having to "and" them off before dereferencing the
pointer. If the pointer is wrapped in a class, and can only be accessed by
member functions, then there is no chance of inadvertently forgetting the
"and", and an assert can be done on construction to verify the low-order
bits involved are actually zero. A bit ugly and I'd hate to see it used in
portable Boost code, but if you are writing library code for a specific
platform, why not?


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