問題描述
我有一個需要迭代的整數列表，但數組不夠用.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的文章就介紹到這了，希望我們推薦的答案對大家有所幫助，也希望大家多多支持html5模板網！