"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