23

我的问题基本上是何时选择QVector以及何时选择QList作为 Qt 容器。我已经知道的：

  1. Qt 文档：QList 类

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

  1. 同样写的是这个非常流行的问答：QVector vs QList。它也有利于 QList。

  2. 但是：在最近的 2015 年 Qt 世界峰会上，KDAB 提出了“为什么 QList 有害”，这基本上是在这里：

QList 被认为是有害的

不要使用 QList，使用 Q_DECLARE_TYPEINFO

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

这就是为什么现在我想了解：QVector我们应该选择它作为默认容器吗？

4

8 回答 8

25

Qt 标榜QList为“万事通”，但那句话的另一半是“无所事事”。QList如果您计划附加到列表的两端，并且它们不大于指针，我会说这是一个很好的候选者，因为QList在之前和之后保留空间。就是这样，我的意思是就使用QList的充分理由而言。

QListQVector<T*>会自动将“大”对象存储为指针并在堆上分配对象，如果你是一个不知道如何声明 a和使用动态分配的婴儿，这可能是一件好事。这不一定是一件好事，在某些情况下它只会增加内存使用量并增加额外的间接性。IMO 明确说明您想要什么总是一个好主意，无论是指针还是实例。即使您确实想要堆分配，最好自己分配它并简单地将指针添加到列表中，而不是构造一次对象，然后在堆上进行复制构造。

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

想象一下这样一种情况，在 64 位系统上，您有一个大小为 9 字节且字节对齐的对象。它“太多了”，QList因此它将使用 8 字节指针 + CPU 开销用于慢速堆分配 + 内存开销用于堆分配。它将使用两倍的内存和额外的间接访问，它几乎不会像宣传的那样提供性能优势。

至于为什么QVector不能突然成为“默认”容器——你不会在比赛中途换马——这是一个遗留问题，Qt 是一个如此古老的框架，尽管很多东西已经被弃用，但对广泛的变化使用默认值并不总是可行的，除非会破坏大量代码或产生不良行为。无论好坏，QList很可能在整个 Qt 5 中一直是默认设置，并且可能在下一个主要版本中也是如此。同样的原因，Qt 将继续使用“哑”指针，多年来智能指针已成为必须，每个人都在哭泣普通指针有多糟糕以及它们永远不应该被使用。

话虽如此，没有人会强迫您在设计中使用QList。没有理由不QVector应该成为您的默认容器。我自己不在QList任何地方使用，并且在返回 a 的 Qt 函数中，QList我只是用作临时将东西移动到QVector.

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

最后但并非最不重要的：

对于大多数用途，QList 是正确使用的类。

这真的归结为你如何理解这一点。IMO 在这种情况下，“正确”不代表“最好”或“最佳”，而是代表“足够好”，如“它会做，即使不是最好的”。特别是如果您对不同的容器类及其工作方式一无所知。

对于大多数目的，QList 可以。

总结一下：

QList专业人士

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

QList缺点

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

CON 略高于 PRO，这意味着虽然“随意”使用QList可能是可以接受的，但您绝对不想在 CPU 时间和/或内存使用是关键因素的情况下使用它。总而言之，QList最适合懒惰和粗心的使用，当您不想为用例考虑最佳存储容器时，通常是 a QVector<T>， aQVector<T*>或 a QLinkedList（我排除“STL”容器，因为我们在这里讨论的是 Qt，所以 Qt 容器同样具有便携性，有时速度更快，而且使用起来肯定更容易、更干净，而std容器则不必要地冗长）。

于 2015-11-26T20:25:35.817 回答
19

在 Qt 5.7 中，有关此处讨论的主题的文档发生了更改。在QVector中现在声明：

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

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

所以官方的观点发生了变化。

于 2016-07-08T09:48:55.723 回答
5

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*放在 aQList中。但是内存管理代码需要指针大小的元素，因此QList添加了填充（！）。这意味着QList<bool>64 位平台上的 a 如下所示：

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

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

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

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

Scott Meyer 的Effective STLstd::vector有几个以“Prefer over...”开头的项目。

一般情况下，C++ 不会因为您使用 Qt 而突然出错。

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

于 2016-03-01T23:00:33.387 回答
3

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

我倾向于说相反的话。在检查这些项目时，情况会更糟。如果它将它作为指针存储在堆上，QList 不会比 QVector 更糟糕吗？顺序存储（一直是 QVector）之所以如此出色，是因为它对缓存友好，一旦存储指针，就会失去数据局部性，开始出现缓存未命中，这对性能来说很糟糕。

恕我直言，“默认”容器应该是 QVector（或 std::vector），如果您担心大量重新分配，请预先分配合理的数量，支付一次性成本，从长远来看，您将受益。

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

于 2015-11-12T06:56:27.373 回答
2

请注意，这在 Qt6 中已经完全改变： https ://www.qt.io/blog/qlist-changes-in-qt-6

QVector 和 QList 统一，使用 QVector 的模型作为底层实现。这意味着 Qt 5 QList 对泛型类型的额外间接级别现在已经消失，元素总是直接存储在分配的内存中。QList 是真正的类，有实现，而 QVector 只是 QList 的别名。Qt 6 中的 QList 支持优化的前置。它现在可能会在不使用保留的情况下在元素移除时缩小。并且取消了 2GB 的大小限制。

于 2020-12-20T21:21:52.537 回答
0

QList 是文档所述的一般使用的最佳容器。如果元素类型的大小 <= 指针大小 = machine & OS bitness = 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 内部的详细描述。

于 2015-11-09T13:19:35.230 回答
0

Imagine, that we have DataType class.

QVector - array of objects, such as:

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

QList - array of pointers to objects, such as:

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

Therefore, direct access by index will be faster for QVector:

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

But swaping will be faster for QList, if sizeof(DataType) > sizeof(DataType*):

{
// 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
// ...
}

So, if you need direct access without swaping operations between elements (such as sorting, for example), or sizeof(DataType) <= sizeof(DataType*), your better way is use QVector. In other case use QList.

于 2015-11-30T12:22:47.413 回答
0

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>内部和其公共接口中使用 a sizeof MyType is < sizeof void*，但您忘记将 MyType 声明为，您将遇到错误Q_MOVABLE_TYPE。稍后，您想添加Q_MOVABLE_TYPE。这是二进制不兼容的，这意味着你现在必须重新编译所有使用你的库的代码，因为QList<MyType>公共 API 中的内存布局发生了变化。如果你不小心，你会错过这个并引入一个错误。这很好地说明了为什么 QList 是一个糟糕的选择这里。）

也就是说，QList 仍然不是完全坏的：它可能会在大多数情况下做你想做的事，但它可能会在幕后完成与你所期望的不同的工作。

经验法则是：

  • QVector<T>使用or代替 QList，QVector<T*>因为它明确说明了您想要什么。您可以将其与std::unique_ptr.

  • 在 C++11 及更高版本中，甚至认为最好只使用std::vector，因为它会在基于范围的 for 循环中正确运行。（QVector 和 QList 可能会分离，因此会执行深度复制）。

您可以在Marc Mutz 的演示文稿和Olivier Goffart的视频中找到所有这些细节和更多信息。

于 2015-11-30T12:56:20.813 回答