c++ - 为哈希表获取和设置正确重载 [bracket] 运算符

Question

我正在尝试实现一个哈希表类。我面临的问题是如何正确重载方括号运算符，以便从哈希表中获取键处的值与将键设置为值区分开来。

到目前为止，该类的外观如下:

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();
};

这是每个括号重载的实现:

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;
}

现在如果我这样做:

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

我得到的输出为 0，但我希望它使用重载方括号的 getter 实现；即这应该引发异常。我该怎么做？

Answer 1

处理这种情况的通常方法是让 operator[] 返回代理。

然后，对于代理重载operator T，大约与您在上面完成const重载一样。重载 operator= 就像您的非常量版本一样。

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();
};

使用它时基本上有两种情况:

some_hash_table[some_key] = some_value;

value_type v = some_hash_table[some_key];

在这两种情况下，some_hash_table[some_key]都会返回proxy的实例。在第一种情况下，您将分配给代理对象，以便调用代理的operator=，并向其传递some_value，因此some_value 被添加到表中，并以 key 作为键。

在第二种情况下，您尝试将 proxy 类型的对象分配给 value_type 类型的变量。显然不能直接赋值 - 但 proxy::operator V 返回底层 Hashtable 的值类型的对象 - 因此编译器调用它来生成可以分配给v的值。反过来，它会检查表中是否存在正确的键，如果不存在则抛出异常。