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
.)