问题描述
我有一个需要迭代的整数列表，但数组不够用.vectors 和 lists 之间有什么区别，在选择类型之前有什么我需要知道的吗?
I have a list of integers that I need to iterate over but an array is inadequate.
What are the differences between vectors and lists and is there anything I need to know before I pick a type?
为了清楚起见，我已经阅读了 QT 文档，但这是我所知道的范围:
Just to be clear, I've read the QT docs but this is the extent of what I know:
QList、QLinkedList 和 QVector 提供类似的功能.概览如下:
QList<T>,QLinkedList<T>, andQVector<T>provide similar functionality. Here's an overview:
- 在大多数情况下，
QList是适合使用的类.它的基于索引的 API 比基于QLinkedList 的迭代器的 API 更方便，并且通常比QVector更快，因为它将其项存储在内存中的方式.它还可以扩展到您的可执行文件中更少的代码. - 如果您需要一个真正的链表，并保证在列表中间插入恒定时间并使用迭代器而不是索引，请使用
QLinkedList. - 如果您希望项目占据相邻的内存位置，请使用
QVector.
- For most purposes,
QListis the right class to use. Its index-based API is more convenient thanQLinkedList'siterator-based API, and it is usually faster thanQVectorbecause 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.
推荐答案
QVector 大部分类似于 std::vector，您可能会从名称中猜到.QList 更接近于 boost::ptr_deque，尽管与 std::list 有明显的关联.它不直接存储对象，而是存储指向它们的指针.您可以获得两端快速插入的所有好处，并且重新分配涉及改组指针而不是复制构造函数，但失去了实际 std::deque 或 std::vector<的空间局部性/code>，并获得大量的堆分配.它确实有一些决策来避免小对象的堆分配，重新获得空间局部性，但据我所知，它只适用于小于 int 的东西.
QVector is mostly analogous to std::vector, as you might guess from the name. QList is 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::deque or 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.
QLinkedList 类似于 std::list，并且具有它的所有缺点.一般来说，这应该是你最后选择的容器.
QLinkedList is analogous to std::list, and has all the downsides of it. Generally speaking, this should be your last choice of a container.
QT 库非常喜欢使用 QList 对象，因此在您自己的代码中使用它们有时可以避免一些不必要的乏味.在某些情况下，额外的堆使用和实际数据的随机定位在理论上可能会造成伤害，但通常不会引起注意.所以我建议使用 QList 直到分析建议更改为 QVector.如果您希望连续分配很重要 [阅读:您正在与需要 T[] 而不是 QList] 的代码交互，这也可能是一个原因立即开始使用 QVector.
The QT library heavily favors the use of QList objects, 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 QList until 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 QVector right off the bat.
如果你问的是一般的容器，只是参考了 QT 文档，那么上面的信息用处不大.
If you are asking about containers in general, and just used the QT documents as a reference, then the above information is less useful.
std::vector 是一个可以调整大小的数组.所有元素都彼此相邻存储，您可以快速访问单个元素.缺点是插入仅在一端有效.如果在中间或开头放了一些东西，则必须复制其他对象以腾出空间.在 big-oh 符号中，最后插入是 O(1)，其他地方插入是 O(N)，随机访问是 O(1).
An std::vector is 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).
An std::deque 类似，但不保证对象彼此相邻存储，并且允许两端插入为 O(1).它还需要一次分配较小的内存块，这有时很重要.随机访问是 O(1)，中间插入是 O(N)，与 vector 相同.空间局部性比 std::vector 差，但对象往往是聚类的，因此您可以获得一些好处.
An std::deque is 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.
std::list 是一个链表.在三个标准顺序容器中，它需要的内存开销最大，但可以在任何地方快速插入……前提是您提前知道需要插入的位置.它不提供对单个元素的随机访问，因此您必须在 O(N) 中进行迭代.但是一旦到达那里，实际的插入是 O(1).std::list 的最大好处是您可以快速将它们拼接在一起……如果您将整个范围的值移动到不同的 std::list，整个操作是 O(1).使列表中的引用无效也更加困难，这有时很重要.
An std::list is 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::list is 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.
作为一般规则，我更喜欢 std::deque 到 std::vector，除非我需要能够将数据传递给需要原始数组.std::vector 保证是连续的，因此 &v[0] 用于此目的.我不记得上次使用 std::list 是什么时候，但几乎可以肯定是因为我需要更强的保证引用保持有效.
As a general rule, I prefer std::deque to std::vector, unless I need to be able to pass the data to a library that expects a raw array. std::vector is 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.
这篇关于QVector 与 QList的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持跟版网！