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. 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? :-) -Howard