std::map per-node overhead (Was: [boost] Re: shared_ptr doubts)

From: Peter Dimov (pdimov_at_[hidden])
Date: 2005-02-15 14:41:35

David Abrahams wrote:
> Howard Hinnant <hinnant_at_[hidden]> writes:
>
>> On Feb 15, 2005, at 9:49 AM, David Abrahams wrote:
>>
>>> 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

You could have pretended that you had in mind an implementation where 
pointers are always even and one of the least-significant bits is used as a 
color bit. ;-)

Are there std::maps that store a next and previous pointer to optimize 
traversal at the expense of per-node overhead?

(Of course my original point was that most people don't care about the 
per-node overhead and those that do just use a different data structure.)