QList与QVector再探讨

Question

我的问题基本上是什么时候选择 QVector ，什么时候选择 QList 作为您的Qt容器。 我已经知道的：

1. Qt文档： QList类

对于大多数情况，QList是正确的类。它的基于索引的API比QLinkedList的基于迭代器的API更方便，并且由于它在内存中存储其项目的方式，通常比QVector更快。它还会扩展到可执行文件中的更少代码。

2. 同样写在这个非常受欢迎的Q&A中： QVector vs QList。它也支持QList。

3. 但是：在最近的Qt World Summit 2015 KDAB上，他们提出了“为什么QList有害”，这基本上在这里：

QList considered harmful

不要使用QList，使用Q_DECLARE_TYPEINFO

据我所知，这个想法是对于几乎所有类型的 QList 在分配新元素时都是低效的。每次添加新元素时，它都会调用 new （每个元素一次），与 QVector 相比，这是低效的。

这就是为什么现在我正在尝试理解：我们应该选择 QVector 作为默认容器吗？

- demonplus

---

我不相信“默认容器”这个概念的存在。 - user362515

嗯，所谓默认容器，我指的是在大多数情况下都可以使用的容器。就像Qt文档中所说的QList，“对于大多数情况来说，QList是正确的类”。 - demonplus

这仅仅是因为Qt对此使用了这种方式。(而你指出的两篇文章试图证明这不是一个好主意。) 无论如何，如果由于某些Qt接口而被迫使用它，那么它是“更好的选择”，否则——决定权在你手中，我看你已经阅读了足够的信息 :) - user362515

我的个人意见是，您可以根据情况选择QList或QVector，但Qt文档在这一点上有误导。这让我感到惊讶，因为通常它非常好。 - demonplus

Answer 1

Qt将QList称为“万能工具”，但这句话的另一半是“样样皆通，样样不精”。如果您计划在列表的两端添加内容，并且它们不大于指针大小，那么我认为QList是一个很好的选择，因为QList会在列表前后保留空间。就好像这些就是使用QList的好理由。 QList会自动将“大”对象存储为指针并在堆上分配对象，这可能是一个好事情，如果您是一个不知道如何声明QVector<T*>并使用动态分配的新手。这不一定是好事，在某些情况下，它只会膨胀内存使用量并增加额外的间接性。我认为明确表达自己的意图总是一个好主意，无论是指针还是实例。即使您确实想要堆分配，也最好自己分配，然后将指针添加到列表中，而不是构造对象，然后在堆上复制构造对象。

在许多地方，Qt会返回一个带有开销的QList，例如获取一个QObject的子项或搜索子项时。在这种情况下，使用一个在第一个元素之前分配空间的容器是没有意义的，因为它是已经存在的对象列表，而不是您可能要添加到前面的内容。我也不太喜欢缺少resize()方法。

想象一下，您有一个大小为9个字节且在64位系统上具有字节对齐的对象。这对于QList来说“太大了”，因此它将使用8字节指针+慢速堆分配的CPU开销+堆分配的内存开销。它将使用两倍的内存，并带有额外的间接性访问，很难像广告中那样提供性能优势。

至于为什么QVector不能突然成为“默认”容器 - 在比赛中你不会换马 - 这是一个遗留问题，Qt是一个如此古老的框架，即使许多东西已被弃用，更改广泛使用的默认值并不总是可能的，不会破坏大量代码或产生不希望的行为。无论好坏，QList都可能继续成为默认容器，直到Qt 5结束，很可能在下一个主要版本中也是如此。这也是Qt将继续使用“愚蠢”指针的原因，尽管智能指针已成为必需品，每个人都在抱怨普通指针有多糟糕，永远不应该使用它们。

话虽如此，没有人强迫您在设计中使用QList。没有理由不将QVector作为默认容器。我自己并没有在任何地方使用QList，在返回QList的Qt函数中，我仅将其用作临时变量以将内容移动到QVector中。

此外，这只是我的个人观点，但我发现Qt中有很多设计决策在性能、内存使用效率或易用性方面并不合理。总的来说，有很多框架和语言喜欢推广他们的做事方式，不是因为这是最好的方法，而是因为这是他们的做事方式。

最后：

对于大多数情况，QList是正确的类。

这实际上取决于你对此的理解。在这种情况下，我认为“正确的”并不代表“最好的”或“最优的”，而是代表“足够好”，即“它可以胜任，即使不是最好的”。特别是如果你不知道不同的容器类及其工作原理。

归纳一下：

QList的优点：

- 您打算在列表前置对象大小不超过指针大小时使用，因为它会在前面保留一些空间。 - 您打算在列表中间插入对象（实质上）比指针大得多的对象（我在这里非常慷慨，因为您可以轻松地使用显式指针的QVector来实现相同且更便宜的操作——没有额外的复制），因为调整列表大小时，不会移动任何对象，只有指针。

QList的缺点：

- 没有resize()方法，reserve()是一个微妙的陷阱，因为它不会增加有效的列表大小，即使索引访问起作用，它也属于UB类别，也无法迭代该列表。 - 当对象大于指针时，会进行额外的复制和堆分配，如果对象标识很重要，这也可能是一个问题。 - 使用额外的间接访问比指针大的对象。 - 由于最后两个原因，具有CPU时间和内存使用开销，同时更少的缓存友好性。 - 当用作“搜索”返回值时，会带来额外的开销，因为您不太可能在其前面或后面添加内容。 - 只有在必须使用索引访问时才有意义，对于最佳的前置和插入性能，链表可能是更好的选择。

CONs略微超过PROs，这意味着在“非正式”使用中，QList可能是可以接受的，但在CPU时间和/或内存使用量是关键因素的情况下，绝对不要使用它。总的来说，QList最适合懒惰和粗心的使用，当您不想考虑用例的最佳存储容器时，通常会使用QVector<T>、QVector<T*>或QLinkedList（我排除了“STL”容器，因为我们在谈论Qt，Qt容器同样具有可移植性，有时更快，并且肯定更易于使用和更清晰，而std容器则是不必要的冗长）。

- dtech

---

自然而然，我完全不同意你的观点。你让QList听起来好像在负载类型不大于一个指针的情况下不会堆分配内存。那只是两个条件之一。另一个条件是该类型被类作者明确标记为可轻松重新定位的。大多数人都不会这样做。大多数Qt开发者（与Qt一起工作而不是使用Qt的开发者）也不会这样做。因此，从实际效果来看，QList可以被视为一个数组列表（指针的向量）。问题是，对于大多数用例来说，数组列表并不是一个好的数据类型。 - Marc Mutz - mmutz

QList 不会出现在 Qt 6 中，至少不会以当前的形式呈现。 - Marc Mutz - mmutz

@MarcMutz-mmutz - 你说的很重要，但我觉得因为某些根本没有提到的“错误”而“自然完全不同意”答案是相当荒谬的。此外，即使是关于QList的最新文档，似乎也没有提到“可以平凡地重新分配”类型或任何相关主题，所以请随意填补我的回答和Qt文档中的任何遗漏，而不要夸大其词。 - dtech

@ddriver：我不同意“随意”使用QList的观点。这是不可接受的。 - Marc Mutz - mmutz

@MarcMutz-mmutz - 我认为“随意使用”甚至不与“容器保证”相匹配，你再次强调了无需强调的事情。如果你想要保证，就不要随意对待它。我个人从未选择使用QList，只有在Qt API返回它时才使用它。此外，正如我的答案结论所指出的那样，QList的负面影响超过了积极影响，并且QList是“懒惰和粗心的使用”。所以...你有点夸张了。 - dtech

Answer 2

在Qt 5.7中，有关此处讨论的主题，文档已经进行了更改。现在在QVector中指出：

QVector应该是您的默认首选。 QVector<T>通常比QList<T>具有更好的性能，因为QVector<T>始终将其项目按顺序存储在内存中，而QList<T>会在堆上分配其项目，除非sizeof(T) <= sizeof(void*)并且使用Q_DECLARE_TYPEINFO声明了T为Q_MOVABLE_TYPE或Q_PRIMITIVE_TYPE之一。

他们参考了Marc Mutz的这篇文章。

因此，官方观点已经改变。

- demonplus

---

很遗憾他们没有清晰地更新容器类页面。它首先说“如果需要一个可变大小的QString数组，请使用QVector<QString>”，而在此之后却说“对于大多数应用程序，使用QList是最好的类型”。 - ymoreau

