9.4 关联容器:QHash、QMultiHash和QSet

本节介绍三种基于哈希表的关联容器,单哈希映射 QHash、多哈希映射 QMultiHash 和集合 QSet。 QHash 、QMultiHash 的功能与上一节 QMap、QMultiMap 功能非常类似,也是将存储 key-value 数据对,但哈希映射与普通映射对数据的内部存储结构和访问效率有区别。集合 QSet 就是数学上的集合,比如求交集∩、求并集∪等。集合的元素没有序号,元素之间也不讲究顺序。
本节共分为四个小节,前三个小节依次介绍 QHash、QMultiHash 和 QSet 的功能,并辅以示例讲解,最后归纳一下关联容器操作的算法复杂度。

9.4.1 单哈希映射 QHash

QHash 是基于哈希表实现的字典结构,存储 key-value 数据对。哈希表可以将任意长度的数据根据特定算法计算固定长度的“精简版”数值,就是数据条目的哈希值。简要来说,对于 key-value 数据对,我们根据 key 的数值计算得到哈希值作为数据存储空间的序号,在该序号位置保存 key-value数据对,那么我们就可以快速地根据 key 计算序号访问到 value 数值。实际中的哈希表结构更复杂,因为要考虑哈希值碰撞的问题,本节就不讨论了。上一节 QMap 利用红黑树实现,读取一个元素的平均效率是 O(logN) ,N 是元素总数。而通过 QHash 读取一个元素,只需要计算 key 对应的哈希值,不需要遍历查找树形结构或数组结构,哈希表的访问效率平均为 O(1) 。
QHash 的优点是通常情况下访问元素效率极高,但是也有缺点,元素排列是无序的,元素排列不按照数值大小或字典序,是按照哈希算法计算的值进行排列,这些哈希值都是杂乱无章的数 值。如果需要有序的数据结构,那么 QMap 就更实用。

QHash 与 QMap 的大部分功能函数名一样,存储的数据也都必须是可赋值类型。但 QHash 与 QMap 有三个重要区别,列举如下:
① QHash 拥有更快的元素查询效率,平均为 O(1),QMap 平均为 O(logN) 。
② 在 QHash 对象里进行元素遍历时,元素排列杂乱无章,而 QMap 总是按照 key 的排序排列。
③ QHash 的 key 类型必须提供  operator==() 运算符函数和  qHash(Key)  全局函数,而 QMap 的 key 类型则必须提供 operator<() 运算符函数。


下面我们分类讲解 QHash 的功能函数:
(1)构造函数
QHash()  //默认构造函数
QHash(std::initializer_list<std::pair<Key, T> > list)
QHash(const QHash<Key, T> & other)
QHash(QHash<Key, T> && other)
~QHash()  //析构函数
第二个构造函数用于支持初始化列表构造,是 C++11 特性,第三个是复制构造函数,第四个是移动构造函数,也是 C++11 特性。构造函数使用举例如下:
    QHash<QString ,int> nameAge = { {"Alice", 20},
    {"Bob", 22},
    {"Kal", 19} };
    qDebug()<<nameAge;
    QHash<QString ,int> nameAge2 = std::move( nameAge );
    qDebug()<<nameAge;
    qDebug()<<nameAge2;
上面一段代码打印输出结果为:
QHash(("Alice", 20)("Kal", 19)("Bob", 22))
QHash()
QHash(("Alice", 20)("Kal", 19)("Bob", 22))
注意 QHash 对象里三个元素是乱序的,没有按字典序排列;进行移动构造后,原本的对象 nameAge 被清空,元素全部填充到新对象 nameAge2 里面。

(2)添加函数
  对于单哈希映射,通常使用下面的添加函数:
iterator    insert(const Key & key, const T & value)
insert() 函数负责添加新元素,或者替换旧的同 key 元素,如果哈希映射之前没有 key 键元素,那么为哈希映射新增一个元素,键为 key,映射的值为 value;如果之前存在键为 key 的元素,那么替换该元素的映射值为新的 value。QHash 本身是支持多哈希映射功能的,但一般不建议这样用。对用于多哈希映射场景 QHash  对象,如果存在多个键为 key 的元素,那么 insert() 函数替换最近添加的同 key 元素。
对于多哈希映射场景,建议使用下面的添加函数:
iterator    insertMulti(const Key & key, const T & value)
insertMulti() 总是为哈希映射添加新元素,而不管之前有无同 key 元素,也不管是否有同 key-value 对的元素。

(3)移除和删除函数
清空哈希映射对象所有元素,使用下面函数:
void    clear()
 如果希望根据键 key 来删除元素,使用下面函数:
int    remove(const Key & key)
remove() 函数删除所有键为 key 的元素,返回值是删除的匹配元素个数,如果没有匹配元素,那么返回 0。
如果希望从哈希映射中卸下一个元素,并作为返回值获取该元素,那么使用下面函数:
T    take(const Key & key)
如果哈希映射中不存在匹配 key 的元素,该函数返回 Key 类型默认构造函数生成的默认元素;如果存在 1 个匹配元素,将元素从哈希映射卸下,并返回;如果存在多个匹配 key 的元素,卸下最近添加的一个匹配元素返回,其他旧的匹配元素不变。
如果知道元素对应的迭代器位置 pos,可以根据迭代器位置删除指向的元素:
iterator    erase(iterator pos)
erase() 返回删除元素之后下一个元素的迭代器位置,有可能是迭代器末尾位置。

(4)访问和查询函数
查询 QHash 对象中元素个数,可以使用下面两个函数:
int    count() const
int    size() const
另外 count() 还有带参数的版本,计算匹配 key 的元素数量:
int    count(const Key & key) const
QHash 对象内部使用哈希表,对于哈希表的容量,可以进行查询、扩容、以及缩减空余等操作:
int    capacity() const      //查询哈希表容量
void    reserve(int size)   //提前预留好参数里指定个数的哈希表,扩容操作
void    squeeze()             //缩减哈希表未使用的冗余空间
针对哈希表容量操作的三个函数很少用到,如果提前知道需求的哈希表特别大,那么可以使用 reserve() 分配哈希表容量,避免大量增加元素时的自动扩容操 作,节省时间。
检查 QHash  对象是否为空,使用下面函数判断:
bool    isEmpty() const // Qt 风格命名,检查哈希映射对象是否为空
bool    empty() const    // STL 风格命名,检查哈希映射对象是否为空
检查哈希映射对象是否包含匹配 key,使用下面函数:
bool    contains(const Key & key) const
如果希望直接找到匹配 key 元素对应的迭代器,使用下面三个函数:
const_iterator    constFind(const Key & key) const  // Qt  风格命名,查找匹配 key 元素的只读迭代器
const_iterator    find(const Key & key) const // STL 风格命名,查找匹配 key 元素的只读迭代器
iterator    find(const Key & key) //查找匹配 key 元素的读写迭代器
如果找不到匹配元素,constFind() 和 find()   返回 end() 迭代器数值,指向末尾不存在位置。
凡是返回迭代器数值的函数,都要注意判断是否为 end() 末尾数值。

如果需要根据 key 查询对应的 value(即正向查找,是通过哈希函数实现,效率高,平均O(1)),使用下面函数:
const T    value(const Key & key) const
const T    value(const Key & key, const T & defaultValue) const
两个 value() 函数如果找到匹配的元素,就返回映射的值;如果第一个 value() 函数找不到匹配元素,就返回 T 值类型默认构造函数生成的默认数值,而第二个 value() 函数在找不到匹配元素时,返回参数里指定的 defaultValue 。对于多哈希映射的场景,如果匹配多个元素,那么返回最近添加的匹配元素的 value 值。

如果希望一股脑获取所有的值列表,使用下面函数:
QList<T>    values() const
对于多哈希映射的场景,获取匹配 key 所有映射的值,使用下面带参数的函数:
QList<T>    values(const Key & key) const

如果希望根据 value 值,反查匹配的 key,那么使用下面函数:
const Key    key(const T & value) const
const Key    key(const T & value, const Key & defaultKey) const
如果找到匹配 value 值的键,那么返回该键 key,对多个匹配元素的情况,总是返回首先匹配 value的 key;如果找不到,那么第一个 key() 函数返回 Key 类型默认构造函数生成的默认对象,第二个 key() 函数返回参数里的 defaultKey。反查操作是遍历哈希表,效率比较低,一般是 O(N)。
如果希望一股脑获取所有的键列表,同样 key 的多个元素算作多个键,那么使用下面函数:
QList<Key>    keys() const  //多个相同 key  算做多个
如果希望获取不会重复的键列表,使用下面函数:
QList<Key>    uniqueKeys() const  //多个相同 key 只算一个
如果希望获取匹配 value 的所有键列表,那么使用下面函数:
QList<Key>    keys(const T & value) const

(5)交换函数和合并函数
 将 QHash 对象自身与另一个 QHash 对象(key 类型、value 类型要一样)的内容全部交换,使用下面成员函数:
void    swap(QHash<Key, T> & other)
交换函数效率很高,并且不会失败。
将另一个 QHash 对象的元素全部复制合并到对象自己内部(两个对象 key 类型、value 类型要一样),使用下面函数:
QHash<Key, T> &    unite(const QHash<Key, T> & other)
unite()  函数总是添加新元素,同样 key 的元素只会增加,不会替换,所以很可能会形成多重映射。

(6)运算符函数
对于运算符函数,我们举两个哈希映射对象来举例说明:
    QHash<QString, int> h1;
    h1["Ali"] = 99;
    QHash<QString, int> h2;
    h2["Bob"] = 88;
    h2["Kal"] = 77;
运算符使用示范如下表所示:

