Re: [boost] Possible class submission: Sparse Array

From: Spencer Collyer (spencer_at_[hidden])
Date: 2006-04-28 03:10:58

On Thu, 27 Apr 2006 22:05:44 +0200, Toon Knapen wrote:
> Spencer Collyer wrote:
> 
> [snip]
> 
> > 
> > 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.
> > 
> 
> 
> 
> but this means also that if I have a sparse-vector and I loop over all 
> indices to print the corresponding values on the screen (doing <code> 
> for( i=0 ; i < size ; ++i ) std::cout << my_spare_vector[i] </code>), I 
> will totally fill up the sparse structure!

If it is a non-const sparse_array then that is true. If it is a const
sparse_array then we don't add entries to it when using operator[](),
because you cannot treat such a return value as an lvalue, so we can just
return a const_reference to a default value.

The problem arises when using the non-const version of operator[]()
(which will be used if the sparse_array is non-const). As explained in
the Meyers item I reference above, it is possible to distinguish lvalue
and rvalue references using proxy classes, so operator[]() could return a
proxy. However, as that item further goes on to explain, proxies have
limitations in cases such as calling member functions of the proxied
type, or even just the increment example I gave above.

I would love to hear any ideas that can allow me to change my class so I
_don't_ have to always add an element with the default type when using
non-const operator[](), but so far I've not come across anything that
lets me do it for any general data type whose interface cannot be known
at coding time.

My class includes a couple of functions to help get around this problem.
First, as mentioned above, there is a normalise() function that goes
through and deletes any elements that have the default value. There is
also an active_subscripts() function that returns to you just the
subscripts of the elements that have been set.

Spencer

-- 
<<< Eagles may soar, but weasels don't get sucked into jet engines >>>
7:48am up 40 days 19:21, 23 users, load average: 0.00, 0.01, 0.08
Registered Linux User #232457 | LFS ID 11703