首页 Qt 学习之路 2 Qt 学习之路 2(38):存储容器

Qt 学习之路 2(38):存储容器

39 4.1K

存储容器(containers)有时候也被称为集合(collections),是能够在内存中存储其它特定类型的对象,通常是一些常用的数据结构,一般是通用模板类的形式。C++ 提供了一套完整的解决方案,作为标准模板库(Standard Template Library)的组成部分,也就是常说的 STL。

Qt 提供了另外一套基于模板的容器类。相比 STL,这些容器类通常更轻量、更安全、更容易使用。如果你对 STL 不大熟悉,或者更喜欢 Qt 风格的 API,那么你就应该选择使用这些类。当然,你也可以在 Qt 中使用 STL 容器,没有任何问题。

本章的目的,是让你能够选择使用哪个容器,而不是告诉你这个类都哪些函数。这个问题可以在文档中找到更清晰的回答。

Qt 的容器类都不继承QObject,都提供了隐式数据共享、不可变的特性,并且为速度做了优化,具有较低的内存占用量等。另外一点比较重要的,它们是线程安全的。这些容器类是平台无关的,即不因编译器的不同而具有不同的实现;隐式数据共享,有时也被称作“写时复制(copy on write)”,这种技术允许在容器类中使用传值参数,但却不会出现额外的性能损失。遍历是容器类的重要操作。Qt 容器类提供了类似 Java 的遍历器语法,同样也提供了类似 STL 的遍历器语法,以方便用户选择自己习惯的编码方式。相比而言,Java 风格的遍历器更易用,是一种高层次的函数;而 STL 风格的遍历器更高效,同时能够支持 Qt 和 STL 的通用算法。最后一点,在一些嵌入式平台,STL 往往是不可用的,这时你就只能使用 Qt 提供的容器类,除非你想自己创建。顺便提一句,除了遍历器,Qt 还提供了自己的 foreach 语法(C++ 11 也提供了类似的语法,但有所区别,详见这里的 foreach 循环一节)。

Qt 提供了顺序存储容器:QListQLinkedListQVectorQStackQQueue。对于绝大多数应用程序,QList是最好的选择。虽然它是基于数组实现的列表,但它提供了快速的向前添加和向后追加的操作。如果你需要链表,可以使用QLinkedList。如果你希望所有元素占用连续地址空间,可以选择QVectorQStackQQueue则是 LIFO 和 FIFO 的。

Qt 还提供了关联容器:QMapQMultiMapQHashQMultiHashQSet。带有“Multi”字样的容器支持在一个键上面关联多个值。“Hash”容器提供了基于散列函数的更快的查找,而非 Hash 容器则是基于二分搜索的有序集合。

另外两个特例:QCacheQContiguousCache提供了在有限缓存空间中的高效 hash 查找。

我们将 Qt 提供的各个容器类总结如下:

  • QList<T>:这是至今为止提供的最通用的容器类。它将给定的类型 T 的对象以列表的形式进行存储,与一个整型的索引关联。QList在内部使用数组实现,同时提供基于索引的快速访问。我们可以使用 QList::append()QList::prepend()在列表尾部或头部添加元素,也可以使用QList::insert()在中间插入。相比其它容器类,QList专门为这种修改操作作了优化。QStringList继承自QList<QString>
  • QLinkedList<T>:类似于 QList,除了它是使用遍历器进行遍历,而不是基于整数索引的随机访问。对于在中部插入大量数据,它的性能要优于QList。同时具有更好的遍历器语义(只要数据元素存在,QLinkedList的遍历器就会指向一个合法元素,相比而言,当插入或删除数据时,QList的遍历器就会指向一个非法值)。
  • QVector<T>:用于在内存的连续区存储一系列给定类型的值。在头部或中间插入数据可能会非常慢,因为这会引起大量数据在内存中的移动。
  • QStack<T>:这是QVector的子类,提供了后进先出(LIFO)语义。相比QVector,它提供了额外的函数:push()pop()top()
  • QQueue<T>:这是QList的子类,提供了先进先出(FIFO)语义。相比QList,它提供了额外的函数:enqueue()dequeue()head()
  • QSet<T>:提供单值的数学上面的集合,具有快速的查找性能。
  • QMap<Key, T>:提供了字典数据结构(关联数组),将类型 T 的值同类型 Key 的键关联起来。通常,每个键与一个值关联。QMap以键的顺序存储数据;如果顺序无关,QHash提供了更好的性能。
  • QMultiMap<Key, T>:这是QMap的子类,提供了多值映射:一个键可以与多个值关联。
  • QHash<Key, T>:该类同QMap的接口几乎相同,但是提供了更快的查找。QHash以字母顺序存储数据。
  • QMultiHash<Key, T>:这是QHash的子类,提供了多值散列。