运算符函数 举 例 描述
bool operator!=(const QHash<Key, T> & other) const  h1 != h2; 两个哈希对象的元素不一样,不等号判断结果为 true。
bool operator==(const QHash<Key, T> & other) const  h1 == h2; 两个哈希对象的元素不一样,等于号判断结果为 false。
QHash<Key, T> & operator=(const QHash<Key, T> & other)  h1 = h2; 将 h2 所有元素复制给 h1,执行后二者相等。
QHash<Key, T> & operator=(QHash<Key, T> && other)  h1 = std::move(h2); 将 h2 中所有元素移动给h1,h2自己清空。
T & operator[](const Key & key)  h2["Kal"] = 18; 修改了 "Kal" 对应的value值。
const T operator[](const Key & key) const  qDebug()<< h2["Kal"]; 打印 "Kal" 对应的常量值。

 两个哈希对象相等只需要二者拥有的键值对一样就行了,如果键值对的前后顺序不同,那么不会影响等于号判断。比如两个哈希对象,第一个哈希 对象三个元素 在内存中的存储序列为:
("Bob", 98), ("Ali", 97), ("Cal", 99)
第二个哈希对象三个同样元素的存储序列为:
("Ali", 97), ("Bob", 98), ("Cal", 99)
那么这两个哈希对象依然是符合相等条件的。

(7)迭代器函数
映射类也定义了 STL 风格和 Qt 命名风格的迭代器:
class    const_iterator   //STL风格只读迭代器
class    iterator             //STL风格读写迭代器
typedef    ConstIterator  //Qt 风格只读迭代器
typedef    Iterator          //Qt风格读写迭代器
STL 风格迭代器使用示范:
QHash<QString, int>::const_iterator i = hash.constBegin();
while (i != hash.constEnd()) {
    cout << i.key() << ": " << i.value() << endl;
    ++i;
}
QHash 对象中的元素排列是无序的,是通过内部哈希函数计算元素排列位置,元素前后序列难以预知。
获取映射的头部元素、尾部假想元素的迭代器函数列举如下:
iterator    begin()     //指向头部的读写迭代器
const_iterator    begin() const            //指向头部的只读迭代器
const_iterator    cbegin() const          //指向头部的只读迭代器
const_iterator    constBegin() const  //指向头部的只读迭代器,Qt风格
iterator    end()       //指向尾部后面假想元素的读写迭代器
const_iterator    end() const             //指向尾部后面假想元素的只读迭代器
const_iterator    cend() const           //指向尾部后面假想元素的只读迭代器
const_iterator    constEnd() const    //指向尾部后面假想元素的只读迭代器,Qt风格
注意 *end() 返回的迭代器通常只用来做不等于判断,它指向的东西根本不存在, *end() 仅用于越界判断。
虽然获取头部、尾部迭代器的函数多,其实功能类似,起了一堆名字是方便兼容 STL 风格函数命名。
另外,迭代器可以配合之前的 insert()、insertMulti()、erase() 、find() 等函数的返回值使用,利用迭代器进行元素查询或修改。

(8)默认支持哈希的类型
之前我们提到 QHash 的 key 类型必须提供  operator==() 运算符函数和  qHash(Key)  全局函数,Qt 为常见的 C++ 类型和 Qt 数据类型都提供了全局哈希函数,下面仅举几个例子:
uint    qHash(const QString & key, uint seed = 0)  //计算字符串的哈希值
uint    qHash(const T * key, uint seed = 0)              //计算任意数据指针的哈希值
uint    qHashBits(const void * p, size_t len, uint seed = 0)  //辅助函数,用于编写新类型的 qHash() 函数,可以根据任意内存块生成哈希值
第一个 qHash()  函数,参数 key 类型为 QString ,参数 seed 是哈希算法种子,对于同样的两个字符串,如果种子不同,就可以生成不同的哈希值。哈希函数的返回值都一样,是 uint 类型,无符号整数。
第二个 qHash() 函数,参数 key 类型是 T *,就是任意数据类型的指针,不管数据类型是什么,其指针总是固定的长度,可以将指针数值用于计算哈希 值。
第三个是计算哈希值的辅助函数,函数名为 qHashBits() ,针对任意内存块来计算哈希值,p 是内存块指针,len 是内存块长度,这个函数可以辅助自定义类型编写新的全局 qHash() 函数,只需要将新类型对象的指针和长度、种子传递给 qHashBits() 函数,就能得到结果哈希值。

(9)其他内容
QHash 模板类也支持串行化输出和输入,通过以下函数实现:
QDataStream &    operator<<(QDataStream & out, const QHash<Key, T> & hash) //输出到数据流
QDataStream &    operator>>(QDataStream & in, QHash<Key, T> & hash)  //从数据流输入
注意串行化输入输出正常工作的前提是 Key 类型和数值 T 类型都支持 QDataStream  串行化。

关于  QHash,这里再提醒两个注意事项:
① 不能使用 hash[key] 这种形式查找哈希对象里是否包含键 key 的元素,因为 operator[](const Key & key) 函数在找不到 key 键元素时,自动调用 value 类默认构造函数为哈希对象添加新的 key-value 哈希映射元素。
应该用 contains(key) 来判断是否包含该 key 元素,或者用  hash.value( key ) 函数查找值,value() 函数不会为哈希对象添加新元素,虽然 value() 函数找不到时也会返回 value 类型默认构造的值,但不会改变哈希对象内容。

② 一般不建议使用 QHash 的 insertMulti() 和 unite() 函数进行多重哈希映射添加或哈希映射合并,Qt 单独提供了 QMultiHash表示多重哈希映射,在程序中尽量让 QHash 保持一对一映射,避免代码的误解。

QHash 类的使用方法与 QMap 非常类似,因此本小节留一个练习,就是将之前 9.3.1 小节 nameage 示例中 QMap 内容改用 QHash 实现。
下面本小节新的示例介绍如何将自定义类型作为 QHash 类的 key 类型,实现自定义类型支持 QHash 的操作,以及串行化输入输出。
在示例中,我们将人员信息自定义为 Person 类,包含姓名、性别、出生日期三个成员变量,将 Person 类作为自定义 key 类型,而身份 ID 就作为 QHash 的 value  类型,身份 ID 简单使用  quint64 表示。下面开始本小节的示例:
我们打开 QtCreator,新建一个 Qt Widgets Application 项目,在新建项目的向导里填写:
①项目名称 persontoid,创建路径 D:\QtProjects\ch09,点击下一步;
②套件选择里面选择全部套件,点击下一步;
③基类选择 QWidget,点击下一步;
④项目管理不修改,点击完成。
进入新项目后,我们右键点击左侧 persontoid 项目根,弹出右键菜单,选择“添加新文件”:
addnew1
弹出新建文件对话框,左边一栏选择“C++”,中间一栏选择“C++ Class”:
addnew2
点击上图界面右下角“Choose...” 按钮,进入定义类的向导对话框,在 Class name 一栏输入 Person 作为类名:
addnew3
输入类名后,头文件名和源文件名会自动填充,不需要再修改,点击“下一步”按钮,进入项目管理界面:
addnew4
项目管理界面不用修改,点击完成,Person 类的文件 person.h 和 person.cpp  会自动添加到本项目中。
添加新类文件后,如果 QtCreator 左下角“运行”的绿三角按钮是灰色的,那么切换一下构建套件,然后切换回来就行了。
添加Person 类的文件之后,我们先编辑图形界面 widget.ui 文件,后面再统一编辑代码文件。
打开 widget.ui 文件进入图形化编辑界面,构造界面如下图所示:
ui
界面第一行是“Person-ID映射”标签、“保存数据”按钮pushButtonSaveData、“加载数据”按钮 pushButtonLoadData, 将“Person-ID映射”标签的sizePolicy属性水平策略设置为 Expanding,第一行控件使用水平布局器排列;
第二行是一个列表控件 listWidget ,用于显示哈希映射数据的内容;
最后两行使用了网格布局,包括两行内容,倒数第二行为“姓名”标签、单行编辑器lineEditName、“性别”标签、组合框 comboBoxGender、 “生日”标签、日期编辑器dateEditBirthday;最后一行是“身份ID”标签、单行编辑器lineEditID、“添加元素”按钮 pushButtonAdd、“删除选中元素”按钮pushButtonDel、“Person查ID”按钮pushButtonPersonToID、“ID查 Person”按钮pushButtonIDToPerson,最后两行对齐了使用网格布局器。
最后整个窗体使用垂直布局器,窗口大小 520*320。

然后我们依次对界面六个按钮,逐个右击,在右键菜单选择“转到槽...”,然后添加各个按钮的 clicked() 信号的槽函数。
界面布局和槽函数编辑完成后面,我们进入代码编辑。
打开 person.h 头文件代码,编辑如下:
#ifndef PERSON_H
#define PERSON_H

#include <QHash>
#include <QMap>
#include <QString>
#include <QDateTime>
#include <QDataStream>

class Person
{
public:
    //带参数的构造函数
    Person(QString strName, QString strGender, QDate birthDay);

    //数据库容器对象只能存储可赋值数据,key和value都要求可赋值
    //不带参数的默认构造函数,可赋值类型要求 1
    Person();
    Person(const Person &other);    //复制构造函数,可赋值类型要求2
    Person &operator =(const Person &other);//赋值号,可赋值类型要求3
    ~Person();

    //姓名、性别、出生日期,三个成员变量读写函数,只读函数要加 const 修饰
    inline QString name() const
    {
        return m_name;
    }
    inline void setName(const QString &strName)
    {
        m_name = strName;
    }
    inline QString gender() const
    {
        return m_gender;
    }
    inline void setGender(const QString &strGender)
    {
        m_gender = strGender;
    }
    inline QDate birthday() const
    {
        return m_birthday;
    }
    inline void setBirthday(const QDate &bday)
    {
        m_birthday = bday;
    }

protected:
    //姓名、性别、出生日期
    QString m_name;
    QString m_gender;
    QDate m_birthday;
};

//哈希对于key类型额外要求 1,全局的等于号比较函数
bool operator ==(const Person &p1, const Person &p2);

//哈希对于key类型额外要求 2,全局的哈希函数
uint qHash(const Person &key, uint seed=0);

//输入输出串行化要求,全局的串行化函数
QDataStream &operator <<(QDataStream &out, const Person &pout);
QDataStream &operator >>(QDataStream &in, Person &pin);

//补充说明,如果用于 QMap,那么实现全局的小于号比较函数,该函数还可以用于 qSort()排序函数
bool operator <(const Person &p1, const Person &p2);

#endif // PERSON_H
文件开头我们添加多个类型的头文件引用,然后定义 Person 类的内容,添加带姓名、性别、生日三个参数的构造函数声明,这个是后面构造Person对象常用的函数。然后是默认构造函数、复制构造函数、赋值运算符三个函数声明,这是容器数据使用的可赋值类型要求的三个条件。
析构函数使用默认的,没有修改。然后添加了姓名 m_name、性别 m_gender、生日 m_birthday 三个成员变量的读写函数,注意给读函数的声明末尾添加 const 修饰符,以便于后面  const Person &p2 这种常量调用只读函数,注意常量声明的对象只能调用声明末尾带 const  只读修饰的函数。

针对哈希映射的 key 类型,要求实现全局的 ==()  比较运算符函数和全局 qHash() 函数,因此在类声明的外面,声明这两个函数;
然后声明了 QDataStream 串行化输入输出的两个函数,最后一个是全局的  <()  小于运算符函数,这个小于号函数可用于 QMap key 类型或者 qSort() 排序函数的支持。

下面我们对 person.cpp 文件分块讲解,首先是构造函数等部分:
#include "person.h"

//带参数的构造函数
Person::Person(QString strName, QString strGender, QDate birthDay)
{
    m_name = strName;
    m_gender = strGender;
    m_birthday = birthDay;
}
//默认构造函数,可赋值类型要求 1
Person::Person()
{
    m_name = "";
    m_gender = "";
    m_birthday = QDate(2000, 1, 1);
}
//复制构造函数,可赋值类型要求2
Person::Person(const Person &other)
{
    m_name = other.m_name;
    m_gender = other.m_gender;
    m_birthday = other.m_birthday;
}
//赋值运算符,可赋值类型要求3
Person &Person::operator =(const Person &other)
{
    m_name = other.m_name;
    m_gender = other.m_gender;
    m_birthday = other.m_birthday;
    //返回对象
    return *this;
}
//默认析构函数
Person::~Person()
{

}
带三个参数的构造函数,简单将参数分别保存到成员变量;接着是默认构造函数,不带参数,直接设置默认的成员变量值;
复制构造函数和 =() 赋值运算符函数代码类似,就是复制数据到成员变量,赋值运算符函数返回自身对象,以便进行连等赋值。
然后是用于支持哈希映射 key 类型的函数:
//哈希对于key类型额外要求 1,全局的等于号比较函数
bool operator ==(const Person &p1, const Person &p2)
{
    bool bRet = false; //默认不等
    if(  (p1.name() == p2.name())
      && (p1.gender() == p2.gender())
      && (p1.birthday() == p2.birthday()) )
    {
        bRet = true; //三个成员都相等
    }
    //返回
    return bRet;
}
//哈希对于key类型额外要求 2,全局的哈希函数
uint qHash(const Person &key, uint seed)
{
    uint nRet;
    nRet = qHash(key.name(), seed)
            ^ qHash(key.gender(), seed)
            ^ qHash(key.birthday(), seed);
    return nRet;
}
==() 比较运算符函数仅在三个成员值都相等的情况下返回 true ,其他情况均为 false。
全局的 qHash() 函数参数,第一个是对象本身,第二个是随机数种子,种子默认为 0,也可以自己指定种子数值。
这里实现的哈希函数比较简单,直接将三个成员的数值分别做哈希,然后进行异或,得到最终的哈希数值返回。
然后我们实现串行化输入输出的函数:
//输入输出串行化要求,全局的串行化函数
QDataStream &operator <<(QDataStream &out, const Person &pout)
{
    out<<pout.name()<<pout.gender()<<pout.birthday();
    return out;
}

QDataStream &operator >>(QDataStream &in, Person &pin)
{
    //定义三个变量接受输入数据
    QString strName;
    QString strGender;
    QDate birthday;
    in>>strName>>strGender>>birthday;
    //设置成员变量
    pin.setName( strName );
    pin.setGender( strGender );
    pin.setBirthday( birthday );
    return in;
}
输出函数中,依次将姓名、性别、生日输出;输入时先定义三个临时变量接受输入数据,然后分别设置给成员变量。
输入输出函数都返回数据量变量,方便进行多个变量的连续输入输出。
person.cpp 最后末尾是补充的 <() 运算符函数,可以用于支持 QMap key 类型,或者用于 qSort() 排序函数:
//补充说明,如果用于 QMap,那么实现全局的小于号比较函数,该函数还可以用于 qSort()排序函数
bool operator <(const Person &p1, const Person &p2)
{
    //按照姓名字典序大小比较
    return ( p1.name() < p2.name() );
}
<()  比较函数用的是使用 name() 函数返回值比较,按字典序排列。
Person 类及其相关代码可以支持 QHash、QMap 的 key 类型,方便使用。以后使用容器遇到需要自定义的 key 类型,可以参照上面代码实现。

下面我们介绍界面类的头文件 widget.h 内容:
#ifndef WIDGET_H
#define WIDGET_H

#include <QWidget>
#include "person.h"

namespace Ui {
class Widget;
}

class Widget : public QWidget
{
    Q_OBJECT

public:
    explicit Widget(QWidget *parent = 0);
    ~Widget();

    //显示更新后的数据
    void UpdateDataShow();

private slots:
    void on_pushButtonAdd_clicked();

    void on_pushButtonDel_clicked();

    void on_pushButtonPersonToID_clicked();

    void on_pushButtonIDToPerson_clicked();

    void on_pushButtonSaveData_clicked();

    void on_pushButtonLoadData_clicked();

private:
    Ui::Widget *ui;

    //定义容器
    QHash<Person, quint64> m_data;
};

#endif // WIDGET_H
widget.h 添加了 "person.h" 头文件包含。在类声明里面我们添加了一个 UpdateDataShow() 函数,专门用于在数据容器内容变化时,将内容显示到界面的列表控件中,然后声明了使用 Person 类型为 key,使用 quint64 类型为 value 的哈希映射类型对象 m_data 。其他函数是自动生成的,有 6 个按钮对应的槽函数。

下面我们分块介绍 widget.cpp 内容,首先是头文件包含和构造函数:
#include "widget.h"
#include "ui_widget.h"
#include <QMessageBox>
#include <QDebug>
#include <QFile>
#include <QFileDialog>
#include <QDataStream>

Widget::Widget(QWidget *parent) :
    QWidget(parent),
    ui(new Ui::Widget)
{
    ui->setupUi(this);
    //添加性别
    ui->comboBoxGender->addItem( tr("男") );
    ui->comboBoxGender->addItem( tr("女") );
    //日历控件编辑时,点击右边小按钮弹出日历表
    ui->dateEditBirthday->setCalendarPopup( true );

}

Widget::~Widget()
{
    delete ui;
}
构造函数里面,为 ui->comboBoxGender 组合框添加性别的字符串,然后设置 ui->dateEditBirthday 日历编辑器可以弹出日历表,方便选择日期。
然后是我们手动添加的更新数据显示的函数:
//显示更新后的数据
void Widget::UpdateDataShow()
{
    //清空旧的显示
    ui->listWidget->clear();
    //获取key列表
    QList<Person> listPersons = m_data.keys();
    //个数
    int nCount = listPersons.count();
    for (int i=0; i<nCount; i++)
    {
        //字符串
        QString strLine;
        strLine = listPersons[i].name() + tr("\t")
                + listPersons[i].gender() + tr("\t")
                + listPersons[i].birthday().toString( "yyyy-MM-dd" );
        //ID
        quint64 theID = m_data[ listPersons[i] ] ;
        strLine += tr("\t%1").arg( theID );
        //添加到列表显示
        ui->listWidget->addItem( strLine );
    }
    //处理完成
}
该函数先清空列表框的旧数据,然后获取 m_data 容器对象的所有 key 存到 listPersons;
循环处理 listPersons 每个人员对象,将姓名、性别、生日连接成字符串,并获取该人员的 ID 数值,转为字符串也添加到字符串,构成列表控件的一行内容,添加给列表控件,注意姓名、性别、生日、ID 四个字符串都使用 '\t' 字符分隔,方便后面切分处理。

接下来是添加元素的函数:
//添加元素
void Widget::on_pushButtonAdd_clicked()
{
    //检查姓名和ID
    QString strName = ui->lineEditName->text().trimmed();
    if( strName.isEmpty() )
    {
        QMessageBox::warning(this, tr("检查姓名"), tr("姓名为空,不能添加!"));
        return;
    }
    quint64 nID;
    bool bOK = false; //用于检查转换是否出错
    nID = ui->lineEditID->text().toULongLong( &bOK, 10 );
    if( ! bOK )
    {
        QMessageBox::warning(this, tr("ID检查"), tr("请输入合法数字ID!"));
        return;
    }
    //性别生日
    QString strGender = ui->comboBoxGender->currentText();
    QDate birthday = ui->dateEditBirthday->date();
    //构造 Person
    Person pkey( strName, strGender, birthday );
    //添加元素
    m_data[ pkey ] = nID;
    //更新显示
    UpdateDataShow();
}
我们先检查姓名字符串,如果为空提示不能为空,然后返回;姓名字符串正常再继续后面代码;
然后检查 ID 的数字字符串,如果转换出问题,bOK 变量就是 false,提示转换出问题,如果ID转换没问题,继续后面代码;
获取性别、日期变量,根据姓名、性别、日期三个参数构造 Person 类对象 pkey,然后使用类似数组元素赋值的语法:
m_data[ pkey ] = nID;
为哈希容器对象添加键值对 pkey 和 nID,注意 [] 函数的用法,如果元素不存在就创建该元素添加给哈希对象,如果哈希对象存在相同的 pkey 键,那么仅更新 value 值,而不会重复添加新元素。
添加元素或更新元素后,调用 UpdateDataShow() 更新界面控件显示。

