Using a QSet as a key in Qt map container

Question

I need a map where the keys will be unique, and each key will be a set or a custom POD struct which contains 3 data items. The values are simply pointers to object instances.

From reading the docs for Qt's QMap vs QHash, it appears as though if I use QSet as the key in my map, then I should use QHash since QSet provides operator==() but not operator<(). Is this a fair assumption? However, the docs also say that QHash requires a "global qHash function called qHash()", but it is not clear to me how this is provided, or if it is an implicit part of QSet?

If alternatively I use a simple struct as my key, I run into the same issue of dealing with qHash(), though a simple POD struct should implicitly have an acceptable overload of operator==() that simply compares all the data, correct?

I'd appreciate some advice on the best approach here.

Answer 1

I advise using QHash unless you need to sort your keys (which I assume you don't).

The operator== function is already provided by QSet, assuming the class which is managed by the set has that operator defined as well (all of the basic data types and QString etc have that).

Two sets are considered equal if they contain the same elements.

This function requires the value type to implement operator==().

You still need to provide the qHash() function which is usally defined like this:

inline uint qHash( QSet<whatever> set )
{
    return /* calculate a hash based on all the elements. */
}

This definition can really be placed anywhere, as long as the code which defines the QHash includes the file which contains the definition. If you have an own class for what is referenced as whatever in this example, you would put that definition e.g. behind your class definition.

Note that the qHash function only needs to ensure that the result of the equation obj1 == obj2 is always equal to the result of qHash(obj1) == qHash(obj2).

This means you don't necessarily have to produce unique hashes, but there is the following note in the documentation:

However, to obtain good performance, the qHash() function should attempt to return different hash values for different keys to the largest extent possible.

---

Examples:

I wrote a small test application for a set which stores strings:

#include <QtCore/QSet>
#include <QtCore/QHash>
#include <QtCore/QList>
#include <QtCore/QDebug>    

typedef QSet<QString> QStringSet;
typedef QHash< QStringSet, QObject* > QStringSetToObjectHash;

inline uint qHash( const QStringSet mySet )
{
    // convert the set to a list so we can sort and iterate over it
    QList<QString> mySetAsList = mySet.toList();
    qSort( mySetAsList );

    // take the hash of the first item
    uint result = qHash( mySetAsList.first() );

    // for each remaining element in the list
    for( int index = 1; index < mySetAsList.count(); index++ )
    {
        // XOR the current result with the hash of the next item
        result ^= qHash( mySetAsList.at( index ) );
    }

    return result;
}
   
void insertIntoHash( QStringSetToObjectHash& hash, const QStringSet& key, QObject* const value )
{
    qDebug() << "---------------------------------";
    qDebug() << "Element hash value:" << qHash( key );

    foreach( QStringSet existingKey, hash.keys() )
    {
        if( existingKey == key )
        {
            qDebug() << "Similar element found using == operator. QHash will not store that item twice";
        }
    }

    hash.insert( key, value );
    qDebug() << "QHash count:" << hash.count();
}

int main(int argc, char *argv[])
{
    QStringSetToObjectHash testHash;

    QObject dummy;

    QStringSet testSet;
    testSet.insert( "1" );
    testSet.insert( "12" );

    insertIntoHash( testHash, testSet, &dummy );

    QStringSet testSet2( testSet );

    insertIntoHash( testHash, testSet2, &dummy );

    QStringSet testSet3;
    testSet3.insert( "12" );
    testSet3.insert( "1" );

    insertIntoHash( testHash, testSet3, &dummy );

    QStringSet testSet4;
    testSet4.insert( "1" );
    testSet4.insert( "2" );
    testSet4.insert( "3" );

    insertIntoHash( testHash, testSet4, &dummy );
}

This produces the following output:

--------------------------------- 
Element hash value: 883
QHash count: 1 
---------------------------------
Element hash value: 883  Similar element found using == operator. QHash will not store that item twice
QHash count: 1 
---------------------------------
Element hash value: 883  Similar element found using == operator. QHash will not store that item twice
QHash count: 1 
--------------------------------- 
Element hash value: 48
QHash count: 2