论Qt容器与STL

kong000dao0 2020-04-16

论Qt容器与STL

https://zhuanlan.zhihu.com/p/24035468

编辑于 2017-02-27

相关阅读

推荐一篇比较全面的介绍QTL的文章:Understand the Qt containers

@渡世白玉 对其做了大致的翻译,链接如下:

[翻译]理解Qt容器:STL VS QTL(一)--特性总览
[翻译]理解Qt容器:STL VS QTL(二)--迭代器
[翻译]理解Qt容器:STL VS QTL(三)--类型系统 和其他处理


============================


定性分析

Qt的容器类具体分析可见官方文档:Container Classes

里面有关于时间复杂度、迭代器等各方面的概述和表格对比。

各个容器的具体实现,可以看代码,或者看容器类文档开头的详细介绍。


QTL比起STL的话,最大的特点是统一用了写时复制技术。缺点是不支持用户自定allocator。


在这里先简单类比下吧,具体数据可以看后面的benchmark

  • QLinkedList —— std::list 两者都是双向链表,两者可以直接互转。
  • QVector —— std::vector 两者都是动态数组,都是根据sizeof(T)进行连续分配,保证成员内存连续,能够用data()直接取出指针作为c数组使用,两者可以直接互转。
  • QMap —— std::map 两者都是红黑树算法,但不能互转,因为数据成员实现方式不同。std::map的数据成员用的是std::pair,而QMap用的是自己封装的Node,当然还是键值对.
  • QMultiMap —— std::multimap 同上。
  • QList —— 暂无。QList其实不是链表,是优化过的vector,官方的形容是array list。它的存储方式是分配连续的node,每个node的数据成员不大于一个指针大小,所以对于int、char等基础类型,它是直接存储,对于Class、Struct等类型,它是存储对象指针。

std::deque很相似,但有少许区别。据有的知友提出,QList更像是boost::deque。

QList的实现模式,优点主要在于快速插入。因为其元素大小不会超过sizeof(void*),所以插入时只需要移动指针,而非如vector那样移动对象。并且,由于QList存储的是void*,所以可以简单粗暴的直接用realloc()来扩容。

另外,QList的增长策略是双向增长,所以对prepend支持比vector好得多,使用灵活性高于Vector和LinkedList。缺点是每次存入对象时,需要构造Node对象,带来额外的堆开销。

QList还规避了模板最大的问题——代码量膨胀。由于QList其实是用void*存储对象,所以它的绝大部分代码是封装在了操作void*的cpp里,头文件只暴露了对其的封装。

然而Qt对QList的支持还是很充足,用户甚至可以用宏为自己要放入list的对象进行属性指定(POD?Class但可以直接memcpy?只能用拷贝构造?)来辅助编译优化。(此项辅助优化对绝大部分QTL容器都有效。如将类型定义为POD后,QVector便会通过realloc()扩容,而std::vector只会对基础类型这么做)

对了,QList虽然是个特殊的Vector,但提供的接口仍然是和std::list的互转,挺奇葩的……

在Qt里,QList是官方最常用的容器类,也是官方最推荐的,原文是这么说的——“在大多数情况下,都推荐使用QList,它提供更加快速的插入,并且(编译后)可以展开为更少的代码量。”

实际QList的内存浪费很严重——当元素小于等于sizeof(void*)时,会直接存储元素,但按照void*对齐的话,过小的数据类型会浪费内存。当元素大于sizeof(void*)时,存在分配指针的开销。但是,当元素是moveable类型(有构造函数但可以直接memcpy),且大小等于sizeof(void*)时,QList在内存开销和性能两者上都达到了完美——而Qt的许多常用数据类型刚好满足这个条件(Qt内建类型习惯用QXxxPrivate指针存储对象数据),包括但不限于QString、QByteArray、QIcon、QFileInfo、QPen、QUrl……

因此,当且仅当你的数据类型大小等于sizeof(void*),并且是moveable或者是POD时,通过宏指定类型辅助优化,这时用QList更好。其他情况都应用QVector。当然,如果你需要push_front()/prepend(),那必须得用QList。

  • QBitArray —— std::bitset 功能相同,实现相似,都是构造一个array,用位操作来存取数据。不同的是,QBitArray数据的基础元素是unsigned char,而bitset是unsigned long。所以QBitArray可能在空间消耗上会省一点。至于效率上么,二者查询都是一次寻址提取加一次移位操作,算法层面应该没有区别。

不过二者最大的差别是,std::bitset是定长,数据元素分配在栈上。QBitArray是变长,数据元素分配在堆上。这个肯定有性能差别。

  • QHash —— std::unordered_map都是各自实现了自己的hashTable,然后查询上都是用node->next的方式逐一对比,不支持互转,性能上更多的应该是看hash算法。QHash为常用的qt数据类型都提供好了qHash()函数,用户自定类型也能通过自己实现qHash()来存入QHash容器。
  • QSet —— std::unordered_set二者不能互转,实现方式本质相同,都是改造过的QHash,用key来存数据,value置空。另外STL提供了使用红黑树的std::set,可以看作是std::map的改造版。std::unordered_set效率上一般应该是和QSet没区别,std::set效率较低,但不用担心撞车。
  • QVarLengthArray —— std::array std::array是用class封装后的定长数组,数据分配在栈上。QVarLengthArray类似,默认也是定长数组,栈分配。但用户依旧可以添加超出大小的内容,此时它会退化为Vector,改用堆分配。

  • 可靠性——二者都有长期在大型系统级商业应用上使用的经历,并且除了c++11版本特性引入外,代码实现上基本没有大的变动,所以可靠性均无问题。当然,为了保证效率,两者都不提供thread safe,最多提供reentrant
  • 安全性——Qt变量存STL不存在安全隐患,毕竟都是class,只要是支持copy constructor和assignment operator的对象,都可以放心存STL。而且由于Qt对象广泛使用了写时复制机制,所以存储时时空开销非常小。

当然还是推荐用QTL来存,因为QTL会对这些隐式共享类型做特殊优化,这方面可以看看QList源码。

唯一的特例是QWidget类型及其子类,这些类型绝对不允许直接保存,只能用指针保存,哪怕用QTL也是这样。

但是,不推荐用STL保存Qt对象,因为代码风格不一致。不过QTL同时提供了Qt style API和STL style API,如果有和第三方库混合编程的需求,推荐用STL style API,这样可以随时替换类型。另外,QTL还提供了Java style iterator,对于一些习惯Java语法的用户会很方便。


总结

QTL比起STL,性能差别不明显,主要差异在:

  1. QTL不支持allocator;
  2. QTL没有shirnk接口(最新的几个版本里有了,不过不叫shirnk);
  3. QTL没有rbegin()/rend()(同上,最近几个版本有了,相同API名称);
  4. QTL对c++11特性的支持较晚(同上,Qt5.6开始才全面支持新特性),在这之前的版本,比起支持比如右值引用的STL版本,性能要略差。

对于采用相同算法的容器,比如QVector和std::vector,各项操作的时间复杂度应该是相同的,差异只会在实现的语法细节。当然如果stl写了内存池用allocator的话,肯定会快上许多。

论Qt容器与STL

上图是Qt Document里Container Classes章节对各容器类性能的统计。从这里也可以看出,QList其实是个特殊的QVector,QSet其实是个特殊的QHash。

============================

Benchmark算法

设计数据元素均为int,无论key还是value(懒得构造随机string了)。这个benchmark写的较早,后来维护文章时把std::hash改为了std::unordered_map,把std::set改为了std::unordered_set,但benchmakr相关用例没有更新,还望见谅。

  • List:一百万次push_back()随机值,一百万次push_front()随机值。成员查询都是靠遍历,就没必要专门测了。
  • ListWithInsert:相比上面的testcase,多了十万次insert操作,插入随机值到随机位置。感觉这个略蛋疼,没必要做
  • Vector:一百万次push_back()随机值,一百万次随机查询并求和(求和结果没去用,只是怕不操作返回值的话,编译器直接把读操作优化没了)(vector的insert效率太低,就不测了。)
  • Map:一百万次随机插入(key和value都是随机值),一百万次随机查询并求和。
  • Hash:同Map
  • Set:同Map
  • Bitset:初始化定长一百万,初值false。然后进行一百万次随机位置取反操作
  • Array:初始化定长十万(一百万试了下,爆栈了),初值随机值。然后进行一百万次随机查询求和操作


测试平台

  • SurfaceBook I5 独显版
  • CPU:I5-6300U 2.4GHz 四线程
  • 内存:8GB
  • 编译器:MinGW 5.3.0 32bit MSVC 2015 (14.0 amd64)
  • 框架:Qt 5.7.0的Qt Test模块(提供代码段进行benchmark,若耗时过少会自动重复多次,统计平均值)


Benchmark结果

论Qt容器与STL

QTL与STL对比结论

(在不使用allocator的前提下)

  1. QTL和STL性能,同样算法的容器基本在同一数量级。
  2. Bitset容器可以看出,堆分配比栈分配有性能损失。
  3. Set和Hash两者存在实现差异,所以benchmark结果差距较大。红黑树和hashtable的效率差距太大了……(后来得知STL有使用hashtable的std::unordered_set,不过没继续测了……)。
  4. vector的insert效率太低,不管是Qt还是STL,时间开销都在内存移动上,而且不太可能通过除了内存池之外的办法进行优化,所以就没测了。
  5. QList在拥有vector的操作性能的同时,通过前向扩展空间,模拟出了LinkedList的双向添加O(1)的特点。但存储int这种基础类型时,由于存在Node的构造开销,效率不如vector。
  6. MSVC的Debug真凶残,不造加了多少overhead进去,这运行时间长的……

吐槽

  • Qt的QQueue队列类,是直接继承自QList,只是添加了队列操作的接口。这难道不应该用LinkedList么,残念……如果我enqueue一百万次,dequeue一百万次,没有shrink功能的list,那内存开销……

(PS:刚在一个小程序里尝试了下QQueue,末尾入队,开头出队,在队长不变的情况下,内存开销毫无变动……看来QList的双向内存增长很有意思,很可能是用了个环形缓冲放头尾指针,放不下时对其进行扩充,所以才能解释为何QQueue的表现会那么神奇……QList虽然是模板类,但Node的具体操作被封装到cpp里了,回头得翻出来看看才行)

  • QStack栈类,继承自QVector,添加了栈操作接口。和QQueue一样残念……不过这个还算好了,内存应该不会爆掉,虽然我觉得,stack和queue这种无随机访问需求的,应该用LinkedList实现比较好……

(PSP:使用list/vector可能是性能考虑吧,因为这二者都是内存连续的,对cache友好)

(PSV:STL的queue和stack好像也是分别用deque和vector实现的……)

  • 出现个诡异的情况,Debug模式下,最后Array的testcase,莫名其妙的越界了,然后assert退出,囧……估计debug的栈分配和realse不同,所以爆栈了


===============================

QList、QVector对比

QList在提供最大化的易用性的同时,带来了最小的性能损耗,若不使用prepend的话,可以换用QVecotr。

以下摘自QList帮助文档:

Qt 4:

  • For most purposes, QList is the right class to use. Its index-based API is more convenient than QLinkedList‘s iterator-based API, and it is usually faster than QVector because of the way it stores its items in memory. It also expands to less code in your executable.
  • If you need a real linked list, with guarantees of constant time insertions in the middle of the list and iterators to items rather than indexes, use QLinkedList.
  • If you want the items to occupy adjacent memory positions, use QVector.

Qt 5:

QList<T> is one of Qt‘s generic container classes. It stores items in a list that provides fast index-based access and index-based insertions and removals.

QList<T>, QLinkedList<T>, and QVector<T> provide similar APIs and functionality. They are often interchangeable, but there are performance consequences. Here is an overview of use cases:

  • QVector should be your default first choice. QVector<T> will usually give better performance than QList<T>, because QVector<T> always stores its items sequentially in memory, where QList<T> will allocate its items on the heap unless sizeof(T) <= sizeof(void*) and T has been declared to be either a Q_MOVABLE_TYPE or a Q_PRIMITIVE_TYPE using Q_DECLARE_TYPEINFO. See the Pros and Cons of Using QList for an explanation.
  • However, QList is used throughout the Qt APIs for passing parameters and for returning values. Use QList to interface with those APIs.
  • If you need a real linked list, which guarantees constant time insertions mid-list and uses iterators to items rather than indexes, use QLinkedList.
  • Note: QVector and QVarLengthArray both guarantee C-compatible array layout. QList does not. This might be important if your application must interface with a C API.

翻译:

Qt 4:

  • 在绝大多数场合,QList都是正确的选择。它的基于下标的API比QLinkeList的基于迭代器的API更加方便,并且它通常比QVector更快——基于它在内存中的存储方式。并且,QList在编译到二进制时可以扩展为为更少的代码。(译者注:此处应该指的是插入比QVector快。访问应该比不过真·顺序存储的QVector)。
  • 如果你需要一个真正的链表,来保证在中间插入时的常量级耗时,并且用迭代器而非下标访问,那么使用QLinkedList。
  • 如果你想让对象在内存中顺序存储,那么使用QVector。

Qt 5:

QList<T>是Qt的通用容器类之一。它用于列表存储元素,并提供快速的序号查询、序号插入和删除。

QList<T>、QLinkedList<T>、QVector<T>提供相似的API和功能。它们经常是可以互相替换的,但存在性能差异。下面是它们的用例介绍:

  • QVector应该是你的默认选择。QVecotr通常提供比QList更好的性能,因为QVector总是将所有元素在内存中顺序存储,而QList则是将各个元素分别分配到堆中,除非sizeof(T) <= sizeof(void*),并且T被通过Q_DECLARE_TYPEINFO()宏定义为Q_MOVABLE_TYPE(可以memcpy的类型)或Q_PRIMITIVE_TYPE(POD类型)。详见Pros and Cons of Using QList 。
  • 然而,QList被Qt API广泛用于传递参数和返回值。在与这些API交互时使用QList。
  • 如果你需要一个真正的链表,以保证常量级的插入,并且使用迭代器而非索引,那么选择QLinkedList。

注意:QVector和QVarLengthArray都保证了对C数组的兼容。QList则不提供此兼容性。这在当你与C API交互时可能很重要。

 

============= End