接下来是删除选定元素的函数:
//删除选中元素
void Widget::on_pushButtonDel_clicked()
{
    //当前条目
    QListWidgetItem *pCurItem = ui->listWidget->currentItem();
    if( NULL == pCurItem )
    {
        return;
    }
    if( ! (pCurItem->isSelected()) )
    {
        //未被选中,不删除
        qDebug()<<tr("未选中条目,不做删除操作");
        return;
    }
    //将文本转为变量
    QString strAll = pCurItem->text();
    QStringList listParas = strAll.split( "\t" );
    qDebug()<<tr("删除元素:")<<listParas;
    // 0号是名字,1号是性别,2号是生日,3号是ID
    QDate birthday = QDate::fromString( listParas[2], "yyyy-MM-dd" );
    Person pkey( listParas[0], listParas[1], birthday );
    //删除变量元素
    m_data.remove( pkey );
    //更新显示
    UpdateDataShow();
}
我们先获取列表控件的当前条目,如果当前条目为空,不处理;
当前条目非空,再判断条目是否处于选中状态,如果未选中也不处理,防止误删除未选中条目;
如果当前条目确定是选中了的,那么获取条目的文本存到 strAll;
对strAll进行切分,按照 "\t" 进行切割,分成四段字符串:姓名、性别、生日、ID,构造 Person 的键值,只需要前三个;
我们将生日字符串转换为 QDate 对象,然后构造 Person 对象 pkey,调用 m_data.remove( pkey ) 函数删除匹配的所有元素。
最后调用  UpdateDataShow() 更新显示。

接下来实现根据Person内容查询ID的函数:
//Person查询ID
void Widget::on_pushButtonPersonToID_clicked()
{
    //检查姓名
    QString strName = ui->lineEditName->text().trimmed();
    if( strName.isEmpty() )
    {
        QMessageBox::warning(this, tr("检查姓名"), tr("姓名为空,不能添加!"));
        return;
    }
    //性别、生日
    QString strGender = ui->comboBoxGender->currentText();
    QDate birthday = ui->dateEditBirthday->date();
    //对象
    Person pkey( strName, strGender, birthday );

    //一定要用 contains 函数查询 key 是否存在
    if( m_data.contains( pkey ) )
    {
        quint64 nID = m_data[ pkey ];
        QString strInfo = tr("已查询到ID: %1").arg( nID );
        QMessageBox::information(this, tr("Person查ID"), strInfo );
    }
    else
    {
        QMessageBox::information(this, tr("Person查ID"), tr("未查找到。"));
    }
}
我们先获取姓名字符串,检查非空后进行后续查询;获取性别生日,然后根据三个变量构造 Person  对象 pkey;
注意查询时,一定要使用 m_data.contains( pkey ) 检查哈希容器是否存在该键,不能使用中括号[],中括号会自动添加新元素。
通过 m_data.contains( pkey )  检查,如果有匹配 Person 对象,那么获取对应的 ID,弹出信息框,显示ID数值;
如果容器不包含匹配的 key ,那么显示信息框未查找到。

接下来是根据 ID 反向查找匹配的 Person 键对象的函数:
//根据ID反向查找Person
void Widget::on_pushButtonIDToPerson_clicked()
{
    //检查ID
    quint64 nID;
    bool bOK = false; //用于检查转换是否出错
    nID = ui->lineEditID->text().toULongLong( &bOK, 10 );
    if( ! bOK )
    {
        QMessageBox::warning(this, tr("ID检查"), tr("请输入合法数字ID!"));
        return;
    }
    //根据 value 反查 key
    QList<Person> listKeys = m_data.keys(nID);
    //个数
    int nCount = listKeys.count();
    if( nCount < 1 )
    {
        QMessageBox::information(this, tr("ID查Person"), tr("未查找到。"));
        return;
    }
    //如果多个人ID相同
    QString strInfo = tr("已查到匹配人名:\r\n");
    for(int i=0; i<nCount; i++)
    {
        strInfo += listKeys[i].name() + tr("\r\n");
    }
    //提示框
    QMessageBox::information(this, tr("ID查Person"), strInfo);
}
我们首先检查 ID 编辑框内容,ID 转换正常后进行后面查询;
我们根据 ID 进行反查,获取所有匹配 ID 的 key 列表 m_data.keys(nID) ;
如果 listKeys 元素个数小于 1 ,说明没找到,提示信息框说明未查找到;
如果有元素,那么循环获取 listKeys 列表中 Person 对象的姓名,添加到字符串 strInfo ,
最后显示到信息框,说明匹配到的人员姓名。

接下来是保存数据按钮的槽函数:
//保存数据到文件
void Widget::on_pushButtonSaveData_clicked()
{
    //判断数据是否为空
    if( m_data.isEmpty() )
    {
        return;
    }
    //获取保存文件名
    QString strFile = QFileDialog::getSaveFileName(this, tr("保存数据到文件"),
                                                   "", "Data files(*.data);;All files(*)");
    if( strFile.isEmpty() )
    {
        return;
    }
    //文件名不空
    QFile fileOut( strFile );
    if( ! fileOut.open( QIODevice::WriteOnly ) )
    {
        QMessageBox::warning(this, tr("保存文件"),
                             tr("保存文件失败,无法写入该文件:\r\n%1").arg(strFile));
        return;
    }
    //文件正常
    QDataStream dsOut( &fileOut );
    dsOut<<m_data;  //非常简单的一句代码,写入所有数据到文件
    QMessageBox::information(this, tr("保存文件"),
                         tr("保存文件完成:\r\n%1").arg(strFile));
}
我们先判断成员 m_data ,如果数据为空就不需要保存,直接返回;
如果数据非空,那么获取要保存的文件名,如果保存文件名为空,那么也不处理,返回;
文件名非空,进行后面处理,根据文件名构造文件对象 fileOut,尝试以只写模式打开文件,如果打开失败,提示错误信息,返回;
如果打开文件正常,那么根据文件对象指针,定义数据流对象 dsOut;
然后输出到文件只需要一句代码:
dsOut<<m_data;
我们实现 Person 类附带的输入输出函数,为的就是这个效果,串行化输入输出特别方便。
最后弹出信息窗,说明保存文件完成。

widget.cpp 文件最后是输入数据到 m_data 的函数代码:
//从文件加载数据
void Widget::on_pushButtonLoadData_clicked()
{
    //获取读取的文件名
    QString strFile = QFileDialog::getOpenFileName(this, tr("从文件加载数据"),
                                                   "", "Data files(*.data);;All files(*)");
    if( strFile.isEmpty() )
    {
        return;
    }
    //文件名不空
    QFile fileIn( strFile );
    if( ! fileIn.open( QIODevice::ReadOnly ) )
    {
        QMessageBox::warning(this, tr("读取文件"),
                             tr("读取文件失败,无法打开该文件:\r\n%1").arg(strFile));
        return;
    }
    //文件正常
    QDataStream dsIn( &fileIn );
    //清空旧的
    m_data.clear();
    ui->listWidget->clear();
    //加载数据
    dsIn>>m_data;
    //更新显示
    UpdateDataShow();
    QMessageBox::information(this, tr("加载文件"),
                         tr("加载文件完成:\r\n%1").arg(strFile));
}
首先获取要读取的文件名,如果文件名为空就返回;文件非空进行后面处理;
根据文件名建立文件对象 fileIn,尝试以只读模式打开,如果打开失败,那么提示信息框说明并返回;
如果文件打开正常,那么以文件对象指针定义数据流对象 dsIn;
在进行输入之前,把 m_data 变量和界面的列表框都清空;
然后输入数据只需要一句代码:
dsIn>>m_data;
最后我们调用 UpdateDataShow() 更新显示界面,并弹信息框说明加载完成。

例子代码讲解到这,我们生成项目并运行,添加 AA 、BB、CC 三个人员信息:
add
可见三个人员顺序乱的,这是QHash的特性,元素不按照字典序,也不按照数值大小排列,看起来没有排序。
我们点击“保存数据”按钮,将数据保存到文件:
save
然后我们删除三个元素,然后点击“加载数据”按钮,选择之前保存的文件,加载后显示:
load
这样我们删除的内容,通过加载文件,又全读取回来了,使用就非常方便。其他按钮功能请读者自行测试,下面小节我们讲解多哈希映射内容。

9.4.2 多哈希映射 QMultiHash

QMultiHash 是 QHash 的派生类,继承了 QHash 绝大多数的函数,同时也根据一对多映射的特性做了改进,将基类的函数进行了重载。除了基类的函数,QMultiHash 新增了一些函数:
(1)构造函数
QMultiHash()    //默认构造函数
QMultiHash(std::initializer_list<std::pair<Key, T> > list)    //初始化列表构造函数
QMultiHash(const QHash<Key, T> & other)    //复制构造函数
第一个是不带任何参数的默认构造函数,第二个是支持C++11特性的初始化列表函数,类似下面代码:
    QMultiHash<QString, int> ha1{
        {"Alice", 10086},
        {"Alice", 10087},
        {"Bob", 10010},
        {"Bob", 10011}
    };
    qDebug()<<ha1;
第三个是复制构造函数,可以从已有对象新建一个内容一样的对象。
(2)添加函数
QHash<Key, T>::iterator    insert(const Key & key, const T & value)
QMultiHash 使用的迭代器与基类一样,只是有些函数功能有差异,这个 insert() 函数就是最典型的差异。
基类 QHash 的插入函数是一对一映射,如果已经有了同样 key 的元素,那么仅修改 value 值,key 对应的 value 只有一个。
派生类 QMultiHash  的插入函数是总是新增新元素,即使旧的 key-value 元素一模一样,调用 QMultiHash  的插入函数仍然会新增元素,比如:
    QMultiHash<QString, int> ha1;
    ha1.insert( "AA", 1 );
    ha1.insert( "AA", 1 );
    ha1.insert( "AA", 1 );
    qDebug()<<ha1;
