c++ - 为哈希表 get 和 set 正确重载 [bracket] 运算符

Question

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

到目前为止，这个类是这样的:

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 的值。反过来，检查表中是否存在正确的键，如果不存在则抛出异常。