2

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

到目前为止，这是该类的样子：

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 实现；即这应该抛出一个异常。我该怎么做呢？

4

2 回答 2

3

处理这种情况的常用方法是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作为其键。

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

于 2013-09-07T07:03:10.957 回答
2

当成员函数或运算符的等效const和非const重载可用时，在非const实例上调用该方法时选择非常量。仅当实例为或通过引用或指针访问时，const才会选择重载：constconst

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
}
于 2013-09-07T06:57:43.893 回答