c++ - 将哈希表重载为 vector 的 [] 运算符

Question

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

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

例如，如果我想向 vector 添加一个项目，我可以编写如下内容:

     hashTable[string1] = newString;

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

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

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

    //Return a reference to a vector to update then reassign?

        vector& HashClass::operator[](const string index)
        {
           assert(size >= 0 && size < maxSize); 
           Hash(key);
           return hashTable[index];     
        }

我认为我最坚持的想法是有一个稍后需要分配的 vector 返回。作为用户，我会发现这很糟糕。

Answer 1

这个问题与另一个问题密切相关:行为是什么 当你访问一个不存在的值时，你想要 任务？换句话说，当您编写时您希望发生什么:

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

表中不存在

和 string ？

有两种可能的方法:您可以将其视为错误，并且 抛出异常、中止或类似的情况；或者你可以返回 某种默认值，使用默认构造函数构建，或者由 早些时候的客户。

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

在许多用例中，第一种方法更好(也许带有 包含函数，因此您可以预先测试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 函数 向哈希表中插入任何内容，这样表就不会填满 所有未命中，并且您可以在 const 上重载 operator[]，因此 您也可以在 const 哈希表上使用它。而且，它不 要求值类型有一个默认构造函数。

与中使用的解决方案相比，它确实有一个缺点 标准;由于您无法重载operator.，因此您无法创建代理 表现得像一个引用，比如:

hashTable[string].someFunction();

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

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

(不要被隐式转换为引用所误导。 表达式中的 a 不会考虑隐式转换 a.b。)