Overload operator [] for a sparse vector

Question

I am trying to create a "sparse" vector class in C ++, for example:

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

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

However, I am having trouble overloading the index operator, [] . I have to overload the [] operator because I am passing objects from this class to the Boost function, which expects [] to work correctly.

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

However, the non-const version requires me to return the link, and that where I ran into the problem. If the value is only being read, I do not need (and do not want) to add anything to the map; but if it is written, I may need to enter a new entry on the card. The problem is that the overloaded [] does not know if the value is being read or written. It just returns the link.

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

Answer 1

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

You will need to check what the Boost function does with its template parameter, however - a custom conversion to V affects which conversion chains are possible, for example, by preventing the presence of more user-defined conversions in the same chain.

Answer 2

Do not let the non-constant operator & implementation return a link, but a proxy object. You can then implement the assignment operator of the proxy object to distinguish read accesses to the operator [] from write access.

Here are some code sketches to illustrate the idea. This approach is not very good, but good is C ++. C ++ programmers do not lose time competing in beauty contests (they will also have no chance) .; -)

 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 if this design sounds.

If you want to return a link, this means that class clients can save the result of calling operator[] in the link and read from / write to it at any other time. If you do not return the link and / or insert an element with each specific pointer, how can they do this? (Also, I get the feeling that a standard standard requires a standard STL container that provides operator[] so that this operator returns a link, but I'm not sure about that.)

You may be able to get around this by giving the proxy server operator V&() (which will create a record and assign a default value), but I'm not sure if in this case it will not just open another hole in the loop I have not thought.

std::map solves this problem by indicating that a non-constant version of this operator always inserts an element (and does not provide a const version at all).

Of course, you can always say that this is not a ready-made STL container, and operator[] does not return simple links that users can store. And maybe it's all right. I'm just curious.