Properly overloading [bracket] operator for hashtable get and set

Question

I am trying to implement a hashtable class. The problem I am facing atm is how to properly overload the square bracket operators so that getting the value at a key from the hashtable is distinguishable from setting a key to a value.

So far here is what the class looks like:

template <typename K, typename V>
class HashTable {
    typedef pair<K, V> KeyVal;
    avl_tree <KeyVal> **TABLE;
    unsigned TABLESIZE;
    
public:
    HashTable( const unsigned & );
    V& operator [] ( const K& ); //Setter
    const V& operator [](const K&) const; //Getter
    typedef unsigned (*hashtype)(const K&);
    static hashtype Hash;
    ~HashTable();
};

And this is the implementation of each overload of the brackets:

template <typename K, typename V>
V& HashTable<K, V>::operator [] ( const K& ret ) {
    unsigned index = HashTable<K, V>::Hash(ret) % TABLESIZE;
    avl_tree <KeyVal> *ptr = AVL_TREE::find(TABLE[index], KeyVal(ret, 0));
    if ( ptr == None ) ptr = (TABLE[index] = AVL_TREE::insert(TABLE[index], KeyVal(ret, 0)));
    return ptr->data.second;
}

template <typename K, typename V>
const V& HashTable<K, V>::operator [](const K& ret) const {
    avl_tree <KeyVal> *ptr = AVL_TREE::find(TABLE[HashTable<K, V>::Hash(ret) % TABLESIZE], KeyVal(ret, 0));
    if (ptr == None) throw "Exception: [KeyError] Key not found exception.";
    return ptr->data.second;
}

Now if I do:

cout << table["hash"] << "\n"; //table declared as type HashTable<std::string, int>

I get an output of 0, but I want it to use the getter implementation of the overloaded square brackets; i.e. this should throw an exception. How do I do this?

Answer 1

The usual way to handle this situation is to have operator[] return a proxy.

Then, for the proxy overload operator T approximately as you've done your const overload above. Overload operator= about like your non-const version.

template <typename K, typename V>
class HashTable {
    typedef pair<K, V> KeyVal;
    avl_tree <KeyVal> **TABLE;
    unsigned TABLESIZE;

    template <class K, class V>
    class proxy { 
        HashTable<K, V> &h;
        K key;
    public:
        proxy(HashTable<K, V> &h, K key) : h(h), key(key) {}

        operator V() const { 
            auto pos = h.find(key);
            if (pos) return *pos;
            else throw not_present();
        }

        proxy &operator=(V const &value) {
            h.set(key, value);
            return *this;
        }
    };
public:
    HashTable( const unsigned & );

    proxy operator [] ( const K& k) { return proxy(*this, k); }
    typedef unsigned (*hashtype)(const K&);
    static hashtype Hash;
    ~HashTable();
};

You basically have two cases when you use this:

some_hash_table[some_key] = some_value;

value_type v = some_hash_table[some_key];

In both cases, some_hash_table[some_key] returns an instance of proxy. In the first case, you're assigning to the proxy object, so that invokes the proxy's operator=, passing it some_value, so some_value gets added to the table with key as its key.

In the second case, you're trying to assign an object of type proxy to a variable of type value_type. Obviously that can't be assigned directly -- but proxy::operator V returns an object of the value type for the underlying Hashtable -- so the compiler invokes that to produce a value that can be assigned to v. That, in turn, checks for the presence of the proper key in the table, and throws an exception if its not present.

Answer 2

When equivalent const and non-const overloads of a member function or operator are available, the non-const is chosen when the method is called on a non-const instance. The const overload will only be picked if the instance is const, or if it is accessed via a const reference or pointer:

struct Foo
{
  void foo() {}
  void foo() const {}
};

void bar(const Foo& f) { f.foo();}
void baz(const Foo* f) { f->foo(); }

int main()
{
  Foo f;
  f.foo(); // non-const overload chosen
  bar(f);  // const overload chosen
  bar(&f); // const overload chosen

  const Foo cf; // const instance
  cf.foo();     // const overload chosen

  const Foo& rf = f; // const reference
  rf.foo();          // const overload chosen
}