C++ QVector 与 QList

QVector vs QList

提问by jcuenod

I have a list of integers that I need to iterate over but an array is inadequate. What are the differences between vectorsand listsand is there anything I need to know before I pick a type?

我有一个需要迭代的整数列表，但数组不够用。vectors和lists和之间有什么区别，在选择类型之前我需要知道什么？

Just to be clear, I've read the QT docs but this is the extent of what I know:

为了清楚起见，我已经阅读了 QT 文档，但这是我所知道的范围：

QList<T>, QLinkedList<T>, and QVector<T>provide similar functionality. Here's an overview:

• For most purposes, QListis the right class to use. Its index-based API is more convenient than QLinkedList'siterator-based API, and it is usually faster than QVectorbecause 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.

QList<T>, QLinkedList<T>, 并QVector<T>提供类似的功能。这是一个概述：

• 对于大多数用途，QList是正确使用的类。它的基于索引的 API 比QLinkedList's基于迭代器的API 更方便，并且通常比QVector将其项存储在内存中的方式更快。它还扩展到您的可执行文件中更少的代码。
• 如果您需要一个真正的链表，并保证在列表中间插入常数时间并使用迭代器而不是索引，请使用QLinkedList.
• 如果您希望项目占用相邻的内存位置，请使用QVector。

回答by Dennis Zickefoose

QVectoris mostly analogous to std::vector, as you might guess from the name. QListis closer to boost::ptr_deque, despite the apparent association with std::list. It does not store objects directly, but instead stores pointers to them. You gain all the benefits of quick insertions at both ends, and reallocations involve shuffling pointers instead of copy constructors, but lose the spacial locality of an actual std::dequeor std::vector, and gain a lot of heap allocations. It does have some decision making to avoid the heap allocations for small objects, regaining the spacial locality, but from what I understand it only applies to things smaller than an int.

QVector大部分类似于std::vector，您可能会从名称中猜到。 QList更接近boost::ptr_deque，尽管与 有明显的关联std::list。它不直接存储对象，而是存储指向它们的指针。您可以获得两端快速插入的所有好处，重新分配涉及改组指针而不是复制构造函数，但失去了实际std::dequeor的空间局部性std::vector，并获得了大量堆分配。它确实有一些决策来避免小对象的堆分配，重新获得空间局部性，但据我所知，它仅适用于小于int.

QLinkedListis analogous to std::list, and has all the downsides of it. Generally speaking, this should be your last choice of a container.

QLinkedList类似于std::list，并且具有它的所有缺点。一般来说，这应该是您最后选择的容器。

The QT library heavily favors the use of QListobjects, so favoring them in your own code can sometimes avoid some unneccessary tedium. The extra heap use and the random positioning of the actual data can theoretically hurt in some circumstances, but oftentimes is unnoticable. So I would suggest using QListuntil profiling suggests changing to a QVector. If you expect contiguous allocation to be important [read: you are interfacing with code that expects a T[]instead of a QList<T>] that can also be a reason to start off with QVectorright off the bat.

QT 库非常喜欢使用QList对象，因此在您自己的代码中使用它们有时可以避免一些不必要的乏味。在某些情况下，额外的堆使用和实际数据的随机定位在理论上可能会造成伤害，但通常不会引起注意。所以我建议使用QList直到分析建议更改为QVector. 如果您希望连续分配很重要 [阅读：您正在与需要 aT[]而不是 a 的代码交互QList<T>]，这也可能是立即开始的原因QVector。

---

---

If you are asking about containers in general, and just used the QT documents as a reference, then the above information is less useful.

如果您是一般询问容器，并且只是使用 QT 文档作为参考，那么上述信息就没那么有用了。

An std::vectoris an array that you can resize. All the elements are stored next to each other, and you can access individual elements quickly. The downside is that insertions are only efficient at one end. If you put something in the middle, or at the beginning, you have to copy the other objects to make room. In big-oh notation, insertion at the end is O(1), insertion anywhere else is O(N), and random access is O(1).

Anstd::vector是一个可以调整大小的数组。所有元素都彼此相邻存储，您可以快速访问单个元素。缺点是插入仅在一端有效。如果在中间或开头放了一些东西，则必须复制其他对象以腾出空间。在 big-oh 符号中，最后插入是 O(1)，其他地方插入是 O(N)，随机访问是 O(1)。

An std::dequeis similar, but does not guarentee objects are stored next to each other, and allows insertion at both ends to be O(1). It also requires smaller chunks of memory to be allocated at a time, which can sometimes be important. Random access is O(1) and insertion in the middle is O(N), same as for a vector. Spacial locality is worse than std::vector, but objects tend to be clustered so you gain some benefits.

Anstd::deque类似，但不保证对象彼此相邻存储，并且允许在两端插入为 O(1)。它还需要一次分配较小的内存块，这有时很重要。随机访问为 O(1)，中间插入为 O(N)，与 a 相同vector。空间局部性比 差std::vector，但对象往往是聚集的，因此您可以获得一些好处。