三句插入函数代码中的 key - value 一模一样,多哈希映射会自动添加三个元素,而不管他们相不相等,打印结果就是:
QHash(("AA", 1)("AA", 1)("AA", 1))

总共有 3 个元素,内容一样。
如果是基类 QHash 调用 insert 插入函数,那么一个 key 仅有一个元素,只对应一个 value。
(3)删除函数
int    remove(const Key & key, const T & value)
int    remove(const Key & key)
第一个删除函数,只删除同时匹配 key 和 value 的元素,如果有多个匹配就删除多个元素,返回删除的个数;如果没有匹配的返回 0。
第二个删除函数,删除匹配 key  的所有元素,返回值是删除的元素个数,如果没有匹配的 key,返回 0。
(4)访问和查询函数
count 计数的函数有三个:
int    count(const Key & key, const T & value) const
int    count(const Key & key) const
int    count() const
第一个统计同时匹配 key-value 的元素个数,第二个统计匹配 key 的元素个数,最后一个是统计所有元素个数。
contains 包含查询有两个函数:
bool    contains(const Key & key, const T & value) const
bool    contains(const Key & key) const
第一个检查是否包含同时匹配 key-value 的元素,第二个检查是否包含匹配 key 的元素。
find 查找函数共有 6 个,首先是根据 key-value 对查找元素位置,3个函数:
QHash<Key, T>::const_iterator    constFind(const Key & key, const T & value) const   //只读迭代器查询,Qt风格函数名
QHash<Key, T>::const_iterator    find(const Key & key, const T & value) const    //只读迭代器查询,STL风格函数名
QHash<Key, T>::iterator    find(const Key & key, const T & value)    //读写迭代器查询
然后是根据 key 查询元素位置,3个函数:
QHash<Key, T>::const_iterator    constFind(const Key & key) const    //只读迭代器查询,Qt风格函数名
QHash<Key, T>::const_iterator    find(const Key & key) const    //只读迭代器查询,STL风格函数名
QHash<Key, T>::iterator    find(const Key & key)    //读写迭代器查询
(5)替换和交换函数
多哈希映射的元素替换函数如下:
QHash<Key, T>::iterator    replace(const Key & key, const T & value)
如果对象不包含 key 键元素,那么新增一个 key-value 元素;如果存在已有的同样 key 元素,那么替换掉旧的 value 值;如果存在多个匹配 key 的元素,那么替换掉最近添加的一个匹配 key 元素。
多哈希映射交换函数如下:
void    swap(QMultiHash<Key, T> & other)
该函数交换数据的效率高,并且不会失败。
(6)运算符函数
多哈希映射新增了 + 和 += 运算符函数,用于合并两个多哈希映射:
QMultiHash    operator+(const QMultiHash & other) const
QMultiHash &    operator+=(const QMultiHash & other)
+ 函数返回新的合并后对象, += 函数直接将合并后的对象赋给左值对象。合并后的对象总是合并前两个对象元素个数的总和,而不会检查有没有重复的元素,元素有重复就重复添加。
另外 QMultiHash 取消了 operator[] 运算符函数,由于多映射的 key 很可能对应多个 value,同样 key 的多个节点定位不明确,所以不能用 operator[] 运算符函数。替换之前最新插入的键为 key 的节点使用 replace() 函数。

QHash 和 QMultiHash 二者功能函数的主要区别对比如下表所示:

功能 QHash 函数 QMultiHash 函数
一对一添加节点 insert(key,value):无匹配key时直接插入新节点,有匹配key时替换旧节点。 replace(key,value):无匹配key时直接插入新节点,有匹配key时,替换之前最新插入的同样key节点。
一对多添加节点 insertMulti(key,value):直接将新节点插入到哈希表,不考虑之前有无同样键值的节点。 insert(key,value):直接将新节点插入到哈希表,不考虑之前有无同样键值的节点。
insertMulti(key,value)函数同基类。
中括号运算符 operator[](key):根据key读写匹配的节点,如果没有匹配的,自动添加该 key 节点。 没有中括号运算符,对于类似功能,读操作调用 value(key)函数,写操作调用replace(key,value)。
合并两个对象 无 + 和 += 运算符函数。QHash::​unite(other)可以将参数other所有节点添加给自己,类似 += 功能。 通过 + 和 += 运算符函数。
查询函数 count(key)、contains(key)、find(key)、constFind(key),只需要通过 key 查询节点,因为通常是一对一映射。 不仅有 count(key)、contains(key)、find(key)、constFind(key),一对多映射查询时还可以根据键值对进行查询
count(key,value)、contains(key,value)、find(key,value)、constFind(key,value)。
删除函数 remove(key),删除匹配 key 的节点。 两个删除函数,remove(key)删除匹配 key 的所有节点,remove(key,value)删除匹配 key-value 的所有节点。

需要特别注意的就是 insert() 函数,基类 QHash 和 派生类 QMultiHash 的 insert() 函数名一样,功能却不一样,基类 QHash 是一对一添加或替换,而派生类 QMultiHash 是一对多的重复添加。

本小节例子作为练习题,将 9.3.2 多映射 QMultiMap 小节的 namephone 例子,用本小节的 QMultiHash 实现。

9.4.3 集合 QSet

集合 QSet 类其实相当于去掉 value ,仅有 key 的哈希类,它存储的元素就是哈希类的 key 类型,要求是可赋值类型,并且带有全局的 operator==() 和 qHash() 函数。QSet 的元素要求唯一不重复,排列顺序则是无序的。下面介绍集合类的功能函数。

(1)构造函数
QSet()   //默认构造函数
QSet(std::initializer_list<T> list)    //初始化列表构造函数,C++11特性
QSet(const QSet<T> & other)    //复制构造函数
QSet(QSet && other)     //移动构造函数,C++11特性
最常用的是默认构造函数,使用模板类要带上数值类型,第二个和第四个是C++11特性,举例如下:
    QSet<QString> s1{"Alice", "Bob", "Ceil"};
    qDebug()<<s1;
    QSet<QString> s2 = std::move(s1);
    qDebug()<<s1;
    qDebug()<<s2;
输出结果如下:
QSet("Bob", "Alice", "Ceil")
QSet()
QSet("Bob", "Alice", "Ceil")
移动构造函数会将右边的对象内容移动给左值对象,右边对象清空。

(2)添加函数
iterator    insert(const T & value)
insert() 会检查集合是否存在相同元素,如果不存在相同的,添加新元素,如果已经有相同的,集合保持不变。与之前的 QMap 和 QHash 类不同的是,集合类没有 insertMulti 函数,因为集合要求元素唯一不重复。

(3)删除函数
bool    remove(const T & value)
remove() 删除匹配数值的元素,如果集合中存在该元素,那么删除了并返回 true,如果没有匹配元素,那么返回 false。
如果希望清空所有元素,使用如下函数:
void    clear()

(4)访问和查询函数
查询集合是否包含一个数值:
bool    contains(const T & value) const
如果集合存在数值,返回 true,不存在就返回 false。
查询集合中元素的总数:
int    count() const
int    size() const
注意集合没有统计匹配数值个数的 count 函数,因为存在是 1,不存在是 0 ,有 contains 就能够判断了,不想要单独的计数函数。
查询集合是否为空:
bool    empty() const    //STL风格命名
bool    isEmpty() const   //Qt风格命名
获取集合所有的元素使用下面两个函数:
QList<T>    values() const
QList<T>    toList() const
这两个函数是等价的,因为集合存储单值元素,而不是键值对。
集合有静态函数,根据列表构建集合,可以实现去重复的功能:
QSet<T>    fromList(const QList<T> & list)
fromList() 静态函数根据参数的列表构造一个新集合返回,新集合中元素值是唯一的,可以快速去重复。

(5)数学集合函数
并集 unite :
QSet<T> &    unite(const QSet<T> & other)
同 operator|=() ,将两个集合求并集,将并集存到调用该函数的对象中。
交集 intersect :
QSet<T> &    intersect(const QSet<T> & other)
同 operator&=(),将两个集合求交集,并将交集存到调用该函数的对象中。
差集 subtract:
QSet<T> &    subtract(const QSet<T> & other)
同 operator-=(),计算 *this 集合对象减去 other 集合对象的差集,差集部分存到 *this 对象中。差集就是 *this 对象去掉交集的部分。
包含关系 contains:
bool    contains(const QSet<T> & other) const
计算 *this 对象是否包含 other 集合对象中的所有元素,如果包含所有 other 内部元素,那么返回 true,否则返回 false。
举例如下:
    QSet<int> s1{1,2,3};
    QSet<int> s2{3,4,5};
    s1.unite( s2 );
    qDebug()<<s1;

    QSet<int> s3{1,2,3};
    s3.intersect( s2 );
    qDebug()<<s3;

    QSet<int> s4{1,2,3};
    s4.subtract( s2 );
    qDebug()<<s4;

    QSet<int> s5{1,2,3,4,5};
    qDebug()<<s5.contains( s2 );
其输出如下:
QSet(1, 4, 5, 2, 3)
QSet(3)
QSet(1, 2)
true
由于集合采用哈希表实现,所以数值排列是无序的。

(6)运算符函数
运算符函数包括更多的集合操作,我们这里以 s1={1, 2, 3} ,s2={3, 4, 5} ,s3={}  三个集合举例,在下面进行运算符举例:

