On Feb 15, 2005, at 2:41 PM, Peter Dimov wrote:
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. ;-)
Actually the Metrowerks implementation does this, although it turns that optimization off if: 1. The client requests it. 2. Alignment is 1. I just had a hard time dealing with all of those bits wasted. :-)
Are there std::maps that store a next and previous pointer to optimize traversal at the expense of per-node overhead?
I haven't heard of one. Along those lines I did do an analysis of the cost of traversal though. If you have a perfectly balanced tree of 2^N - 1 elements (a full, balanced tree), and if you iterate from begin() to end(), then the number of pointer links you chase is 2*distance(begin(),end()). I.e. for my money your speed gain would be no greater than a factor of two, and due to the fact that your nodes are now up to 50% bigger, you could well realize a slow down just from the extra level-2 cache flush. But I haven't actually coded it up and performance tested it. If optimized iteration is really what you need, std::map probably isn't the container you want. A sorted vector, deque or list (or cdeque or slist) may be a better fit. map is good for the requirements of a strictly bounded log(N) lookup and insert/erase, plus iterator/reference stability. Iteration and per-element overhead are secondary concerns and therefore sacrificed. -Howard