2

我正在使用 C++ 编写一个简单的哈希表。我有插入、删除和搜索指定键的哈希表的方法。我知道 C++ map STL 容器可以处理我的情况，但我有点想编写自己的代码作为教育练习。

基本上我有一个哈希表，它将采用单个字符串并将其映射到其他字符串的向量。这在方法中很容易做到，因为调用 .Add() 或 .Delete() 将按预期运行。但是，我想为能够对向量执行这些操作的类创建一个重载的 [] 运算符。

例如，如果我想在向量中添加一个项目，我可以这样写：

     hashTable[string1] = newString;

这会将新字符串设置为我的向量的成员。删除和搜索也是如此。

    hashTable[string1] = "";
    cout << hashTable[string1] << endl;

我的主要问题是我不知道如何重载[]运算符来获得此功能。我现在已经编写了这个函数。它适用于基本的 1 对 1 字符串匹配，但不适用于字符串到矢量匹配。

    //返回对要更新的向量的引用然后重新分配？

        vector& HashClass::operator[](const string index)
        {
           断言（尺寸 >= 0 && 尺寸 < 最大尺寸）；
           散列键）;
           返回哈希表[索引]；     
        }

我认为我最坚持的想法是稍后需要分配一个向量返回。作为用户，我会觉得这个很笨拙。

4

2 回答 2

2

这个问题与另一个问题密切相关：当你访问一个不存在的值而不是赋值时，你想要什么行为？换句话说，当你写的时候你想发生什么：

std::cout << hashTable[string] << std::endl;

并且string不存在于表中？

有两种可能的方法：您可以将其视为错误，然后抛出异常、中止或类似的东西；或者您可以返回某种默认值，使用默认构造函数构建，或者由客户端早些时候提供。

标准 map 和 unordered_map 采用第二种方法，使用默认构造函数构造一个新值。这允许一个非常简单的解决方案：如果operator[]不存在，则插入它，并使用默认值对其进行初始化。然后返回对它的引用； hashTable[string] = newString;通过对已经存在的值的引用进行分配。

在许多用例中，第一种方法会更可取（可能使用 contains函数，因此您可以预先测试它是否operator[] 会找到某些东西）。要实现第一种方法，您必须首先为每种访问类型实现特定功能：

template <typename Key, typename Value>
class HashTable
{
public:
    Value* get( Key const& key ) const;
    void set( Key const& key, Value const& value );
};

（我通常会公开这些信息；没有理由禁止客户使用它们。）

然后，您定义operator[]返回一个代理，如下所示：

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

因此，当你写：

hashTable[key] = newString;

，代理operator=将调用hashTable.put( key, newString )；但是，在其他情况下，它将调用代理上的隐式类型转换，该代理调用hashTable.get( key ).

在某些情况下，即使您希望返回默认值，最好使用此解决方案：该get函数不需要向哈希表中插入任何内容，因此该表不会填满所有未命中的值，你可以重载operator[]on ，所以你也可以在哈希表const上使用它。const此外，它不需要值类型具有默认构造函数。

相对于标准中使用的解决方案，它确实有一个缺点。因为你不能重载operator.，你不能让代理表现得像一个引用，比如：

hashTable[string].someFunction();

不工作。一种解决方法是operator->在代理中重载，但这会导致语法有些不自然：

hashTable[string]->someFunction();  //  But the hash table contains
                                    //  values, not pointers!!!

a（不要被隐式转换为引用所误导。在表达式中 不会考虑隐式转换a.b。）

于 2012-09-28T12:53:29.817 回答
0

在 C++ 中，[]对关联容器的访问通常具有以下语义：默认构造一个映射类型的对象，用键插入它，并返回对插入的映射对象的引用。

所以你operator[]将被实施为：

    string& HashClass::operator[](const string index)
    {
       assert(size >= 0 && size < maxSize); 
       Hash(key);
       vector &v = hashTable[index];     
       if (index in v) {
          ...
       } else {
          v.push_back(string());
          return v.back();
       }
    }
于 2012-09-28T11:48:39.203 回答