如何创建迭代器的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

你已经做得很好了。散列函数的基本规则是：

如果是hash(x) = hash(y).

• If，

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

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

干杯!