c++ - 如何创建迭代器的 QSet

Question

我想做的是:

#include <QVector>
#include <QLinkedList>
#include <QSet>

class MyType
{
//...
};

int main(int argc, char** argv)
{
    QVector<MyType> vector;
    QSet<QVector<MyType>::iterator> a;
    a.insert(vector.begin());          // This is fine

    QLinkedList<MyType> linkedList;
    QSet<QLinkedList<MyType>::iterator> b;
    b.insert(linkedList.begin());      // This does not compile

    return 0;
}

编译器信息是:

error: no matching function for call to 'qHash(const QLinkedList<MyType>::iterator&)'

我知道，前三行编译的原因是 QVector , 迭代器定义为 typedef T* iterator;但对于 QLinkedList它是一种自定义类型。

我发现，QSet模板类是根据哈希表实现的。 显然可以为指针计算散列函数，但不能为自定义类型计算。

请你告诉我，如何重载 qHash我的程序编译的功能？我已经阅读了一些关于哈希表工作原理的基本信息，但我对这个主题缺乏信心。

我试图了解 QLinkedList<T>::iterator 的内部工作原理.它似乎与 QVector<T>::iterator 非常相似.它只是持有指向链表中节点的指针，而不是指向项目本身的指针。

class iterator
{
public:
   ...
   Node *i;
   ...
};

所以我尝试以这种方式定义函数:

uint qHash(QLinkedList<MyType>::iterator it)
{
    return qHash(it.i);
}

程序已编译，但我对我的解决方案没有信心。我应该如何正确地重载 qHash功能？

Answer 1

你已经做得很好了。哈希函数的基本规则是:

1. 如果 x = y 则 hash(x) = hash(y)。
2. 如果 x != y 则 hash(x) != hash(y)(尽可能频繁)。这不是一个严格的规则，但遵循得越好，哈希表的性能就越好。理想情况下，输出将随机出现。

你的方法是可行的，因为如果两个迭代器 ia 和 ib 相等(指的是同一个节点)，它们的内部指针 ia.i 和 ib.i 将是相等的。这适用于规则 1。然后您在这些指针上使用内置的哈希函数； Qt 会为您处理规则 2。

干杯!