Overloading [] in C++ to return lvalue

Question

I'm writing a simple hash map class:

template <class K, class V> class HashMap;

The implementation is very orthodox: I have a heap array which doubles in size when it grows large. The array holds small vectors of key/value pairs.

Vector<Pair<K, V> > *buckets;

I would like to overload the subscript operator in such a way that code like this will work:

HashMap<int, int> m;
m[0] = 10; m[0] = 20;
m[2] = m[1] = m[0];

In particular,

• For m[k] = v where m does not contain k, I'd like a new entry to be added.
• For m[k] = v where m does contain k, I'd like the old value to be replaced.
• In both of these cases, I'd like the assignment to return v.

Presumably the code will look something like

V& operator[](K &key)
{
    if (contains(key))
    {
        // the easy case
        // return a reference to the associated value
    }
    else
    {
        Vector<Pair<K, V> > *buck = buckets + hash(k) % num_buckets;
        // unfinished
    }
}

How should I handle the case where the key is not found? I would prefer to avoid copying values to the heap if I can.

I suppose I could make a helper class which overloads both the assignment operator and a cast to V, but surely there is a simpler solution?

Edit: I didn't realize that std::map required that the value type have a zero argument constructor. I guess I will just default-construct a value as well.

Answer 1

How should I handle the case where the key is not found?

Insert a new element with that key and return a reference to the value of that new element. Effectively, your pseudocode becomes something equivalent to:

if (!contains(key))
    insert(Pair<K, V>(key, V()));
return reference_to_the_element_with_that_key;

This is exactly what your requirement is, too. You said "For m[k] = v where m does not contain k, I'd like a new entry to be added."

Answer 2

How should I handle the case where the key is not found?

std::map creates a new object, and inserts it into the map, and returns its reference. You can also do the same.

Alternatively, you can throw an exception KeyNotFoundException like the way .NET map throws. Of course, you've to define KeyNotFoundException yourself, possibly deriving from std::runtime_exception.

By the way, as a general rule, always implement operator[] in pair as:

V &operator[](const K &key);
const V &operator[](const K &key) const;

Just for the sake for const-correctness. However, if you decide to create a new object and insert it into the map, when the key is not found, then this rule is not applicable here, as const version wouldn't make sense in this situation.

See this FAQ:

• What's the deal with "const-overloading"?

Answer 3

It sounds like what you want is a "smart reference", which you cannot generically implement in C++ because you cannot overload the dot operator (among other reasons).

In other words, instead of returning a reference to a V, you would return a "smart reference" to a V, which would contain a pointer to V. That smart reference would implement operator=(const V &v) as this->p = new V(v), which only requires a copy constructor (not a zero-argument constructor).

The problem is that the smart reference would have to behave like an actual reference in all other ways. I do not believe you can implement this in C++.

One not-quite-solution is to have your constructor take a "default" instance of V to use for initializing new entries. And it could default to V().

Like this:

template<class K, class V> class HashMap {
private:
    V default_val;
public:
    HashMap(const V& def = V()) : default_val(def) {
        ...
    }
...
};

When V lacks a zero-argument constructor, HashMap h will not compile; the user will need to provide a V object whose value will be returned when a key is accessed for the first time.

This assumes V has a copy constructor, of course. But from your examples, that seems like a requirement anyway.

Answer 4

The simple solution is to do as std::map does: construct a new entry, using the default constructor of the value type. This has two drawbacks: you won't be able to use [] on a HashMap const, and you can't instantiate HashMap with a value type which doesn't have a default constructor. The first is more or less implicit in the specification, which says that [] may modify the map. There are several solutions for the second: the simplest is probably to pass an instance of a "default" value to the constructor, which saves it, and uses it to copy construct the new instance, e.g.:

template <typename Key, typename Value>
class HashMap
{
    //  ...
    Value m_defaultValue;
public:
    HashMap( ..., Value const& defaultValue = Value() )
        : ... , m_defaultValue( defaultValue )...

    Value& operator[]( Key& key )
    {
        //  ...
        //  not found
        insert( key, m_defaultValue );
        //  return reference to newly inserted value.
    }
};

Alternatively, you can have operator[] return a proxy, something like:

template <typename Key, typename Value>
class HashMap::Helper  //  Member class of HashMap
{
    HashMap* m_owner;
    Key m_key;
public:
    operator Value&() const
    {
        if ( ! m_owner->contains( m_key ) )
            m_owner->createEntryWithDefaultValue( m_key );
        return m_owner->getValue( m_key );
    }
    Helper& operator=( Value const& newValue ) const
    {
        m_owner->insert( m_key, newValue );
        return *this;
    }
};

Note that you'll still need the default value for the case where someone writes:

v = m[x];

and x isn't present in the map. And that things like:

m[x].f();

won't work. You can only copy the entire value out or assign to it. (Given this, I'd rather prefer the first solution in this case. There are other cases, however, where the proxy is the only solution, and we have to live with it.)