[boost] Re: shared_ptr doubts

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
www.boost-consulting.com