到了2017年底，在Qt 5.10文档中，所有这些混乱仍然存在 :( - demonplus

Answer 3

QList是一个void*数组。

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

但是，数组列表的调整大小可以分解为无类型辅助类（QListData），这应该能够节省一些可执行代码大小。在我的实验中，几乎不可能预测哪个QList、QVector或std::vector会产生最少的可执行代码。

这是许多类似于QString、QByteArray等仅由pimpl指针组成的Qt引用类型的好数据类型。对于这些类型，当类型不大于指针时（请注意，此定义取决于平台的指针大小-32位或64位），QList获得了重要的优化：对象不再在堆上分配，而是直接存储在void*插槽中。

然而，这只有在类型可以被轻松地重定位时才可能实现。这意味着可以使用memcpy将一个对象在内存中重定位。重定位在这里的意思是我拿出一个对象，在另一个地址上进行memcpy，并且重要的是不运行旧对象的析构函数。

这就是事情开始出错的地方。因为与Java不同，在C++中，对对象的引用是其地址。而通过将它们放入void*数组中，尽管在原始的QList中，引用在对象从集合中移除之前是稳定的，但这种属性不再有效。从所有目的来看，这不再是一个“列表”。

事情继续出现问题，因为它们允许比 void* 更小的类型被放置在 QList 中。但是内存管理代码希望指针大小的元素，所以 QList 添加了填充(!)。这意味着在64位平台上，QList<bool> 看起来像这样:

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

与 QVector 不同，QList 只能将 64 个布尔值放入缓存行中，而只有 8 个。

当文档开始称 QList 为一个好的默认容器时，事情变得不成比例。原始STL规范指出：

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

Scott Meyer 的 Effective STL 中有几项以“优先使用 std::vector 而不是…” 开头。

在一般的C++中正确的东西并不会因为你使用Qt而突然变得错误。

Qt 6 将修复那个特定的设计错误。 在此期间，请使用 QVector 或 std::vector。

- Marc Mutz - mmutz

Answer 4

如果QList的元素类型大小大于指针大小，那么QList的性能会比QVector更好，因为它不是按顺序存储对象，而是按顺序存储指向堆副本的指针。

我倾向于相反的意见。当遍历项目时，如果将其存储为堆上的指针，QList会比QVector差得多吗？顺序存储(QVector一直)之所以很好，是因为它对缓存友好，一旦存储指针，就会失去数据局部性，开始出现缓存未命中，并且对性能非常不利。

"默认"容器应该是QVector（或std :: vector），如果您担心大量重新分配，则可以预先分配合理的数量，支付一次性成本，从长远来看会受益。

默认情况下使用*Vector，如果遇到性能问题，请进行分析并根据需要进行更改。

- Tom Kulaga

---

我也同意。如果我有一个8字节的结构体，并将100个它们添加到QVector中，我会使用大约800字节，再加上一些管理开销。如果我将相同的8字节结构体添加到QList中100次，我需要（假设32位）分配400字节用于指针和额外的100个8字节堆分配，再加上更多的管理开销。这是非常低效的。QList有其存在的价值，但对于嵌入式来说，它是一个有吸引力的麻烦，特别是在堆碎片化是一个真正的问题的情况下。 - locka

Answer 5

请注意，这在Qt6中已完全更改：https://www.qt.io/blog/qlist-changes-in-qt-6 QVector和QList合并了，使用QVector的模型作为底层实现。这意味着Qt 5 QList对于通用类型的额外间接级别现在已经消失了，元素总是直接存储在分配的内存中。QList是真正的类，拥有实现，而QVector只是一个别名。 Qt 6中的QList支持优化的prepend（向列表头部添加元素）。它现在可以在删除元素时缩小而无需使用reserve。并且2GB大小限制已被移除。

- Silicomancer

Answer 6

根据文档所述，QList是通常使用的最佳容器。如果元素类型的大小<=指针大小=机器和操作系统位数=4或8字节，则对象以与QVector相同的方式顺序存储在内存中。如果QList的元素类型大小大于指针大小，则QList比QVector表现更好，因为它不会按顺序存储对象，而是按顺序存储指向堆副本的指针。 在32位情况下，情况如下：

sizeof( T ) <= sizeof( void* )
=====
QList< T > = [1][1][1][1][1]
                   or
             [2][2][2][2][2]
                   or
             [3][3][3][3][3]
                   or
             [4][4][4][4][4] = new T[];

sizeof( T ) > sizeof( void* )
=====
QList< T > = [4][4][4][4][4] = new T*[]; // 4 = pointer's size
              |   |  ...  |
           new T new T   new T

如果您希望无论元素大小，对象都按顺序在内存中布局，就像OpenGL编程通常所做的那样，那么您应该使用QVector。

这里有一个 QList内部详细描述。

- Ivan Caravanio

---

全错了。QList 只与 QVector 和 C 数组兼容，当 sizeof T == sizeof void* 时才兼容。如果该类型被明确标记为 Q_MOVABLE_TYPE，则也可以兼容。是的，这在32位和64位平台上有所不同。如果 sizeof T < sizeof void*，则 QList 会填充。因此，QList<bool> 使用的内存量是 QVector<bool> 的8倍，是 std::vector<bool> 的64倍，尽管 std::vector 的 bool 特化被广泛认为是一个错误。 - Marc Mutz - mmutz

Answer 7

QList 的行为取决于其存储的元素类型（参见 源代码 struct MemoryLayout）：

• 如果 sizeof T == sizeof void* 并且 T 被定义为 Q_MOVABLE_TYPE，那么 QList<T> 的行为与 QVector 完全相同，即数据在内存中是连续存储的。

• 如果 sizeof T < sizeof void* 并且 T 被定义为 Q_MOVABLE_TYPE，那么 QList<T> 每个条目都会填充到 sizeof void*，并且会失去与 QVector 的布局兼容性。

• 在所有其他情况下，QList<T> 是一个链表，因此在某种程度上速度较慢。

这种行为使得QList<T>几乎总是一个不好的选择，因为根据一些微妙的细节，QList<T>要么是一个列表，要么是一个向量。这是糟糕的API设计，容易出错。（例如，如果您有一个带有公共接口的库，其在内部和公共接口中使用QList<MyType>，但忘记将MyType声明为Q_MOVABLE_TYPE，则会遇到错误。稍后，您想添加Q_MOVABLE_TYPE。这是二进制不兼容的，意味着现在您必须重新编译所有使用您的库的代码，因为QList<MyType>的内存布局在公共API中发生了变化。如果您不小心，您将会忽略这个问题并且引入一个bug。这很好地说明了为什么在这里QList是个糟糕的选择。）

尽管如此，QList还不完全是坏的：在大多数情况下，它可能会做你想要的事情，但也许它在幕后以与您预期不同的方式完成工作。

经验法则是：

使用QVector<T>或QVector<T*>代替QList，因为它明确说明了你想要什么。你可以将其与std::unique_ptr相结合使用。 在C++11及以后的版本中，甚至被认为最好只使用std::vector，因为它在range-based for loop中的行为是正确的（QVector和QList可能会分离并且执行深复制）。 你可以在Marc Mutz的演示文稿和Olivier Goffart的视频中找到所有这些细节以及更多内容。

- dhaumann

---

第一个情况需要使用等于号，而不是小于等于号。然后再添加另一个情况：- 如果 T 的大小小于 void* 的大小，并且 T 被定义为 Q_MOVABLE_TYPE，那么 QList<T> 会将每个条目填充到 sizeof void*，并且会失去与 QVector 的布局兼容性。然后描述就正确了。 - Marc Mutz - mmutz

Answer 8

假设我们有一个DataType类。

QVector是对象数组，例如：

// QVector<DataType> internal structure
DataType* pArray = new DataType[100];

QList - 指向对象的指针数组，例如：

// QList<DataType> internal structure
DataType** pPointersArray = new DataType*[100];

因此，对于 QVector，通过索引的直接访问将更快：

{
// ...
cout << pArray[index]; //fast
cout << *pPointersArray[index]; //slow, need additional operation for dereferencing
// ...
}

但是如果 DataType 的大小大于 DataType* 的大小，对于 QList 来说交换会更快：

{
// QVector swaping
DataType copy = pArray[index];
pArray[index] = pArray[index + 1];
pArray[index + 1] = copy; // copy object

// QList swaping
DataType* pCopy = pPointersArray [index];
pPointersArray[index] = pPointersArray [index + 1];
pPointersArray[index + 1] = pCopy; // copy pointer
// ...
}

因此，如果您需要直接访问元素而无需进行交换操作（例如排序），或者 sizeof(DataType) <= sizeof(DataType*)，则更好的方法是使用 QVector。否则，请使用 QList。

- synacker

---

这不是正确的：根据内容类型，QList 就像 QVector 一样在后台实现，因此应该被否决。 - dhaumann

@dhaumann，你能提供文档或源代码的链接吗？ - synacker

更好的是，观看这个视频。 - dhaumann

@dhaumann 我看到了所有的内容，但仍然不明白 QList 如何可以拥有像 QVector 这样的结构。 - synacker

@dhaumann Q_MOVABLE_TYPE 对于所有类型的 Qt 容器都有意义，它表示容器可以通过 memcpy 函数复制元素，或者需要调用复制构造函数，这总是更慢的。我没有看到 QList 在 Q_MOVABLE_TYPE 上有任何依赖。我在源代码中看到了对 sizeof(void*) 的内存布局依赖，但仍然不明白如果 sizeof(DataType) == sizeof(void*)，QVector 结构是否与 QList 相同。 - synacker