From: David Abrahams (dave_at_[hidden])
Date: 2005-02-21 10:43:51
Beman Dawes <bdawes_at_[hidden]> writes:
> 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?
It's fine to use it conditionally in portable code, providing you have
a (non-portable, obviously) way to find out if the low bit of the
pointer is needed.
-- Dave Abrahams Boost Consulting www.boost-consulting.com
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk