实现一个返回项目引用的搜索函数，C++

Question

我正在制作一个简单的哈希表类，我想实现一个搜索函数来搜索表并返回对项目的引用（例如，我需要一个引用来进一步删除 deleteItem 函数中的项目）。问题是该函数需要让调用者知道该项目是否不存在。

这是表定义：

std::list<std::pair<int, std::string>> table[size];

我尝试使用 std::Optional:

auto HashTable::searchItem(int hashValue, int key)
{
    auto& cell = table[hashValue];
    
    for (auto it = begin(cell); it != end(cell); it++)
    {
        if (it->first == key)
        {
            return std::optional<std::pair<int, std::string>&>(*it);
        }
    }
    return std::nullopt;
}

但由于某种原因这不起作用，看起来可选不支持引用。

然后我尝试使用智能指针，但这似乎也不起作用，因为我会创建对象的副本来创建智能指针。然后我决定抛出一个异常：

auto& HashTable::searchItem(int hashValue, int key)
{
    auto& cell = table[hashValue];
    
    for (auto it = begin(cell); it != end(cell); it++)
    {
        if (it->first == key)
        {
            return *it;
        }
    }
    throw not_found{};
}

但是这不是很有效，因为我每次插入项目时都会使用这个函数来检查重复项。

这个功能的正确实现方法是什么？

Answer 1

但由于某种原因这不起作用，看起来可选不支持引用。

没错，

std::optional

不支持引用。这是一个长期存在的问题，因为对于

std::optional<T&>::operator=

是否应该将分配传递给

T

，还是应该重新绑定引用存在分歧。

指针与可选引用非常相似，允许以下解决方案：

std::pair<int, std::string>* HashTable::searchItem(int hashValue, int key)
{
    auto& cell = table[hashValue];
    
    for (auto it = begin(cell); it != end(cell); it++)
    {
        if (it->first == key)
        {
            return &*it; // or return it.operator->();
        }
    }
    return nullptr;
}

为此目的使用原始指针是现代且惯用的。例如，

std::get_if

返回原始指针。