0

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

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

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

if(key == '\0')//As key is not of type string

或者

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

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

4

3 回答 3

2

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

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

或者，如果您只关心键

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

这种方法假定key类型的默认构造函数构造一个对象，该对象将被视为“空”或“无效”键。

于 2016-10-10T08:10:50.773 回答
0

如果您不想排除在哈希中包含“默认构造”元素的可能性，您可以构建并行数据结构，例如 a std::bitset（如果您事先知道数据结构的最大大小）或 a std::vector<bool>，即在下面我会打电话has。has[i]如果vector[i]包含一个有效的、实际插入的元素，则为真。

所以操作应该修改如下：

  • 插入：继续扫描向量，直到找到i这样的位置has[i] == false
  • 删除位置 i 的元素：设置has[i]为false

希望这可以帮助

于 2016-10-10T10:16:00.870 回答
0

您可以使用免费功能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 !或需要不同逻辑进行检查的密钥类型

于 2016-10-10T09:03:32.787 回答