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

...

Howard Hinnant <hinnant@twcny.rr.com> 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

David Abrahams wrote: 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.