Boost logo

Boost :

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, gregod at, cpdaniel at, john at