Overloaded [] operator for hash table to a vector

Question

I am working on a simple hash table in C++. I have methods to insert, delete, and search the hash table for the specified key. I know that the C++ map STL container can handle my situation, but I would kind of like to code my own as an educational exercise.

Basically I have a hash table that will take a single string and map it to a vector of other strings. This is easy to do in a method because calling a .Add() or .Delete() will behave as expected. I would however like to create an overloaded [] operator to the class that is able to do these operations on the vector.

For example, if I want to add an item to the vector I can write something like this:

     hashTable[string1] = newString;

This will set the new string as a member of my vector. The same can be said for delete and search.

    hashTable[string1] = "";
    cout << hashTable[string1] << endl;

My major problem is that I do not know how to overload the [] operator to gain this functionality. I have this function coded up right now. It works on a basic 1 to 1 string match, but not on a string to vector match.

    //Return a reference to a vector to update then reassign?

        vector& HashClass::operator[](const string index)
        {
           assert(size >= 0 && size < maxSize); 
           Hash(key);
           return hashTable[index];     
        }

I think I'm most stuck on the idea of having a vector return that later needs to be assigned. As the user, I would find this kludgy.

I personally didn't understand where the problem is... (could just be me though) — Luchian Grigore
Do you want 2 different return types? One overloaded operator[] returns a string and the other overload returns a vector<string>? — sashang
From what you write it is not clear whether you have one or many strings for each key. — Nicola Musatti

James Kanze James Kanze · Accepted Answer · 2012-09-28T12:53:29

This question is closely related to another question: what behavior do you want when you access a non-existant value other than in an assignment? In other words, what do you want to happen when you write:

std::cout << hashTable[string] << std::endl;

and string is not present in the table?

There are two possible approaches: you can consider it an error, and throw an exception, or abort, or something similar; or you can return some sort of default, built with the default constructor, or provided by the client earlier.

The standard map and unordered_map take the second approach, using the default constructor to construct a new value. This allows a very simple solution: if operator[] isn't present, you insert it, initializing it with the default value. Then you return a reference to it; hashTable[string] = newString; assigns through the reference to an already existing value.

In many use cases, the first approach will be preferable (perhaps with a contains function, so you can test up front whether the operator[] will find something or not). To implement the first approach, you must first implement specific functions for each type of access:

template <typename Key, typename Value>
class HashTable
{
public:
    Value* get( Key const& key ) const;
    void set( Key const& key, Value const& value );
};

(I generally make these public; there's no reason to forbid their use by a client.)

Then, you define operator[] to return a proxy, as follows:

template <typename Key, typename Value>
class HashTable
{
public:
    class Proxy
    {
        HashTable* myOwner;
        Key myKey;
    public:
        Proxy( HashTable* owner, Key const& key )
            : myOwner( owner )
            , myKey( key )
        {
        }

        operator Value const&() const
        {
            Value const* result = myOwner->get( myKey );
            if ( result == NULL ) {
                //  Desired error behavior here...
            }
            return *result;
        }

        Proxy const& operator==( Value const& value ) const
        {
            myOwner->set( myKey, value );
            return *this;
        }
    };

    Value* get( Key const& key ) const;
    void set( Key const& key, Value const& value );

    Proxy operator[]( Key const& key )
    {
        return Proxy( this, key );
    }
};

Thus, when you write:

hashTable[key] = newString;

, the proxy's operator= will call hashTable.put( key, newString ); in other contexts, however, it will call the implicit type conversion on the proxy, which calls hashTable.get( key ).

In some cases, even if you desire to return a default value, it may be preferable to use this solution: the get function is not required to insert anything into the hash table, so the table doesn't fill up with all of the misses, and you can overload the operator[] on const, so you can use it on a const hash table as well. Also, it doesn't require the value type to have a default constructor.

It does have one disadvantage with respect to the solution used in the standard; since you can't overload operator., you can't make the proxy behave like a reference, and things like:

hashTable[string].someFunction();

don't work. A work-around is to overload operator-> in the proxy, but this leads to a somewhat unnatural syntax:

hashTable[string]->someFunction();  //  But the hash table contains
                                    //  values, not pointers!!!

(Don't be mislead by the implicit conversion to a reference. An implicit conversion will not be considered for a in an expression a.b.)

Overloaded [] operator for hash table to a vector

2 Answers