Boost logo

Boost :

From: Pavel Vozenilek (pavel_vozenilek_at_[hidden])
Date: 2006-04-26 16:02:17

"Spencer Collyer" wrote:

> It is a policy-based sparse array class.
> To try and make it as flexible as possible, I've implemented it using
> four policies, as follows:
> storage:
> This allows the user to specify how the underlying storage for the
> sparse_array is handled. Currently I only have one policy defined
> (std_map, which unsurprisingly uses a std::map for the storage), but
> policies to use hash maps or something akin to Loki's AssocVector could
> be easily defined.

The storage can get better:

- double-array structure provides O(1) retrieving time,
requires more-less O(N) space where N = number
of nonzero elements (with /no/ overhead due to pointers),
 deletion and insertions are bounded.

It is described in IEEE Transaction of SW Engineering,
vol 15, No9, Sep 1989 by Jun-Ichi Aoe.
An implementation seems to exist on

It is also possible to come up with quite a few ad-hoc
storages fitting this or that domain and faring better than std::map.

BitMagic library
has ability to store sparse bit arrays
(and this library would really fit into Boost).


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