Re: [boost] Possible class submission: Sparse Array

From: Spencer Collyer (spencer_at_[hidden])
Date: 2006-04-27 03:21:29

On Wed, 26 Apr 2006 22:02:17 +0200, Pavel Vozenilek wrote:
> 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

Pavel,

Thanks for the pointers to these. Because the storage is specified using
a policy there is nothing to stop a user specifying a different storage
policy if they have specific needs. I've only developed a policy for
std::map because it is available to everyone, and it is quick enough for
my needs at present.

I'll need to look closer at the double-array structure. Do you think it
would be a good idea to develop a Boost implementation of it to submit
with my sparse_array class, as another storage policy? I could try and do
that if you think it would be a good idea. Mind you, it looks (at a first
quick glance) like it could be a useful class on its own, so maybe a
separate submission would be appropriate?

Thanks for the pointer to the BitMagic stuff. I'll have a look at it
later.

Spencer

-- 
<<< Eagles may soar, but weasels don't get sucked into jet engines >>>
8:12am up 39 days 19:45, 21 users, load average: 0.00, 0.00, 0.07
Registered Linux User #232457 | LFS ID 11703