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
> 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
> traversal at the expense of per-node overhead?
> (Of course my original point was that most people don't care about
> per-node overhead and those that do just use a different data
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk