Boost logo

Boost :

From: Corwin Joy (cjoy_at_[hidden])
Date: 2001-11-20 03:09:23

Michael Gradman and myself have uploaded a new contaier to the
boost files area in a folder called vec_multiset.

What it is:
A wrapper that holds a sorted vector in such a way as to make it look
like a std::multiset.

It has been observed by Scott Meyers ("Effective STL") and others that in
many situations
when dealing with sorted data one has a "setup" phase followed by a
"lookup" phase where items are retrieved from the container. In this
a sorted vector can offer superior performance to the standard tree
used by multiset both in terms of memory and speed. We have taken the step
of wrapping a sorted vector with an interface very similar to a
to make it easy to convert code that uses multiset to a faster
when a setup/lookup pattern is followed.

By using some fancy footwork we were able to preserve multiset requirements
like iterator invariants after insertions/deletions and several other
making for quite a nice container. There are really only two major
on this container versus a true multiset:

1. Because it uses a vector as the underlying container to hold data,
elements may get shifted around in memory. If you need pointer or reference
validity throughout the lifetime of the container, use std::multiset.
underlying container can shift the data elements around in memory. However,
if you write your code in a more modern fashion to use iterators rather than
pointers, you can still use vec_multiset.

2. Exception safety. Because it uses vector to hold the data elements this
suffers from the same exception safety issues a std::vector.

More documentation about how we built this container to preserve interator
and other details can be found at:



Boost list run by bdawes at, gregod at, cpdaniel at, john at