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