Boost logo

Boost :

From: David Abrahams (dave_at_[hidden])
Date: 2008-06-26 12:58:55

Alex Shafir wrote:

> The other idea is the “sparse array” container. Working for securities
> trading industry I used it innumerable number of times. It is useful in
> situations where there is a set of entities identified by
> integer(unsigned) numbers. Most often the numbers are identity keys in a
> database, a protocol field ids, etc. The potential range of the numbers
> makes it impractical to use a C++ array or the STL <vector>. On the
> other hand the average percentage of the keys that are really used in an
> application relative to the potential range is often less then 5% and
> there are huge holes of unused keys between zero and max(used key). The
> data elements or pointers to objects are kept in a structure similar to
> a balanced B-tree. Elements are directly accessed by an index operator.
> Access involves only a few arithmetic and redirection operations. When
> storing a new element that is outside of the range provided by exiting
> data structure the structure bilds itself up extending the indes range
> enough to accommodate a new index value. Existing data are never
> physically moved like in the STL vector. So, all
> references/pointers/iterators referencing existing elements are never
> invalidated.

Very interesting, but how is it substantially different from std::map?

Dave Abrahams
BoostPro Computing

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