Re: [boost] Possible class submission: Sparse Array

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

On Wed, 26 Apr 2006 22:05:58 +0200, Toon Knapen wrote:

> > iterator:
> > This determines how the limits on iterators are defined. So it is
> > possible to specify that iteration should be over the whole range of
> > the sparse_array, or that it should only be from the lowest assigned
> > subscript to the highest assigned subscript.
> 
> what syntax do you use exactly for these different iterators?

I think you may have misunderstood me (my fault, I probably didn't express myself adequately).

The iterators behave exactly the same as you would find on a std::vector, except that the policy defines where the start and end subscripts are obtained from.

Thus, one of the polices I've defined (whole_range) will always iterate from the lowest allowed subscript to the highest allowed subscript without caring whether values have been assigned to those elements or not, while another (filled_range) will iterate from the lowest subscript that has had an element assigned (the low-water-mark) to the highest such subscript (the high-water-mark).

As you define the iterator policy when you create the sparse_array, these are the limits that all iterators over that sparse_array will have.

Note, however, that it is always possible to get the minimum and maximum allowed subscripts and the low- and high-water-marks from a sparse_array, so if you need to process a different range of subscripts you can do so.

> > 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.
> 
> can you also separate the structure from the values. I.e is it possible 
> to first define the structure and then afterwards assign the values to 
> the corresponding positions? Does the interface also allow me to share 
> the structure-information between multiple sparse vectors?

In principle, your storage policy class can do anything you want it to as long as it supplies the interface the sparse_array is looking for. Bear in mind that the storage policy is inherited by sparse_array, not contained by it.

> What a coincidence, I just started discussing the design of a 
> sparse-vector on the glas mailing list 
> (http://lists.boost.org/mailman/listinfo.cgi/glas). One of the
> questions that pops up: what should be the return-type of
> operator[](size_type) ?

I have two versions of this function in my sparse_array class:

reference operator[](size_type sub);
const_reference operator[](size_type sub) const;

The one that returns a non-const reference has to handle the case where there is no element existing at the given subscript. Because it can be used in expressions like

  sa[sub]++;

I opted to always create a default-valued element if one did not exist. After reading Meyers' _More Effective C++_ item 30 on proxy classes, I decided not to go down the proxy root as we can't know in advance what our stored values are.

The function that returns a const_reference has an easier time if there is no element at the subscript given, as it can just return a const& to the default value, without having to store anything in the sparse_array.

Because we are sometimes forced to create default values in the array there is a 'normalise()' function which goes through and removes such values. Note also that assignment and merging to sparse_arrays does not copy default values if the values policy says not to.

Spencer

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