Proposal: Sorted Vector Container

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.

Why:
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
situation
a sorted vector can offer superior performance to the standard tree
implementation
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
std::multiset
to make it easy to convert code that uses multiset to a faster
implementation
when a setup/lookup pattern is followed.

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

1. Because it uses a vector as the underlying container to hold data,
individual
elements may get shifted around in memory.  If you need pointer or reference
validity throughout the lifetime of the container, use std::multiset.
Vec_multiset's
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
container
suffers from the same exception safety issues a std::vector.

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

Documentation:
http://groups.yahoo.com/group/boost/files/vec_multiset/vec_multiset.htm

Code:
http://groups.yahoo.com/group/boost/files/vec_multiset/vec_multiset.zip