运算符函数 举 例 描述
bool operator!=(const QSet<T> & other) const  s1 != s2; 两个映射的元素不一样,不等号判断结果为 true。
QSet<T> operator&(const QSet<T> & other) const  s3 = s1 & s2; s3 为交集 {3},s1和s2不变。
QSet<T> & operator&=(const QSet<T> & other)  s1 &= s2; s1 为交集 {3},s2不变。
QSet<T> & operator&=(const T & value)  s1 &= 1; s1 和单个数值求交集,s1变为 {1}。
QSet<T> operator+(const QSet<T> & other) const  s3 = s1 + s2; s3 为并集{1,2,3,4,5},s1和s2不变。
QSet<T> & operator+=(const QSet<T> & other)  s1 += s2; s1 为并集{1,2,3,4,5},s2不变。
QSet<T> & operator+=(const T & value)  s1 += 8; s1 为合并一个数值的新集合 {1,2,3,8}。
QSet<T> operator-(const QSet<T> & other) const  s3 = s1 - s2; s3 为差集{1,2},s1和s2不变。s3 等同于 s1 - (s1&s2) 。
QSet<T> & operator-=(const QSet<T> & other)  s1 -= s2; s1 为差集{1,2},s2不变。
QSet<T> & operator-=(const T & value)  s1 -= 1; s1 为{2,3},去掉右边单个数值。
QSet<T> & operator<<(const T & value)  s1 << 8; 添加一个数值给 s1,s1变成{1,2,3,8}。
QSet<T> & operator=(const QSet<T> & other)  s3 = s1; 赋值,s3变成 {1,2,3},s1不变。
QSet<T> & operator=(QSet<T> && other)  s3 = std::move(s1); 移动赋值,s3变成 {1,2,3},s1变为空集合。
bool operator==(const QSet<T> & other) const  s1 == s2; 结果为 false,两个集合不一样。
QSet<T> operator|(const QSet<T> & other) const  s3 = s1 | s2; s3 为并集{1,2,3,4,5},s1和s2不变。
QSet<T> & operator|=(const QSet<T> & other)  s1 |= s2; s1 为并集{1,2,3,4,5},s2不变。
QSet<T> & operator|=(const T & value)  s1 |= 8; s1 为合并一个数值的新集合 {1,2,3,8}。

(7)迭代器函数
集合类定义了 STL 风格和 Qt 命名风格的迭代器:
class    const_iterator  //STL风格只读迭代器
class    iterator            //STL风格读写迭代器
typedef    ConstIterator  //Qt命名风格只读迭代器
typedef    Iterator          //Qt命名风格读写迭代器
STL 风格迭代器使用示范:
QSet<QString>::const_iterator i = set.constBegin();
while (i != set.constEnd()) {
    qDebug() << *i;
    ++i;
}
获取集合的头部和尾部迭代器的函数列举如下:
iterator    begin()     //指向头部的读写迭代器
const_iterator    begin() const            //指向头部的只读迭代器
const_iterator    cbegin() const          //指向头部的只读迭代器
const_iterator    constBegin() const  //指向头部的只读迭代器,Qt风格
iterator    end()       //指向尾部后面假想元素的读写迭代器
const_iterator    end() const             //指向尾部后面假想元素的只读迭代器
const_iterator    cend() const           //指向尾部后面假想元素的只读迭代器
const_iterator    constEnd() const    //指向尾部后面假想元素的只读迭代器,Qt风格
注意 *end() 返回的迭代器通常只用来做不等于判断,它指向的东西根本不存在, *end() 仅用于越界判断。
虽然获取头部、尾部迭代器的函数多,其实功能类似,起了一堆名字是方便兼容 STL 风格函数命名。

查询数值的迭代器位置:
const_iterator    constFind(const T & value) const  //只读迭代器查询,Qt风格命名
const_iterator    find(const T & value) const    //只读迭代器查询,STL风格命名
iterator    find(const T & value)   //读写迭代器查询
三个查找函数如果找到匹配数值,返回指向该数值的迭代器,否则返回末尾空的迭代器。

另外,根据迭代器位置删除元素的函数:
iterator    erase(iterator pos)
erase() 函数删除时,不会导致内部哈希表的重构,因此可以在迭代遍历集合元素时,安全地调用 erase() 删除指定位置的元素,各个元素的哈希表位置不会错乱。而 remove() 函数会可能导致内部哈希表重构,所以不要在迭代过程中使用 remove() 函数删除元素,哈希表重构会导致迭代器失效。

(8)其他内容
集合类内部的存储空间默认是自动控制增长的,如果预先知道元素个数,那么可以提前分配内存空间:
void    reserve(int size)
reserve() 提前分配 size 大小的空间位置,用于预留内存空间。查询预留空间大小,使用如下函数:
int    capacity() const
如果确定不再添加新元素,要把预留的内存空间释放了,不再预留,那么使用下面函数:
void    squeeze()
交换两个集合内容,使用下面函数:
void    swap(QSet<T> & other)   //交换函数效率很高,并且不会失败
QSet集合类也支持串行化输入输出,前提是存储的数值类型也支持串行化:
QDataStream &    operator<<(QDataStream & out, const QSet<T> & set)
QDataStream &    operator>>(QDataStream & in, QSet<T> & set)

集合类内容介绍到这,下面开始编写一个集合类应用的例子。例子是五个投票人从三个候选人中投票选举武林盟主和副盟主,每个投票人可以投两个候选人,得票最多的是盟主,得票第二的是副盟主。我们编写程序统计一些信息。
我们打开 QtCreator,新建一个 Qt Widgets Application 项目,在新建项目的向导里填写:
①项目名称 voteset,创建路径 D:\QtProjects\ch09,点击下一步;
②套件选择里面选择全部套件,点击下一步;
③基类选择 QWidget,点击下一步;
④项目管理不修改,点击完成。
打开 widget.ui 文件进入图形化编辑界面,构造界面如下图所示:
ui
界面第一行是一个标签“投票数据(每人可以投2票)”。
第二行是一个列表控件 listWidget 。
第三行是两个按钮,“统计投票人”按钮 pushButtonGetVoters,“统计候选人”按钮 pushButtonGetCandidates,两个按钮使用水平布局排列。
第四行是“统计同时选择张三和狗哥的投票人”按钮 pushButtonGetIntersect。
第五行是“统计选择张三或狗哥的投票人”按钮 pushButtonGetUnite。
最后一行是文本浏览框 textBrowser 。
窗口整体使用垂直布局器排列,窗口大小 400*550 。
界面布局好之后,我们依次右击四个按钮,添加各个按钮 clicked() 信号对应的槽函数。
四个按钮槽函数添加后,我们打开头文件 widget.h 头文件,编辑内容如下:
#ifndef WIDGET_H
#define WIDGET_H

#include <QWidget>
#include <QMultiHash>
#include <QSet>

namespace Ui {
class Widget;
}

class Widget : public QWidget
{
    Q_OBJECT

public:
    explicit Widget(QWidget *parent = 0);
    ~Widget();

private slots:
    void on_pushButtonGetVoters_clicked();

    void on_pushButtonGetCandidates_clicked();

    void on_pushButtonGetIntersect_clicked();

    void on_pushButtonGetUnite_clicked();

private:
    Ui::Widget *ui;
    //保存投票
    QMultiHash<QString, QString> m_voteData;
    //填充投票,并设置列表框显示
    void FillDataAndListWidget();

};

#endif // WIDGET_H
我们添加 QMultiHash、QSet 头文件包含,然后为窗口类手动添加了成员变量 m_voteData,保存投票数据,添加 FillDataAndListWidget() 函数,用于填充投票数据,并显示到界面列表框。其他代码是之前自动生成的,包括四个按钮对应的槽函数。
接下来我们分块讲解 widget.cpp 源文件的内容,首先是开头构造函数部分:
#include "widget.h"
#include "ui_widget.h"
#include <QMessageBox>
#include <QDebug>

Widget::Widget(QWidget *parent) :
    QWidget(parent),
    ui(new Ui::Widget)
{
    ui->setupUi(this);

    //填充投票,并设置列表框显示
    FillDataAndListWidget();
}

void Widget::FillDataAndListWidget()
{
    m_voteData.insert( tr("路人甲"), tr("张三") );
    m_voteData.insert( tr("路人甲"), tr("狗哥") );
    m_voteData.insert( tr("路人乙"), tr("李四") );
    m_voteData.insert( tr("路人乙"), tr("狗哥") );
    m_voteData.insert( tr("路人丙"), tr("张三") );
    m_voteData.insert( tr("路人丙"), tr("狗哥") );
    m_voteData.insert( tr("路人丁"), tr("李四") );
    m_voteData.insert( tr("路人丁"), tr("狗哥") );
    m_voteData.insert( tr("路人戊"), tr("张三") );
    m_voteData.insert( tr("路人戊"), tr("狗哥") );
    //显示到列表控件
    ui->listWidget->clear();
    //使用迭代器遍历
    QHash<QString, QString>::const_iterator it = m_voteData.constBegin();
    while ( it != m_voteData.constEnd() )
    {
        QString strLine = it.key() + tr("\t投\t") + it.value();
        ui->listWidget->addItem( strLine );
        ++it;
    }
}

Widget::~Widget()
{
    delete ui;
}
我们在构造函数里面调用了 FillDataAndListWidget()  函数,这个函数首先为 m_voteData 对象添加了五个路人的投票,每人 2 票,共有 10 票。
然后清空列表控件,使用迭代器遍历 m_voteData 对象,将容器里每个元素组成一行文本,显示为列表框的一个条目。

接着我们编辑“统计投票人”按钮对应的槽函数:
//统计投票人,不重复的
void Widget::on_pushButtonGetVoters_clicked()
{
    //投票人是 keys
    QList<QString> listVoters = m_voteData.keys();
    //用集合去重复
    QSet<QString> uniqueVoters = QSet<QString>::fromList( listVoters );
    //可以转回列表
    listVoters = uniqueVoters.toList();
    //构造信息字符串
    int nCount = listVoters.count();
    QString strInfo = tr("投票人数:%1 \r\n").arg(nCount);
    for(int i=0; i<nCount; i++)
    {
        strInfo += listVoters[i] + tr("\r\n");
    }
    //显示
    ui->textBrowser->setText( strInfo );
}
我们先获取 m_voteData 对象所有的 keys 存到 listVoters,注意是 5 个人投 10 票,所以投票人会重复,因此我们调用集合类的静态函数
 QSet<QString>::fromList( listVoters )