所有的容器都可以嵌套。例如,QMap<QString, QList<int> >是一个映射,其键是QString类型,值是QList<int>类型,也就是说,每个值都可以存储多个 int。这里需要注意的是,C++ 编译器会将连续的两个 > 当做输入重定向运算符,因此,这里的两个 > 中间必须有一个空格。

能够存储在容器中的数据必须是可赋值数据类型。所谓可赋值数据类型,是指具有默认构造函数、拷贝构造函数和赋值运算符的类型。绝大多数数据类型,包括基本类型,比如 int 和 double,指针,Qt 数据类型,例如QStringQDateQTime,都是可赋值数据类型。但是,QObject及其子类(QWidgetQTimer等)都不是。也就是说,你不能使用QList<QWidget>这种容器,因为QWidget的拷贝构造函数和赋值运算符不可用。如果你需要这种类型的容器,只能存储其指针,也就是QList<QWidget *>

如果要使用QMap或者QHash,作为键的类型必须提供额外的辅助函数。QMap的键必须提供operator<()重载,QHash的键必须提供operator==()重载和一个名字是qHash()的全局函数。

作为例子,我们考虑如下的代码:

struct Movie
{
    int id;
    QString title;
    QDate releaseDate;
};

作为 struct,我们当做纯数据类使用。这个类没有额外的构造函数,因此编译器会为我们生成一个默认构造函数。同时,编译器还会生成默认的拷贝构造函数和赋值运算符。这就满足了将其放入容器类存储的条件:

QList<Movie> movs;

Qt 容器类可以直接使用QDataStream进行存取。此时,容器中所存储的类型必须也能够使用QDataStream进行存储。这意味着,我们需要重载operator<<()operator>>()运算符:

QDataStream &operator<<(QDataStream &out, const Movie &movie)
{
    out << (quint32)movie.id << movie.title
        << movie.releaseDate;
    return out;
}

QDataStream &operator>>(QDataStream &in, Movie &movie)
{
    quint32 id;
    QDate date;

    in >> id >> movie.title >> date;
    movie.id = (int)id;
    movie.releaseDate = date;
    return in;
}

根据数据结构的相关内容,我们有必要对这些容器类的算法复杂性进行定量分析。算法复杂度关心的是在数据量增长时,容器的每一个函数究竟有多快(或者多慢)。例如,向QLinkedList中部插入数据是一个相当快的操作,并且与QLinkedList中已经存储的数据量无关。另一方面,如果QVector中已经保存了大量数据,向QVector中部插入数据会非常慢,因为在内存中,有一半的数据必须移动位置。为了描述算法复杂度,我们引入 O 记号(大写字母 O,读作“大 O”):

  • 常量时间:O(1)。如果一个函数的运行时间与容器中数据量无关,我们说这个函数是常量时间的。QLinkedList::insert()就是常量时间的。
  • 对数时间:O(log n)。如果一个函数的运行时间是容器数据量的对数关系,我们说这个函数是对数时间的。qBinaryFind()就是对数时间的。
  • 线性时间:O(n)。如果一个函数的运行时间是容器数据量的线性关系,也就是说直接与数量相关,我们说这个函数是线性时间的。QVector::insert()就是线性时间的。
  • 线性对数时间:O(n log n)。线性对数时间要比线性时间慢,但是要比平方时间快。
  • 平方时间:O(n²)。平方时间与容器数据量的平方关系。

