重新审视了QList与QVector

Question

我的问题基本上是什么时候选择QVector以及何时选择QList作为你的Qt容器.我所知道的:

1. Qt docs:QList类

对于大多数用途,QList是正确的类.它的基于索引的API比QLinkedList的基于迭代器的API更方便,并且它通常比QVector更快,因为它将其项目存储在内存中.它还扩展到可执行文件中较少的代码.

2. 这是非常受欢迎的问答:QVector vs QList.它也有利于QList.

3. 但是:在最近的2015年Qt世界峰会上,KDAB提出了"为什么QList有害",这基本上是在这里:

QList被认为是有害的

不要使用QList,请使用Q_DECLARE_TYPEINFO

据我所知,这个想法是,QList在堆中分配新元素时,几乎所有类型都是低效的.每次添加新元素时,它都会调用new(每个元素一次),与之相比,这是低效的QVector.

这就是我现在试图理解的原因:QVector我们应该选择哪个默认容器？

Answer 1

Qt宣传QList为"所有行业的杰克",但另一半的说法是"无人掌握".QList如果你打算附加到列表的两端,那么我会说这是一个很好的候选者,并且它们不会超过指针,因为它会QList保留前后的空间.这就是它,我的意思是就使用的好理由QList而言.

QList将自动存储"大"对象作为指针并在堆上分配对象,如果你是一个婴儿,这可能被认为是一件好事,它不知道如何声明QVector<T*>和使用动态分配.这不一定是好事,在某些情况下,它只会膨胀内存使用量并增加额外的间接性.IMO总是一个好主意,明确你想要什么,无论是指针还是实例.即使你确实想要堆分配,最好自己分配它,只需将指针添加到列表中,而不是构造对象一次,然后在堆上有复制构造.

Qt会QList在很多地方给你回报,例如当QObject你的孩子或你寻找孩子时.在这种情况下,使用在第一个元素之前分配空间的容器是没有意义的,因为它是已经存在的对象列表,而不是您可能要添加的对象.我也不太喜欢没有resize()方法.

想象一下,在64位系统上有一个大小为9字节且字节对齐的对象.这样做太"太多了",QList相反,它将使用8字节指针+ CPU开销来实现堆分配的慢堆分配和内存开销.它将使用两倍的内存和额外的间接访问,它几乎不会提供广告宣传的性能优势.

至于为什么QVector不能突然成为"默认"容器 - 你不会在比赛中改变马匹 - 这是一个传统的东西,Qt是一个如此古老的框架,即使很多东西已经被弃用,也要广泛地做出改变使用默认值并不总是可行的,不是没有破坏大量代码或产生不良行为.无论好坏,QList都可能在整个Qt 5中继续成为默认值,并且可能在下一个主要版本中也是如此.同样的原因Qt将继续使用"哑"指针,多年后智能指针已成为必须,每个人都在抱怨平原指针有多糟糕以及它们应该如何使用.

话虽这么说,没有人强迫你QList在你的设计中使用.没有理由不QVector应该是您的默认容器.我自己不在QList任何地方使用,并且在Qt函数中返回一个QList我只是用作临时将东西移动到一个QVector.

此外,这只是我个人的意见,但我确实发现Qt中的许多设计决策没有必要有意义,是性能或内存使用效率或易用性明智,总体而言有很多框架和喜欢宣传他们做事方式的语言,不是因为这是最好的方式,而是因为这是他们的方式.

最后但并非最不重要的:

对于大多数用途,QList是正确的类.

这真的归结为你如何理解这一点.IMO在这种背景下,"正确的"并不代表"最好的"或"最优的",而是"足够好",就像"它会做,即使不是最好的".特别是如果您对不同的容器类及其工作方式一无所知.

对于大多数目的,QList会这样做.

总结一下:

QList 投票站

• 你打算在不大于指针大小的前面添加对象,因为它在前面保留了一些空间
• 你打算在列表中间插入(基本上)大于指针的对象(我在这里很慷慨,因为你可以轻松地使用QVector显式指针来实现相同和更便宜 - 没有额外的副本),因为在调整大小时列表,没有对象将被移动,只有指针

QList CON外

• 没有resize()方法,reserve()是一个微妙的陷阱,因为它不会增加有效的列表大小,即使索引访问工作它属于UB类别,你也将无法迭代该列表
• 当对象大于指针时,会执行额外的复制和堆分配,如果对象标识很重要,这也可能是一个问题
• 使用额外的间接访问来访问大于指针的对象
• 由于最后两个而导致CPU时间和内存使用开销,也减少了缓存友好性
• 当用作"搜索"返回值时会带来额外的开销,因为您不可能在前面添加或甚至附加到该值
• 只有索引访问是必须的才有意义,为了获得最佳的前置和插入性能,链表可能是更好的选择.

CON略微超过了PRO,这意味着虽然在"随意"使用中QList可能是可以接受的,但你肯定不希望在CPU时间和/或内存使用是关键因素的情况下使用它.总而言之QList,当您不想考虑用例的最佳存储容器时,最适合懒惰和不小心使用,通常是a QVector<T>,a QVector<T*>或a QLinkedList(并且我不包括"STL"容器,因为我们在这里谈论Qt,Qt容器就像便携式,有时更快,并且使用起来肯定更容易和更清洁,而std容器是不必要的冗长的.

Answer 2

在Qt 5.7中,关于此处讨论的主题的文档已经更改.在QVector中,现在说:

QVector应该是您的默认首选.QVector<T>通常会提供比它更好的性能QList<T>,因为它QVector<T>总是将其项目按顺序存储在内存中,QList<T>除非sizeof(T)<= sizeof(void*)并且T已声明为a Q_MOVABLE_TYPE或者Q_PRIMITIVE_TYPE使用,否则将在堆上分配其项目Q_DECLARE_TYPEINFO.

他们参考Marc Mutz撰写的这篇文章.

所以官方的观点已经发生了变化.

Answer 3

QList是一个数组void*。

在其正常操作中，它new是堆上的元素并将指向它们的指针存储在void*数组中。与链表一样，这意味着对包含在列表中的元素的引用（但与链表不同，不是迭代器！）在所有容器修改下仍然有效，直到该元素再次从容器中删除。因此名称为“列表”。这种数据结构称为数组列表，并在许多编程语言中使用，其中每个对象都是引用类型（例如 Java）。它是一种对缓存非常不友好的数据结构，就像所有基于节点的容器一样。

但是可以将数组列表的大小调整分解为与类型无关的帮助程序类 ( QListData)，它应该可以节省一些可执行代码的大小。在我的实验，这是几乎不可能预测哪些的QList，QVector或std::vector产生最小的可执行代码。

这已经为众多的Qt良好的数据类型的参考样的类型，如QString，QByteArray等，其中包括无非PIMPL指针。对于这些类型，QList获得了一个重要的优化：当类型不大于指针时（请注意这个定义取决于平台的指针大小 - 32 或 64 位），而不是堆分配对象，对象存储在void*直接开槽。

但是，这只有在类型可以轻松重定位的情况下才有可能。这意味着它可以使用memcpy. 这里的重定位意味着我将一个对象memcpy带到另一个地址，并且 - 至关重要的是 -不运行旧对象的析构函数。

这就是事情开始出错的地方。因为与 Java 不同，在 C++ 中，对对象的引用是它的地址。而在原始 中QList，引用是稳定的，直到对象再次从集合中删除，通过将它们放入void*此属性不再保留的数组中。这不再是所有意图和目的的“列表”。

但是，事情继续出错，因为它们也允许将严格小于 a 的类型void*放在 a 中QList。但是内存管理代码需要指针大小的元素，因此QList添加了 padding(!)。这意味着QList<bool>64 位平台上的 a 看起来像这样：

[ | | | | | | | [ | | | | | | | [ ...
[b|   padding   [b|   padding   [b...

不像将 64 个布尔值放入缓存行，QVector而是QList只管理8 个。

当文档开始调用QList一个好的默认容器时，事情出现了任何比例的错误。它不是。在原来的STL状态：

Vector 是最简单的 STL 容器类，在许多情况下也是最有效的。

Scott Meyer 的Effective STL有几个以“Prefer std::vectorover...”开头的条目。

一般而言，C++ 的正确性不会因为您使用 Qt 而突然出错。

Qt 6 将修复那个特定的设计错误。同时，使用QVector或std::vector。