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:
> 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.
has ability to store sparse bit arrays
(and this library would really fit into Boost).
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk