QVector和QList [英] QVector vs QList
问题描述
我有一个整数列表，我需要迭代，但一个数组是不够的。
向量和列表之间的区别是什么，在选择类型之前，我需要知道什么？
为了清楚，我已经阅读QT文档，但这是我知道的程度：
QList，QLinkedList和QVector提供类似的功能。这里是一个概述：
- 对于大多数用途，QList是正确的类使用。它的基于索引的API比QLinkedList的基于迭代器的API更方便，它通常比QVector快，因为它将它的项目存储在内存中。
- 如果您需要一个真正的链表，保证在列表中间有固定的时间插入，并且迭代器到项而不是索引，请使用
$ b $
< b
QVector 大多类似于 std :: vector ，因为你可能从名字猜到。 QList 更接近 boost :: ptr_deque ，尽管与 std :: list 。它不直接存储对象，而是存储指向它们的指针。你获得了在两端快速插入的所有好处，重新分配涉及混洗指针而不是复制构造函数，但丢失实际 std :: deque 或<$的空间局部性c $ c> std :: vector ，并获得很多堆分配。它有一些决定避免对小对象的堆分配，重新获得空间局部性，但从我的理解它只适用于小于 int 的事情。 p>
QLinkedList 类似于 std :: list 它的所有缺点。一般来说，这应该是你最后一个容器的选择。
QT库非常喜欢使用 QList 对象，所以在自己的代码中赞成他们有时可以避免一些不必要的烦琐。额外的堆使用和实际数据的随机定位在某些情况下理论上可能受损，但通常是不可察觉的。所以我建议使用 QList ，直到分析建议更改为 QVector 。如果你期望连续分配是重要的[读：你正在与期望 T [] 而不是 QList< T& code>]，也可以是刚开始使用 QVector 的原因。
如果你一般地询问容器，并且仅仅使用QT文档作为参考，那么上面的信息就不太有用。
std :: vector 是可以调整大小的数组。所有元素都彼此相邻存储，您可以快速访问各个元素。缺点是插入只在一端有效。如果你把东西放在中间，或在开始，你必须复制其他对象，以腾出空间。在大-Ω符号中，在末尾的插入是O（1），在任何其他地方插入是O（N），并且随机存取是O（1）。
std :: deque 是类似的，但不会保证对象彼此相邻，并允许在两端插入为O（1）。它还需要一次分配较小的内存块，这有时很重要。随机访问是O（1），中间插入是O（N），与向量相同。空间局部性比 std :: vector 更糟糕，但对象往往是聚集的，所以你获得一些好处。
std :: list 是一个链表。它需要三个标准顺序容器的最大内存开销，但提供快速插入任何地方...只要你事先知道你需要插入。它不提供对各个元素的随机访问，所以你必须在O（N）中进行迭代。但一旦有，实际插入是O（1）。对 std :: list 最大的好处是你可以将它们快速拼接...如果你将一个完整的值范围移动到不同的 std :: list ，整个操作是O（1）。
作为一般规则，我更喜欢 std :: deque 到 std :: vector ，除非我需要能够将数据传递到需要原始数组的库。 std :: vector 保证连续，因此& v [0] 可用于此目的。我不记得最后一次我使用 std :: list ，但它几乎肯定是因为我需要更强的guaretee关于引用保持有效。
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?
Just to be clear, I've read the QT docs but this is the extent of what I know:
QList, QLinkedList, and QVector provide similar functionality. Here's an overview:
- For most purposes, QList is the right class to use. Its index-based API is more convenient than QLinkedList's iterator-based API, and it is usually faster than QVector because 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 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 is analogous to std::list, and has all the downsides of it. Generally speaking, this should be your last choice of a container.
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.
If you are asking about containers in general, and just used the QT documents as a reference, then the above information is less useful.
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 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.
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.
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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
