Overloading operator [] for a sparse vector

Question

I'm trying to create a "sparse" vector class in C++, like so:

template<typename V, V Default>
class SparseVector {
    ...
}

Internally, it will be represented by an std::map<int, V> (where V is the type of value stored). If an element is not present in the map, we will pretend that it is equal to the value Default from the template argument.

However, I'm having trouble overloading the subscript operator, []. I must overload the [] operator, because I'm passing objects from this class into a Boost function that expects [] to work correctly.

The const version is simple enough: check whether the index is in the map, return its value if so, or Default otherwise.

However, the non-const version requires me to return a reference, and that's where I run into trouble. If the value is only being read, I do not need (nor want) to add anything to the map; but if it's being written, I possibly need to put a new entry into the map. The problem is that the overloaded [] does not know whether a value is being read or written. It merely returns a reference.

Is there any way to solve this problem? Or perhaps to work around it?

Answer 1

There may be some very simple trick, but otherwise I think operator[] only has to return something which can be assigned from V (and converted to V), not necessarily a V&. So I think you need to return some object with an overloaded operator=(const V&), which creates the entry in your sparse container.

You will have to check what the Boost function does with its template parameter, though - a user-defined conversion to V affects what conversion chains are possible, for example by preventing there being any more user-defined conversions in the same chain.

Answer 2

Don't let the non-const operator& implementation return a reference, but a proxy object. You can then implement the assignment operator of the proxy object to distinguish read accesses to operator[] from write accesses.

Here's some code sketch to illustrate the idea. This approach is not pretty, but well - this is C++. C++ programmers don't waste time competing in beauty contests (they wouldn't stand a chance either). ;-)

template <typename V, V Default>
ProxyObject SparseVector::operator[]( int i ) {
   // At this point, we don't know whether operator[] was called, so we return
   // a proxy object and defer the decision until later
   return ProxyObject<V, Default>( this, i );
}

template <typename V, V Default>
class ProxyObject {
    ProxyObject( SparseVector<V, Default> *v, int idx );
    ProxyObject<V, Default> &operator=( const V &v ) {
      // If we get here, we know that operator[] was called to perform a write access,
      // so we can insert an item in the vector if needed
    }

    operator V() {
      // If we get here, we know that operator[] was called to perform a read access,
      // so we can simply return the existing object
    }
};