基于上面的表示,我们来看看 Qt 顺序容器的算法复杂度:

 查找插入前方添加后方追加
QLinkedList<T>O(n)O(1)O(1)O(1)
QList<T>O(1)O(n)统计 O(1)统计 O(1)
QVector<T>O(1)O(n)O(n)统计 O(1)

上表中,所谓“统计”,意思是统计意义上的数据。例如“统计 O(1)”是说,如果只调用一次,其运行时间是 O(n),但是如果调用多次(例如 n 次),则平均时间是 O(1)。

下表则是关联容器的算法复杂度:

查找键插入
平均最坏平均最坏
QMap<Key, T>O(log n)O(log n)O(log n)O(log n)
QMultiMap<Key, T>O(log n)O(log n)O(log n)O(log n)
QHash<Key, T>统计 O(1)O(n)O(1)统计 O(n)
QSet<Key, T>统计 O(1)O(n)O(1)统计 O(n)

QVectorQHashQSet的头部添加是统计意义上的 O(log n)。然而,通过给定插入之前的元素个数来调用QVector::reserve()QHash::reserve()QSet::reserve(),我们可以把复杂度降到 O(1)。我们会在下面详细讨论这个问题。

QVector<T>QStringQByteArray在连续内存空间中存储数据。QList<T>维护指向其数据的指针数组,提供基于索引的快速访问(如果 T 就是指针类型,或者是与指针大小相同的其它类型,那么 QList 的内部数组中存的就是其实际值,而不是其指针)。QHash<Key, T>维护一张散列表,其大小与散列中数据量相同。为避免每次插入数据都要重新分配数据空间,这些类都提供了多余实际值的数据位。

我们通过下面的代码来了解这一算法:

QString onlyLetters(const QString &in)
{
    QString out;
    for (int j = 0; j < in.size(); ++j) {
        if (in[j].isLetter())
            out += in[j];
    }
    return out;
}

我们创建了一个字符串,每次动态追加一个字符。假设我们需要追加 15000 个字符。在算法运行过程中,当达到以下空间时,会进行重新分配内存空间,一共会有 18 次:4,8,12,16,20,52,116,244,500,1012,2036,4084,6132,8180,10228,12276,14324,16372。最后,这个 out 对象一共有 16372 个 Unicode 字符,其中 15000 个是有实际数据的。

上面的分配数据有些奇怪,其实是有章可循的:

  • QString每次分配 4 个字符,直到达到 20。
  • 在 20 到 4084 期间,每次分配大约一倍。准确地说,每次会分配下一个 2 的幂减 12。(某些内存分配器在分配 2 的幂数时会有非常差的性能,因为他们会占用某些字节做预订)
  • 自 4084 起,每次多分配 2048 个字符(4096 字节)。这是有特定意义的,因为现代操作系统在重新分配一个缓存时,不会复制整个数据;物理内存页只是简单地被重新排序,只有第一页和最后一页的数据会被复制。

QByteArrayQList<T>实际算法与QString非常类似。

对于那些能够使用memcpy()(包括基本的 C++ 类型,指针类型和 Qt 的共享类)函数在内存中移动的数据类型,QVector<T>也使用了类似的算法;对于那些只能使用拷贝构造函数和析构函数才能移动的数据类型,使用的是另外一套算法。由于后者的消耗更高,所以QVector<T>减少了超出空间时每次所要分配的额外内存数。

QHash<Key, T>则是完全不同的形式。QHash的内部散列表每次会增加 2 的幂数;每次增加时,所有数据都要重新分配到新的桶中,其计算公式是qHash(key) % QHash::capacity()QHash::capacity()就是桶的数量)。这种算法同样适用于 QSet<T>QCache<Key, T>。如果你不明白“桶”的概念,请查阅数据结构的相关内容。

对于大多数应用程序。Qt 默认的增长算法已经足够。如果你需要额外的控制,QVector<T>QHash<Key, T>QSet<T>QStringQByteArray提供了一系列函数,用于检测和指定究竟要分配多少内存:

  • capacity():返回实际已经分配内存的元素数目(对于QHashQSet,则是散列表中桶的个数)
  • reserve(size):为指定数目的元素显式地预分配内存。
  • squeeze():释放那些不需要真实存储数据的内存空间。

如果你知道容器大约有多少数据,那么你可以通过调用reserve()函数来减少内存占用。如果已经将所有数据全部存入容器,则可以调用squeeze()函数,释放所有未使用的预分配空间。

39 评论

xiaojian 2013年1月15日 - 14:32

学习了 楼主好强大的呀

回复
豆子 2013年1月16日 - 09:54

过奖,这些很多都是文档中的内容,可以看看文档原文。

回复
andmoe 2013年1月15日 - 16:26

呼~期待下一篇! 🙂

回复
死机不死 2013年1月15日 - 20:07

加上一个ODBC的SQLSERVER/ORACLE,最好能自己写个DataSet、DataTable类,加油豆子

回复
enockipp 2013年9月24日 - 21:02

感觉跟C++的容器差不多,怎么没有了multiSet?

回复
豆子 2013年9月25日 - 10:27

容器只有那么多,各个库都是差不多的。STL 有的 Qt 也不一定要引入的,所以没有 multiset 也是正常

回复
enockipp 2013年9月26日 - 08:40

恩,谢谢回复

回复
Tino 2013年12月19日 - 17:23

博主真是博学多才~
算法复杂度讲的言简意赅~
受益匪浅~

回复
Const_Lin 2014年3月15日 - 16:25

豆子你好:
文中这段话:“QHash则是完全不同的形式。QHash的内部散列表每次会增加 2 的幂数;每次增加时,所有数据都要重新分配到新的桶中,其计算公式是qHash(key) % QHash::capacity()”
其中,计算公式有没有误?感觉应该是qHash(key) / QHash::capacity()

回复
豆子 2014年3月17日 - 09:19

这个公式是文档中给出的,应该没有错误。一般这里都会是取模运算,这样才能将数据平均分配到 [ 0, QHash::capacity() ) 范围;除法运算则更为集中。考虑 qHash(key) 运算结果分别为 1, 2, 3, 4, 5,QHash::capacity() == 5 的情况,qHash(key) % QHash::capacity() 运算结果分别是 1, 2, 3, 4, 0;qHash(key) / QHash::capacity() 运算结果分别是 0, 0, 0, 0, 1。显然,取模更平均一些。

回复
rrrdr 2014年4月28日 - 13:31

你好,请问,QList有没有子类能像QMultiHash那样允许保存多值的容器呢?

回复
豆子 2014年4月29日 - 15:04

QList 本身就允许重复值,不知道你说的类似 QMultiHash 是什么意思?如果是一个索引可以存入多个值,是不是使用 QList 就可以了?

回复
Rice 2014年6月22日 - 16:08

請問版主
(1)使用 STL Lib 是否可以支援日後的跨平台?
(2)如果使用第三方函式庫(dll or lib)是不是就不一定能支援日後的跨平台?
非常感謝

回复
delifue 2014年7月27日 - 10:37

qt中有没有有信号槽的容器?

回复
豆子 2014年7月28日 - 22:10

没有,Qt 的容器都没有继承 QObject,所以都不支持信号槽。如果需要可以自己封装一个类似的容器。

回复
Wangzhe 2014年8月22日 - 14:37

“这里需要注意的是,C++ 编译器会将连续的两个 > 当做输入重定向运算符,因此,这里的两个 > 中间必须有一个空格。”——按说支持Qt 5的编译器都是支持C++11的,这个限制在C++11里已经取消了。
另外“Qt容器类没有继承自QObject”这个问题也挺重要的,应该在文中提一下吧!

回复
豆子 2014年8月23日 - 12:02

考虑到这篇文章也涉及到 Qt 4,所以关于重定向运算符还是这么写的。毕竟有些代码还要考虑向前兼容。Qt容器类没有继承自QObject的确是的。

回复
gq 2015年8月17日 - 15:44

博主大哥,请问一下定义QMultiHash x;
程序在x.insertMulti(a,b); 的时候就报错了,我查了一些资料,说需要对key进行==重载,还有一个就是qhash全局函数,就是不太明白。请问怎么操作呢?
我想做一个一对多的映射,b是会自动生成QList?,那遍历的时候怎么遍历呢?

回复
gq 2015年8月17日 - 15:47

struct a,struct b,这两个都是结构体,重载了==运算符还是报错。博主求帮助

回复
豆子 2015年8月26日 - 13:06

QHash 和 QMultiHash 需要计算存入对象的 hash 值,所以需要提供一个全局的 qHash 函数,具体你可以看看 qHash 的文档;遍历的时候可以使用 iterator 进行。

回复
Kian 2015年10月29日 - 16:47

Qt 容器类可以直接使用QDataStream进行存取。此时,容器中所存储的类型必须也能够使用QDataStream进行存储。这意味着,我们需要重载operator<>()运算符
请问为什么需要重载operator<>()运算符

回复
豆子 2015年11月4日 - 14:07

文中并没有类似的语句,可能看错了吧

回复
罗伊马斯特 2016年3月25日 - 16:13

一个小错:
QHash以字母顺序存储数据。
应该是:
QHash以任意顺序存储数据。

回复
zhangdexin 2016年7月14日 - 19:57

QString中一个字符占两个字节吗?

回复
豆子 2016年7月17日 - 19:32

QString 文档中写的是“QString stores a string of 16-bit QChars, where each QChar corresponds one Unicode 4.0 character. ”,因此一个字符是 16 位的 Unicode。

回复
ccppaa 2016年7月21日 - 15:49

大神,我现在在准备做一个收银系统中的挂单功能,需要把当前刷的商品挂起来,我的想法是把先判断有没有商品,,、有没有已经挂单当前的的商品,先存到QVariant中,插入到表里,取单的时候,从表里查询有没有数据,有的话再把数据取出来,想问一下大神能不能不建表,直接通过容器操作,怎么判断

回复
豆子 2016年7月22日 - 09:16

这个不是很明确,容器的话不就是检索一下看有没有该商品不就好了?

回复
ccppaa 2016年7月22日 - 16:44

QMap(("0", QVariant(QVariantMap, QMap(("beizhu", QVariant(QString, "无"))("discountRate", QVariant(QString, "100"))("goods_code", QVariant(QString, ""))("goods_id", QVariant(QString, "1234567"))("goods_name", QVariant(QString, "无码收银"))("goods_norms", QVariant(QString, "件"))("goods_num", QVariant(QString, "1"))("goods_pay_price", QVariant(QString, "0.00"))("goods_price", QVariant(QString, "0.00"))("subTotal", QVariant(QString, "0.00"))("xuaho", QVariant(QString, "1")))))("1", QVariant(QVariantMap, QMap(("beizhu", QVariant(QString, "无"))("discountRate", QVariant(QString, "100"))("goods_code", QVariant(QString, ""))("goods_id", QVariant(QString, "1234567"))("goods_name", QVariant(QString, "无码收银"))("goods_norms", QVariant(QString, "件"))("goods_num", QVariant(QString, "1"))("goods_pay_price", QVariant(QString, "1.00"))("goods_price", QVariant(QString, "1.00"))("subTotal", QVariant(QString, "1.00"))("xuaho", QVariant(QString, "2"))))))

这是我用qDebug()调出来的QVariantMap 类型的数据,该怎么读出来,读取到tableView里,希望大神能用代码讲解一下(大概用法),我之前想把它转化成QVariantList读,但是没成功,

回复
ccppaa 2016年7月22日 - 18:04

QJsonDocument({"buyer":"","buyerEmail":"","buyerid":"","discountRate":1,
"goodsList":{"0":{"beizhu":"无","discountRate":"100","goods_code":"","goods_id":"1234567","goods_name":"无码收银","goods_norms":"件",
"goods_num":"1","goods_pay_price":"0.00","goods_price":"0.00","subTotal":"0.00","xuaho":"1"},

"1":{"beizhu":"无","discountRate":"100","goods_code":"","goods_id":"1234567","goods_name":"无码收银","goods_norms":"件","goods_num":"1",
"goods_pay_price":"0.00","goods_price":"0.00","subTotal":"0.00","xuaho":"2"}},

"mpredeposit":"","payMethod":"custom","realprice":0,"totalcount":2,"totalprice":0,"truename":"来宾"})转化成json是这样的,但是我不会解析到tableview中,我的tableview的model是QStandardModel

回复
豆子 2016年7月23日 - 11:09

goodsList 看起来应该是一个数组,但是你的输出是一个对象。对话的话就只能转换成 map 了,怀疑是你的数据有问题,应该讲 goodsList 转换成数组(以 [] 包裹才对,你现在是 {})。如果的确就是对象,那么只能转换成 map 之后遍历这个 map,每次取出 map 的一项,每一个字段对应创建一个 QStandardItem,这些组成 item 一个 list,然后用 insertRow() 插入到 QStandardItemModel 中。

回复
ccppaa 2016年7月23日 - 11:11

QVariantMap orderMap;
int num = goodsListModel->rowCount();
for(int i = 0;iindex(i,0).data().toString();
gorderDetail["goods_code"] = goodsListModel->index(i,1).data().toString();
gorderDetail["goods_name"] = goodsListModel->index(i,2).data().toString();
gorderDetail["goods_norms"] = goodsListModel->index(i,3).data().toString();
gorderDetail["goods_num"] = goodsListModel->index(i,4).data().toString();
gorderDetail["goods_price"] = goodsListModel->index(i,5).data().toString();
gorderDetail["discountRate"] = goodsListModel->index(i,6).data().toString();
gorderDetail["goods_pay_price"] = goodsListModel->index(i,7).data().toString();
gorderDetail["subTotal"] = goodsListModel->index(i,8).data().toString();
gorderDetail["beizhu"] = goodsListModel->index(i,9).data().toString();
gorderDetail["goods_id"] = goodsListModel->index(i,10).data().toString();
orderMap[QString::number(i)] = gorderDetail;
}
qDebug()<<orderMap;
gorderInfo["goodsList"] = orderMap;

这是goodsList

回复
ccppaa 2016年7月23日 - 15:43

问题已经解决了,犯了一个低级错误,我一直没弄出来只是遍历的时候吧QString类型的弄成int了,麻烦大神了

回复
小张 2016年11月23日 - 11:15

线性时间:O(n)。如果一个函数的运行时间是容器数据量的线性关系,也就是说直接与数量相关,我们说这个函数【限行】时间的。——应该是【线性】吧
对于那些能够使用【memcry() 】——这个是写错了吗,是【memcpy()】吗

回复
豆子 2016年11月26日 - 10:41

已经修改过了,多谢指出

回复
Booth 2019年6月5日 - 15:24

"为避免每次插入数据都要重新分配数据空间,这些类都提供了多余实际值的数据位。"
——这里是不是要改为“多于实际值”

回复

回复 小张 取消回复

关于我

devbean

devbean

豆子,生于山东,定居南京。毕业于山东大学软件工程专业。软件工程师,主要关注于 Qt、Angular 等界面技术。

主题 Salodad 由 PenciDesign 提供 | 静态文件存储由又拍云存储提供 | 苏ICP备13027999号-2