QVector vs QList
Asked Answered
D

5

87

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<T>, QLinkedList<T>, and QVector<T> 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.
Disaffection answered 6/7, 2011 at 19:47 Comment(0)
H
130

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.

Hypaethral answered 6/7, 2011 at 20:14 Comment(6)
FWIW, std::deque has pretty good guarantees about references. Iterators are easily invalidated, but pointers to members are pretty robust to operations on the dequeue.Flame
Great answer. But I have an additional question: Which is faster to iterate? I have a set of objects, they aren't really inserted or removed often, but I need to iterate over the objects as fast as possible. Which is faster?Pylle
Good info. I found the following statement most useful... "The QT library heavily favors the use of QList objects". In my use case, I am dealing with a QTableWidget, which likes QList and QListString. Therefore, let your use case dictate your decision between QVector and QList.Gather
Have you acually benchmarked std::deque against std::vector? You will be surprised...Unhallowed
Please bear in mind that the documentation has been updated following complains from Qt developers that QList is a poor recommendation as a default container. It now states: "QVector should be your default first choice. [...] However, QList is used throughout the Qt APIs for passing parameters and for returning values. Use QList to interface with those APIs." (QList documentation)Islamism
Furthermore, in Qt 6, QVector has been removed and replaced with an alias to QList, and QList has been replaced by the QVector's implementation, thus making both classes the same, and equal to the old QVectorInsnare
C
91

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 :

QVector should 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_TYPE or a Q_PRIMITIVE_TYPE using Q_DECLARE_TYPEINFO.

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

Clairclairaudience answered 28/4, 2017 at 10:0 Comment(4)
This should go up, and now be accepted as the answer.Scamp
Same comment as in the other answer: in Qt 6, QVector has been removed and replaced with an alias to QList, and QList has been replaced by the QVector's implementation, thus making both classes the same, and equal to the old QVectorInsnare
Besides making things confusing what was the reason for that? Do you have a link?Translatable
@Translatable Qt explained: "Previously, Qt featured very different implementations[...]: QVector being a natural and straightforward array-like container and QList being rather special in its implementation to nicely accommodate types defined and used by Qt itself. With Qt 6 updates to existing types, [...] it seemed that there is little to no benefit to have an implementation difference between the classes. Additionally, QVector proved to be a better choice in many cases. Thus, in Qt 6, QVector and QList are unified and the model of QVector is used..."Bollworm
K
14

In QVector is similar to std::vector. QLinkedList is similar to std::list. QList is an index based vector, but the memory position is not guaranteed (like std::deque).

Kamal answered 6/7, 2011 at 19:50 Comment(0)
G
3

From QtList doc:

  • 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

  • QVector to be preferred in case of a lot of append() or insert() of new items with size larger than a pointer since QVector allocates 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.

Giliane answered 27/5, 2013 at 16:37 Comment(0)
M
-3

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

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, QLinkedList works 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.

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

Michaelis answered 7/7, 2011 at 15:20 Comment(1)
-1: QVector doesn't come with heavy transactions as you claim because it preallocates and has a good grow/shrink strategy for appending and popping. Prepend/insertion indeed requires moving data ranges, but since they're continous in memory this is done very quickly (cache can work well with continous data, unlike with scattered heap chunks as with QList). Your second statement that QLinkedList is used for most purposes is plain wrong. It is most rarely used. You might be confusing it with QList?Suellen

© 2022 - 2024 — McMap. All rights reserved.