根据列表构造一个元素不重复的集合,存到 uniqueVoters 对象,然后将投票人集合再转回列表,存到 listVoters ,这样就实现了去重复人名。
然后我们构造信息字符串,把人数和人名都添加到信息字符串,显示到 ui->textBrowser 控件。

接下来我们编辑“统计候选人”按钮对应的槽函数:
//统计候选人,不重复的
void Widget::on_pushButtonGetCandidates_clicked()
{
    //候选人是 values
    QList<QString> listCandidates = m_voteData.values();
    //用集合去重复
    QSet<QString> uniqueCandidates = QSet<QString>::fromList( listCandidates );
    //转回列表
    listCandidates = uniqueCandidates.toList();
    //构造信息字符串
    int nCount = listCandidates.count();
    QString strInfo = tr("候选人数:%1 \r\n").arg(nCount);
    for(int i=0; i<nCount; i++)
    {
        strInfo += listCandidates[i] + tr("\r\n");
    }
    //显示
    ui->textBrowser->setText( strInfo );
}
选举时,3 个候选人加起来被投了 10 票,所以也一定是重复的,我们类似地,获取 m_voteData 对象的所有 values,也是用集合类中转处理,实现去重复,最后将不重复的候选人名单存到 listCandidates,然后根据候选人数和人名构造信息字符串,显示到 ui->textBrowser 控件。

接下来我们编辑“统计同时选择张三和狗哥的投票人”按钮对应的槽函数:
//统计同时选择张三和狗哥的投票人
void Widget::on_pushButtonGetIntersect_clicked()
{
    QSet<QString> voteZhangSan;
    QSet<QString> voteGouGe;
    //使用迭代器遍历
    QHash<QString, QString>::const_iterator it = m_voteData.constBegin();
    while ( it != m_voteData.constEnd() )
    {
        if( it.value() == tr("张三") )
        {
            voteZhangSan<<it.key();
        }
        if( it.value() == tr("狗哥") )
        {
            voteGouGe<<it.key();
        }
        ++it;
    }
    //张三的投票人集合,与狗哥的投票人集合 求交集
    QSet<QString> sIntersect = voteZhangSan & voteGouGe;
    QStringList listIntersect = sIntersect.toList();
    //构造信息字符串
    QString strInfo = tr("同时选择张三和狗哥的投票人数:%1 \r\n").arg(listIntersect.count());
    strInfo += listIntersect.join( "\r\n" );
    //显示
    ui->textBrowser->setText( strInfo );
}
我们定义两个集合,voteZhangSan 保存投张三的投票人,voteGouGe 保存投狗哥的投票人;
使用迭代器遍历,凡是投张三的存到 voteZhangSan ,投狗哥的存到 voteGouGe;
然后我们求出 voteZhangSan 和  voteGouGe 的交集,存到 sIntersect ,这样就得出同时投张三和狗哥的投票人。
我们将 sIntersect 转为 QList<QString>,然后存到 QStringList 对象 listIntersect 里面,
QList<QString> 转到 QStringList 这个转换过程是自动的,因为 QStringList 类定义了转换的构造函数和赋值函数;
然后我们根据交集信息构造字符串,在显示人名时,使用了 QStringList  的 join() 函数,可以方便地使用分隔字符拼接 QStringList 对象内部多个字符串,形成一个拼接后的完整字符串。最后显示到文本浏览框 ui->textBrowser 。

最后我们编辑 “统计选择张三或狗哥的投票人”按钮对应的槽函数:
//统计选择张三或狗哥的投票人
void Widget::on_pushButtonGetUnite_clicked()
{
    QSet<QString> voteZhangSan;
    QSet<QString> voteGouGe;
    //使用迭代器遍历
    QHash<QString, QString>::const_iterator it = m_voteData.constBegin();
    while ( it != m_voteData.constEnd() )
    {
        if( it.value() == tr("张三") )
        {
            voteZhangSan<<it.key();
        }
        if( it.value() == tr("狗哥") )
        {
            voteGouGe<<it.key();
        }
        ++it;
    }
    //张三的投票人集合,与狗哥的投票人集合 求并集
    QSet<QString> sUnite = voteZhangSan | voteGouGe;
    QStringList listUnite = sUnite.toList();
    //构造信息字符串
    QString strInfo = tr("选择张三或狗哥的投票人数:%1 \r\n").arg(listUnite.count());
    strInfo += listUnite.join( "\r\n" );
    //显示
    ui->textBrowser->setText( strInfo );
}
这个函数代码和上一个求交集函数的代码很类似,遍历 m_voteData 元素,将投张三的投票人存到 voteZhangSan,将投狗哥的投票人存到 voteGouGe,对两个集合求并集就得到投张三或狗哥的人员名单,然后构造信息字符串,显示到文本浏览框 ui->textBrowser 。
示例代码介绍到这,我们生成项目,运行程序,点击“统计同时选择张三和狗哥的投票人”按钮,可以看到如下结果:
run1
其他功能按钮请读者自行测试,另外,统计武林盟主和副盟主的功能作为练习,请读者自行实现。

9.4.4 关联容器对比

9.3 节和 9.4 节内容介绍了 QMap、QMultiMap、QHash、QMultiHash、QSet 五种容器,前两种是红黑树实现,后三种是哈希表实现。他们的 key 查询和元素插入的时间复杂度如下表所示:

容器类型 key 查询平均时间 key 查询最坏时间 元素插入平均时间 元素插入最坏时间
QMap / QMultiMap O(log n) O(log n) O(log n) O(log n)
QHash / QMultiHash Amort. O(1) O(n) Amort. O(1) O(n)
QSet Amort. O(1) O(n) Amort. O(1) O(n)

表格中 Amort. 是 amortized behavior 的缩写,即均摊行为。以 Amort. O(1) 为例,如果程序仅执行一次操作,那么有可能是 O(n) 时间,但是如果执行很多次该操作,那么很多次平均分摊下来,平均的时间是 O(1) 。
从上面表格可以看到红黑树的 QMap、QMultiMap 性能是最稳定的,最坏情况也是 O(log n) 时间。
基于哈希表的 QHash、QMultiHash、QSet 大部分情况效率很高,当然如果遇到最坏情况就是遍历所有元素。
红黑树是排序的,而哈希表是乱序的,这些容器都可以存储数据,要根据实际的应用需求,选择最合适的容器来使用。

如果有排序需求,那么肯定是选择 QMap、QMultiMap 合适;如果不需要排序,那么 QHash、QMultiHash 也是很好的选择;如果需要去重复,保证元素唯一性,需要求交集、并集、差集这些功能,那么集合 QSet 就很实用。下面我们通过例子测试对比关联容器的访问效率。
我们打开 QtCreator,新建一个 Qt Widgets Application 项目,在新建项目的向导里填写:
①项目名称 associativetest,创建路径 D:\QtProjects\ch09,点击下一步;
②套件选择里面选择全部套件,点击下一步;
③基类选择 QWidget,点击下一步;
④项目管理不修改,点击完成。
我们先打开 associativetest.pro 项目文件,末尾添加一行:
CONFIG += c++11
保存该文件,这样就能启用 C++11 新特性。
打开 widget.ui 文件进入图形化编辑界面,构造界面如下图所示:
ui
界面第一行是一个表格控件 tableWidget;
第二行是 “执行次数”标签、旋钮编辑框 spinBoxTimes、“添加元素”按钮 pushButtonInsert、“随机访问”按钮 pushButtonFind ,第二行控件使用水平布局器排列。
窗口整体使用垂直布局器,窗口大小 550*400 。
设置布局后,我们依次右击两个按钮,在右键菜单添加 clicked() 信号的槽函数。
下面我们开始编辑 头文件 widget.h 的代码:
#ifndef WIDGET_H
#define WIDGET_H

#include <QWidget>
#include <QMap>
#include <QHash>
#include <QSet>
#include <QElapsedTimer> //计时器
#include <QLocale> //本地化类,用于打印逗号分隔的数字

namespace Ui {
class Widget;
}

class Widget : public QWidget
{
    Q_OBJECT

public:
    explicit Widget(QWidget *parent = 0);
    ~Widget();

private slots:
    void on_pushButtonInsert_clicked();

    void on_pushButtonFind_clicked();

private:
    Ui::Widget *ui;
    //容器对象
    QMap<int, int>  m_map;
    QHash<int, int> m_hash;
    QSet<int>  m_set;
    //耗费计时器
    QElapsedTimer m_calcTimer;
    //本地化对象,用于打印逗号分隔的数字
    QLocale m_locale;
};

#endif // WIDGET_H
在开头添加 QMap、QHash、QSet 三个模板类的头文件包含,然后添加计时器类 QElapsedTimer 、本地化类 QLocale 的头文件包含。
窗口类里面构造函数、析构函数、两个槽函数都是自动生成的。
我们手动添加三个容器对象,分别是 m_map、m_hash、m_set,
然后定义计时器对象 m_calcTimer,本地化类对象 m_locale。

接下来我们分块编辑 widget.cpp 文件的代码,首先是构造函数内容:
#include "widget.h"
#include "ui_widget.h"
#include <QMessageBox>
#include <QDebug>
#include <random>
using namespace std;

