Boost logo

Boost :

From: David Abrahams (dave_at_[hidden])
Date: 2005-02-15 13:59:10

Howard Hinnant <hinnant_at_[hidden]> writes:

> 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.

Oh, I didn't understand that he meant color info. I guess that is
only for rebalancing, isn't it?

/me crawls back under rock

> 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? :-)

/me burrows several inches down into dirt under rock

Dave Abrahams
Boost Consulting

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