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
    }
};

Answer 3

I wonder whether this design is sound.

If you want to return a reference, that means that clients of the class can store the result of calling operator[] in a reference, and read from/write to it at any later time. If you do not return a reference, and/or do not insert an element every time a specific index is addressed, how could they do this? (Also, I've got the feeling that the standard requires a proper STL container providing operator[] to have that operator return a reference, but I'm not sure of that.)

You might be able to circumvent that by giving your proxy also an operator V&() (which would create the entry and assign the default value), but I'm not sure this wouldn't just open another loop hole in some case I hadn't thought of yet.

std::map solves this problem by specifying that the non-const version of that operator always inserts an element (and not providing a const version at all).

Of course, you can always say this is not an off-the-shelf STL container, and operator[] does not return plain references users can store. And maybe that's OK. I just wonder.