Beman Dawes <bdawes@acm.org> 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