Re: [boost] Possible class submission: Sparse Array

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
http://linux.thai.net/~thep/datrie/datrie.html

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
http://bmagic.sourceforge.net/
has ability to store sparse bit arrays
(and this library would really fit into Boost).

/Pavel