Widget::Widget(QWidget *parent) :
    QWidget(parent),
    ui(new Ui::Widget)
{
    ui->setupUi(this);
    //窗口标题栏
    setWindowTitle( tr("关联容器测试,时间单位:纳秒") );

    //设置表格列数
    ui->tableWidget->setColumnCount( 4 );
    //设置表头
    QStringList header;
    header<<tr("操作名称")<<tr("QMap")<<tr("QHash")<<tr("QSet");
    ui->tableWidget->setHorizontalHeaderLabels( header );
    //各列均匀拉伸
    ui->tableWidget->horizontalHeader()->setSectionResizeMode( QHeaderView::Stretch );

    //设置旋钮编辑框
    ui->spinBoxTimes->setSuffix( tr(" 万") ); // 单位万
    ui->spinBoxTimes->setRange( 1, 21*10000 ); //21亿上限
    //设置英语本地化,每三个数字打逗号
    m_locale = QLocale(QLocale::English, QLocale::UnitedStates);
    qDebug()<<m_locale.toString( 1234567 );

}

Widget::~Widget()
{
    delete ui;
}
我们在构造函数里设置窗口标题文本,说明测试的时间单位是纳秒。
设置表格控件共有 4 列,并设置表头的 4 列内容,然后设置表头对象的自动拉伸模式为均匀拉伸。
设置旋钮编辑框的数字单位是 万 ,并设置数字的范围 1 万到 21 亿,就是接近整数上限。
然后设置本地化对象 m_locale 为英文模式,这样显示数字就是每隔 3 个数字打个英文逗号,比如 "1,234,567" 。

接下来我们编辑“添加元素”按钮对应的槽函数:
//添加元素功能测试
void Widget::on_pushButtonInsert_clicked()
{
    //获取测试次数
    int nTimes = ui->spinBoxTimes->value() * 10000;
    //表格控件添加新行
    int nNewRow = ui->tableWidget->rowCount(); //作为新行序号
    ui->tableWidget->setRowCount( nNewRow+1 ); //增加一行
    //设置第 0 列文本
    QString strText = tr("添加元素 %1 万次").arg( ui->spinBoxTimes->value() );
    QTableWidgetItem *itemNew = new QTableWidgetItem( strText );
    ui->tableWidget->setItem(nNewRow, 0, itemNew);

    //C++11特性,定义随机数均匀分布、随机数引擎
    uniform_int_distribution<unsigned> ud(0, nTimes);
    default_random_engine eg;
    //QMap测试
    m_map.clear();
    qint64 nsUsed = 0; //纳秒计数,耗时包含了随机数产生时间
    //开始计时
    m_calcTimer.start();
    for(int i=0; i<nTimes; i++)
    {
        int nVal = ud(eg);
        m_map.insert(nVal, nVal);
    }
    nsUsed = m_calcTimer.nsecsElapsed();
    //设置文本并新建表格条目
    strText = m_locale.toString( nsUsed );
    itemNew = new QTableWidgetItem( strText );
    ui->tableWidget->setItem( nNewRow, 1, itemNew );

    //QHash测试
    m_hash.clear(); //清空旧的
    nsUsed = 0;
    //开始计时
    m_calcTimer.start();
    for(int i=0; i<nTimes; i++)
    {
        int nVal = ud(eg);
        m_hash.insert(nVal, nVal);
    }
    nsUsed = m_calcTimer.nsecsElapsed();
    //设置文本并新建表格条目
    strText = m_locale.toString( nsUsed );
    itemNew = new QTableWidgetItem( strText );
    ui->tableWidget->setItem( nNewRow, 2, itemNew );

    //QSet测试
    m_set.clear(); //清空旧的
    nsUsed = 0;
    //开始计时
    m_calcTimer.start();
    for(int i=0; i<nTimes; i++)
    {
        int nVal = ud(eg);
        m_set.insert( nVal );
    }
    nsUsed = m_calcTimer.nsecsElapsed();
    //设置文本并新建条目
    strText = m_locale.toString( nsUsed );
    itemNew = new QTableWidgetItem( strText );
    ui->tableWidget->setItem( nNewRow, 3, itemNew );
}
该函数先获取要测试的次数,将旋钮编辑框的数字乘以 10000,就是实际测试次数;
获取表格控件现有的行数,将该数字作为新建的行序号,然后为表格增加一个新行,序号 nNewRow;
设置新行的第 0 列文本,就是测试内容和次数的文本。

然后使用 C++11新的随机数功能,先定一个随机数分布对象 ud(0, nTimes),0是生成随机数的下限,nTimes 是随机数的上限;
定义默认的随机数生成引擎 eg;C++11的随机数可以指定生成随机数的范围,可以生成指定类型指定范围内的随机数,
而 Windows 系统默认的 RAND_MAX 只有 32767,通常是不够用的,所以推荐使用 C++11 的随机数类型。

然后我们依次测试 m_map、m_hash、m_set 的执行效率,三种容器的测试代码结构完全类似,以第一个 m_map 为例:
清空旧的 m_map 内容,将 nsUsed 纳秒时间设置为 0;
开始 m_calcTimer 计时器,然后循环 nTimes 次数,每次执行生成随机数 ud(eg) 存到 nVal,然后添加给 m_map 对象,key-value的内容一样;
然后使用计时器的 nsecsElapsed() 函数获取纳秒计数存到 nsUsed;
然后将 nsUsed 数值 转为英语本地化文本,根据文本构造表格的单元条目,添加到表格列中。
三种容器的测试过程一样,结果各自显示到新行的第 1、2、3列,即完成测试。

最后我们编辑“随机访问”按钮对应的槽函数:
//随机访问功能测试
void Widget::on_pushButtonFind_clicked()
{
    //检查是否为空
    if( m_map.isEmpty() || m_hash.isEmpty() || m_set.isEmpty() )
    {
        QMessageBox::warning(this, tr("随机访问"), tr("容器对象为空,请执行添加元素后执行访问!"));
        return;
    }
    //获取测试次数
    int nTimes = ui->spinBoxTimes->value() * 10000;
    //表格控件增加一行
    int nNewRow = ui->tableWidget->rowCount(); //新行的序号
    ui->tableWidget->setRowCount( nNewRow+1 ); //加一行
    //设置第 0 列文本
    QString strText = tr("随机访问 %1 万次").arg( ui->spinBoxTimes->value() );
    QTableWidgetItem *itemNew = new QTableWidgetItem( strText );
    ui->tableWidget->setItem( nNewRow, 0, itemNew );

    //C++11特性,定义随机数均匀分布、随机数引擎
    uniform_int_distribution<unsigned> ud(0, nTimes);
    default_random_engine eg;

    //QMap测试
    qint64 nsUsed = 0; //纳秒计数,耗时包含了随机数产生时间
    //开始计时
    m_calcTimer.start();
    for(int i=0; i<nTimes; i++)
    {
        int nVal = ud(eg);
        m_map.find( nVal );
    }
    nsUsed = m_calcTimer.nsecsElapsed();
    //设置文本并新建表格条目
    strText = m_locale.toString( nsUsed );
    itemNew = new QTableWidgetItem( strText );
    ui->tableWidget->setItem( nNewRow, 1, itemNew );

    //QHash测试
    nsUsed = 0;
    //开始计时
    m_calcTimer.start();
    for(int i=0; i<nTimes; i++)
    {
        int nVal = ud(eg);
        m_hash.find(nVal);
    }
    nsUsed = m_calcTimer.nsecsElapsed();
    //设置文本并新建表格条目
    strText = m_locale.toString( nsUsed );
    itemNew = new QTableWidgetItem( strText );
    ui->tableWidget->setItem( nNewRow, 2, itemNew );

    //QSet测试
    nsUsed = 0;
    //开始计时
    m_calcTimer.start();
    for(int i=0; i<nTimes; i++)
    {
        int nVal = ud(eg);
        m_set.find( nVal );
    }
    nsUsed = m_calcTimer.nsecsElapsed();
    //设置文本并新建条目
    strText = m_locale.toString( nsUsed );
    itemNew = new QTableWidgetItem( strText );
    ui->tableWidget->setItem( nNewRow, 3, itemNew );
}
该函数先检查 m_map、m_hash、m_set 三个对象的内容,如果有一个为空就提示,需要在添加元素之后再测试随机访问功能,提示后返回;
如果三个容器对象都有内容,进行后续测试。
获取测试计数,将旋钮编辑框的数值乘以 10000,就是真实的测试次数;
为表格增加一个新行,新行序号是 nNewRow;
设置新行第 0 列的文本,就是测试功能的文本和次数;
然后定义随机数分布对象 ud、随机数引擎 eg;然后开始三类容器对象的测试过程,这三类对象的测试代码结构完全类似,
以 m_map 为例,将 nsUsed 纳秒计数设置为 0;
开始计时器,然后循环 nTimes 次数,每次生成随机数存到 nVal,然后使用 find() 函数查找该关键字内容;
循环完成后获取纳秒计数存到 nsUsed;
将纳秒计数转为英文本地化字符串,根据字符串构建表格控件的单元格条目,设置给表格控件的最新行。
三种容器对象的测试结果分别显示到表格新行的第 1、2、3 列中。
例子代码讲解到这,我们生成该项目,运行程序,然后测试一下效果,如下图所示:
run
可以看到添加元素操作时间对比,QHash 和 QSet 对象的执行时间大概是 QMap 对象执行时间 1/3 ;
对比随机访问时间,QHash 和 QSet 对象的执行时间大概是 QMap 对象执行时间 1/4 ;
说明通常情况下 QHash 和 QSet 对象的添加和访问效率比 QMap 对象高很多,如果不需要排序,那么使用哈希类是更高效的选择。
本节的内容讲解到这,我们下一节专门讲解容器类的迭代器知识。


tip 练习
① 将 9.3.1 单映射 QMap 小节 nameage 示例中 QMap 内容改用 QHash 实现。
② 将 9.3.2 多映射 QMultiMap 小节的 namephone 例子,用本小节的 QMultiHash 实现。
③ 为 9.4.3 小节 voteset 例子添加一个按钮,实现选举出武林盟主、副盟主的功能,信息显示到文本浏览框。



prev
contents
next