CODEWITHSUNDEEP
c++qthashiterator
Martin Drozdik
Martin Drozdik

Reputation: 13303

How to create a QSet of iterators

What I am trying to do is:

#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;
}

The compiler message is: 

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

I know, that the reason why the first three lines compile is that for the QVector, the iterator is defined as typedef T* iterator; but for the QLinkedList it is a custom type.

I found out, that the QSet template class is implemented in terms of a hash table. Apparently it is possible to evaluate the hash function for a pointer, but not for a custom type.

Please, could you tell me, how to overload the qHash function for my program to compile? I have read some basic information on the workings of a hash table, but I lack the confidence in the subject.

I tried to understand the inner workings of the QLinkedList<T>::iterator. It seems that it is very similar to the QVector<T>::iterator. It just holds a pointer to a node in the linked list instead of a pointer to the item itself.

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

So I tried to define the function in this manner:

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

The program compiled, but I have no confidence in my solution. How should I correctly overload the qHash function?

Upvotes: 2

Views: 781

Answers (1)

Xavier Holt
Xavier Holt

Reputation: 14621

You did perfectly well already. The basic rules of hash functions are:

  1. If x = y then hash(x) = hash(y).
  2. If x != y then hash(x) != hash(y) (as often as possible). This isn't a strict rule, but the better it's followed, the better the performance of the hash table. Ideally, the outputs will appear random.

Your way works because if two iterators, ia and ib are equal (referring to the same node), their internal pointers, ia.i and ib.i will be equal. That takes care of rule 1. Then you use a built-in hash function on those pointers; Qt takes care of rule 2 for you.

Cheers!

Upvotes: 1

Related Questions