Re: [boost] Possible library submissions: fuzzy logic library, new container

From: Spencer Collyer (spencer_at_[hidden])
Date: 2008-08-01 15:09:20

On Wed, 25 Jun 2008 16:45:23 -0500, Alex Shafir wrote:

> The other idea is the “sparse array” container. Working for securities
> trading industry I used it innumerable number of times. It is useful
> in situations where there is a set of entities identified by
> integer(unsigned) numbers. Most often the numbers are identity keys
> in a database, a protocol field ids, etc. The potential range of the
> numbers makes it impractical to use a C++ array or the STL <vector>.
> On the other hand the average percentage of the keys that are really
> used in an application relative to the potential range is often less
> then 5% and there are huge holes of unused keys between zero and
> max(used key). The data elements or pointers to objects are kept in a
> structure similar to a balanced B-tree. Elements are directly
> accessed by an index operator. Access involves only a few arithmetic
> and redirection operations. When storing a new element that is
> outside of the range provided by exiting data structure the structure
> bilds itself up extending the indes range enough to accommodate a new
> index value. Existing data are never physically moved like in the STL
> vector. So, all references/pointers/iterators referencing existing
> elements are never invalidated.

Catching up on my emails, I've just seen this one. I also have a sparse
array implementation I've been thinking about introducing to Boost (I
did send a message to the boost mailing list some time ago, but various
commitments since then have prevented me from going forward with it).
It's a policy-based sparse array implementation which allows for
specification of how bounds are handled, how iterators behave, how
default values are handled, and the underlying storage mechanism. I've
tried to make it as flexible as possible within the bounds of those
policies. If there is interest I could try tidying up the documentation
and sorting out a Boost submission.

Spencer