From: Howard Hinnant (hinnant_at_[hidden])
Date: 2005-02-15 16:08:04
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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk