c++ - 使用 QSet 作为 Qt 映射容器中的键

Question

我需要一个映射，其中的键是唯一的，每个键都是一个集合或一个包含 3 个数据项的自定义 POD 结构。这些值只是指向对象实例的指针。

来自阅读docs for Qt's QMap vs QHash , 看起来好像我使用 QSet作为我 map 中的键，那么我应该使用 QHash，因为 QSet 提供了 operator==()但不是 operator<() .这是一个公平的假设吗？然而，文档还说 QHash 需要一个“名为 qHash()” 的全局 qHash 函数，但我不清楚这是如何提供的，或者它是否是 QSet 的隐含部分？

如果我使用一个简单的结构作为我的键，我会遇到同样的问题来处理 qHash() ，虽然一个简单的 POD 结构应该隐含地具有可接受的重载 operator==()这只是比较所有数据，对吗？

如果您能给我一些关于最佳方法的建议，我将不胜感激。

Answer 1

我建议使用 QHash 除非你需要对你的键进行排序(我假设你不需要)。

operator== 函数已经由 QSet 提供，假设由集合管理的类也定义了该运算符(所有基本数据类型和 QString 等都有)。

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

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

你仍然需要提供通常定义如下的qHash()函数:

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

这个定义实际上可以放在任何地方，只要定义 QHash 的代码包含包含该定义的文件即可。如果您有一个自己的类用于此示例中被引用为 whatever 的内容，您可以将该定义放在例如在你的类定义后面。

注意qHash函数只需要保证等式obj1 == obj2的结果总是等于qHash(obj1)的结果== qHash(obj2).

这意味着您不必生成唯一的哈希值，但文档中有以下注释:

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

---

例子:

我为一组存储字符串编写了一个小型测试应用程序:

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

这会产生以下输出:

--------------------------------- 
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