kong000dao0 2020-04-16
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
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。
不过二者最大的差别是,std::bitset是定长,数据元素分配在栈上。QBitArray是变长,数据元素分配在堆上。这个肯定有性能差别。
当然还是推荐用QTL来存,因为QTL会对这些隐式共享类型做特殊优化,这方面可以看看QList源码。
唯一的特例是QWidget类型及其子类,这些类型绝对不允许直接保存,只能用指针保存,哪怕用QTL也是这样。
但是,不推荐用STL保存Qt对象,因为代码风格不一致。不过QTL同时提供了Qt style API和STL style API,如果有和第三方库混合编程的需求,推荐用STL style API,这样可以随时替换类型。另外,QTL还提供了Java style iterator,对于一些习惯Java语法的用户会很方便。
QTL比起STL,性能差别不明显,主要差异在:
对于采用相同算法的容器,比如QVector和std::vector,各项操作的时间复杂度应该是相同的,差异只会在实现的语法细节。当然如果stl写了内存池用allocator的话,肯定会快上许多。
============================
设计数据元素均为int,无论key还是value(懒得构造随机string了)。这个benchmark写的较早,后来维护文章时把std::hash改为了std::unordered_map,把std::set改为了std::unordered_set,但benchmakr相关用例没有更新,还望见谅。
(在不使用allocator的前提下)
(PS:刚在一个小程序里尝试了下QQueue,末尾入队,开头出队,在队长不变的情况下,内存开销毫无变动……看来QList的双向内存增长很有意思,很可能是用了个环形缓冲放头尾指针,放不下时对其进行扩充,所以才能解释为何QQueue的表现会那么神奇……QList虽然是模板类,但Node的具体操作被封装到cpp里了,回头得翻出来看看才行)
(PSP:使用list/vector可能是性能考虑吧,因为这二者都是内存连续的,对cache友好)
(PSV:STL的queue和stack好像也是分别用deque和vector实现的……)
===============================
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