An std::listis a linked list. It requires the most memory overhead of the three standard sequential containers, but offers fast insertion anywhere... provided you know in advance where you need to insert. It does not offer random access to individual elements, so you have to iterate in O(N). But once there, the actual insertion is O(1). The biggest benefit to std::listis that you can splice them together quickly... if you move an entire range of values to a different std::list, the entire operation is O(1). It is also much harder to invalidate references into the list, which can sometimes be important.

Anstd::list是一个链表。在三个标准顺序容器中，它需要的内存开销最大，但可以在任何地方快速插入……前提是您事先知道需要插入的位置。它不提供对单个元素的随机访问，因此您必须在 O(N) 中进行迭代。但是一旦到达那里，实际的插入是 O(1)。最大的好处std::list是您可以快速将它们拼接在一起……如果您将整个范围的值移动到不同的std::list，则整个操作是 O(1)。使列表中的引用无效也更加困难，这有时很重要。

As a general rule, I prefer std::dequeto std::vector, unless I need to be able to pass the data to a library that expects a raw array. std::vectoris guaranteed contiguous, so &v[0]works for this purpose. I don't remember the last time I used a std::list, but it was almost certainly because I needed the stronger guaretee about references remaining valid.

作为一般规则，我宁愿std::deque到std::vector，除非我需要能够将数据传递给需要原始阵列库。 std::vector保证连续，因此&v[0]适用于此目的。我不记得我上次使用 astd::list是什么时候了，但几乎可以肯定是因为我需要关于引用保持有效的更强保证。

回答by dlewin

Things have changed

事情变了

We are now in Qt 5.8 and things have changed, so the documentation. It gives a clear and different answer to this question :

我们现在在 Qt 5.8 中，事情发生了变化，所以文档。它对这个问题给出了明确而不同的答案：

QVectorshould 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_TYPEor a Q_PRIMITIVE_TYPEusing Q_DECLARE_TYPEINFO.

See the Pros and Cons of Using QListfor an explanation. However, QListis used throughout the Qt APIs for passing parameters and for returning values. Use QListto interface with those APIs.

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

有关QList解释，请参阅使用的优点和缺点。但是，QList在整个 Qt API 中都用于传递参数和返回值。用于QList与这些 API 交互。

回答by Naszta

In QVectoris similar to std::vector. QLinkedListis similar to std::list. QListis an index based vector, but the memory position is not guaranteed (like std::deque).

在QVector类似于std::vector. QLinkedList类似于std::list. QList是基于索引的向量，但不保证内存位置（如std::deque）。

回答by kiriloff

From QtList doc:

来自 QtList 文档：

• QList to be used in most cases. For structures with a thousand of items, enables efficient insertion in the middle, and provides indexed-access. prepend()and append()very fast since memory is preallocated at both ends of the internal array. QList<T>is an array of pointer of type T. If T has a pointer or Qt shared-like pointer type, object is stored directly in array

• QVectorto be preferred in case of a lot of append()or insert()of new items with size larger than a pointer since QVectorallocates memory for its items in a single heap allocation. For QList, insert of append of a new item requires memory allocation of the new item on the heap. In short, if you want the items to occupy adjacent memory positions, or if your items are larger than a pointer and you want to avoid the overhead of allocating them on the heap individually at insertion time, then use QVector.

• QList 在大多数情况下使用。对于具有一千个项目的结构，可以在中间有效插入，并提供索引访问。prepend()并且append()非常快，因为内存是在内部数组的两端预先分配的。QList<T>是一个 T 类型的指针数组。如果 T 有一个指针或 Qt 类共享指针类型，则对象直接存储在数组中

• QVector在大量append()或insert()新项目的大小大于指针的情况下首选，因为QVector在单个堆分配中为其项目分配内存。对于QList，插入新项目的追加需要在堆上分配新项目的内存。简而言之，如果您希望项目占用相邻的内存位置，或者您的项目大于指针并且您希望避免在插入时在堆上单独分配它们的开销，那么使用QVector.

回答by Nick

QVectoris like an array that can change size (increase or decrease) but it comes with heavy transactions and computation and time.

QVector就像一个可以改变大小（增加或减少）的数组，但它伴随着繁重的事务、计算和时间。

For example, if you want to add an item, a new array is created, all the items are copied to new array, the new item is added to the end, and old array is deleted. And vice versa to delete as well.

例如，如果要添加一个项目，则创建一个新数组，将所有项目复制到新数组中，将新项目添加到末尾，并删除旧数组。反之亦然删除。

However, QLinkedListworks with pointers. So when a new item is created, just a new memory space is allocated and linked to the only chunk of memory. Since it works with pointers it is faster and efficient.

但是，QLinkedList可以使用指针。因此，当创建一个新项目时，只会分配一个新的内存空间并将其链接到唯一的内存块。由于它与指针一起工作，因此速度更快，效率更高。

If you have list of items that you do not expect to change size much, QVectoris probably good, but usually QLinkedListis used for most purposes.

如果您有一些不希望改变大小的项目列表，这QVector可能很好，但通常QLinkedList用于大多数目的。