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

From: JOAQUIN LOPEZ MU?Z (joaquin_at_[hidden])
Date: 2005-02-15 15:59:19

----- Mensaje original -----
De: Peter Dimov <pdimov_at_[hidden]>
Fecha: Martes, Febrero 15, 2005 8:41 pm
Asunto: std::map per-node overhead (Was: [boost] Re: shared_ptr doubts)

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

I'm pretty certain no commercial STL implementation exists that
does this, precisely because of the overhead. Users might not
care, but implementors surely do.

Incidentally, a multi_index_container with an ordered index
and a sequenced index pretty much mimics the kind of data
structure you've got in mind.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo.