From: corwinjoy (cjoy_at_[hidden])
Date: 2002-01-08 17:33:09
--- In boost_at_y..., "Greg Colvin" <gcolvin_at_u...> wrote:
> From: "dave_abrahams" <david.abrahams_at_r...>
> > Reviving an old thread:
>
> I'd forgotten about this thread, so remind me please, in
> what way does std::multimap fail to meet your needs for
> an associative container.
>
Basically, when Mike and I wrote the sorted vector container we
already had a fair amount of code that relied on multimap. The
issues that made us want to move to a sorted vector were:
1. Speed. A sorted vector can perform *significantly* faster in terms
of sort time than the standard tree implementation for multiset. For
larger data sets this starts to make a big difference. (See the
benchmarks in the document link below).
2. Memory. The tree implementation for multimap imposes a
significant memory overhead / cost. Many implementations will have a
tree node like:
struct Node {
Pointer left, right, parent;
RedBlack color;
Value value;
}
giving a significant memory overhead for every element stored -
especially if the element sizes are small.
The goal of the vec_multiset was to develop a vector based
implementation of a multimap that could be used as a substitute for
situations where multimap was employed but which would run faster and
use less memory. We were able to come fairly close in maintaining
the invariants given by multimap - but we didn't get all them - such
as exception safety - see the docs. The issue, of course, is that
there are other solutions for the same problem (such as a vector of
pointers or a straight vector) which give different performance /
iterator invariant tradeoffs. Probably there is no one "best"
container for all these situations - but I think it is worth
exploring alternatives to multimap that can give better performance
characteristics than multimap with similar guarantees.
Here is a link to the docs on this submission:
http://groups.yahoo.com/group/boost/files/vec_multiset/vec_multiset.ht
m