在 C++ 中为泛型实现线性探测

Question

我想在 C++ 中实现哈希表的线性探测，但是键、值 pair 将是通用类型，例如：vector< pair< key,value> >（其中 key,value 是通用类型）。

现在，在线性探测中，如果一个单元格被占用，我们遍历向量直到找到一个空单元格，然后将新对放入该单元格。

问题是，在通用类型中，我如何能够检查特定单元格是否被占用？我不能使用这些条件：

if(key == '[=10=]')//As key is not of type string

或

if(key == 0)//As key is not of type int

那么，如何检查向量中的特定单元格是否为空？如果我误解了这个概念，请纠正我。

Answer 1

我认为你可以只检查向量的元素是否具有有意义的键和值：

if(vector[i] == std::pair<key, value>())
    //empty

或者，如果您只关心键

if(vector[i].first == key())
    //empty

此方法假定 key 类型的默认构造函数构造一个对象，该对象将被视为 "empty" 或 "invalid" 键。

Answer 2

您可以使用免费函数 isEmpty 来检查键类型是否为空。定义适用于大多数类型的模板化默认函数，并制作默认无法处理的特殊函数。

例如

template<typename T>
bool isEmpty(const T &t) {
    return !t;
}

bool isEmpty(const std::string &s) {
   return s.length() == 0;
}

bool isEmpty(double d) {
    return d < 0;
}

isEmpty(0); // true
isEmpty(1); // false
isEmpty(std::string()); // true
isEmpty(std::string("not empty")); // false
isEmpty(1.0); // false
isEmpty(-1.0); // true

您只需要专注于没有 operator ! 或需要不同逻辑进行检查的键类型

Answer 3

如果您不想排除哈希中包含 "default constructed" 元素的可能性，您可以构建一个并行数据结构，例如 std::bitset（如果您事先知道您的数据结构的最大大小）或 std::vector<bool>，在下文中我将其称为 has。如果 vector[i] 包含一个有效的、实际插入的元素，has[i] 将为真。

所以操作应该修改如下：

插入：继续扫描向量直到找到一个位置i使得has[i] == false
删除位置i的元素：设置has[i]为false

希望对您有所帮助

在 C++ 中为泛型实现线性探测

implement linear probing in c++ for a generic type

c++

templates

hashtable

linear-probing