QList vs QVector revisited
Qt advertises QList
as the "jack of all trades", but the other half of that saying is "master of none". I'd say QList
is a good candidate if you plan on appending to both ends of the list, and those are no larger than than a pointer, as QList
reserves space before and after. That's about it, I mean as far as good reasons to use QList
are concerned.
QList
will automatically store "large" objects as pointer and allocate the objects on the heap, which may be considered a good thing if you are a baby, which doesn't know how to declare a QVector<T*>
and use dynamic allocation. This is not necessarily a good thing, and in some cases it will only bloat the memory usage and add extra indirection. IMO it is always a good idea to be explicit about what you want, whether it is pointers or instances. Even if you do want heap allocation, it is always better to allocate it yourself and simply add the pointer to the list than construct the object once, then have have copy construct that on the heap.
Qt will return you a QList
in a lot of places where it comes with overhead, for example when getting a QObject
's children or you search for children. In this case it doesn't make sense to use a container that allocates space before the first element, as it is a list of objects which are already there, not something you are likely to prepend to. I also don't much like the absence of a resize()
method.
Imagine a situation where you have an object with size of 9 bytes and byte alignment on a 64 bit system. It is "far too much" for QList
so instead it will use 8 byte pointer + CPU overhead for the slow heap allocation + memory overhead for the heap allocation. It will use twice the memory and with an extra indirection for access it will hardly offer performance advantages as advertised.
As of why QVector
cannot suddenly become the "default" container - you don't change horses mid-race - it is a legacy thing, Qt being such an old framework, and even though a lot of stuff has been deprecated, making changes to widely used defaults is not always possible, not without breaking a lot of code, or producing undesired behavior. Good or bad, QList
will likely continue being the default all the way throughout Qt 5, and likely in the next major release as well. The same reason Qt will continue using "dumb" pointers, for years after smart pointers have become a must and everybody is crying about how bad plain pointers are and how they should not be used ever.
That being said, nobody is forcing you to use QList
in your design. There is no reason why QVector
should not be your default container. I myself don't use QList
anywhere, and in the Qt functions which return a QList
I merely use as a temporary to move stuff into a QVector
.
Furthermore, and this is only my personal opinion, but I do find a lot of design decisions in Qt that don't necessary make sense, be that performance or memory use efficiency or ease of use wise, and overall there are a a lot of frameworks and languages which like promoting their ways of doing things, not because it is the best way to do it, but because it is their way to do it.
Last but not least:
For most purposes, QList is the right class to use.
It really boils down to how you understand this. IMO in this context, "the right" does not stand for "the best" or "the optimal", but for "good enough" as in "it will do, even if not the best". Especially if you know nothing about different container classes and how they work.
For most purposes, QList will do.
To sum things up:
QList
PROs
- you intend to prepend objects no larger than the size of a pointer, since it reserves some space in the front
- you intend to insert in the middle of the list objects (substantially) larger than a pointer (and I am being generous here, since you can easily use
QVector
with explicit pointers to achieve the same and cheaper - no extra copy), since when resizing the list, no objects will be moved, only pointers
QList
CONs
- doesn't have a
resize()
method,reserve()
is a subtle trap, since it will not increase the valid list size, even if index access works it falls in the UB category, also you will not be able to iterate that list - does an extra copy and heap allocating when object is larger than a pointer, which might also be an issue if object identity matters
- uses extra indirection to access objects larger than a pointer
- has CPU time and memory usage overheads due to the last two, also less cache friendly
- comes with additional overhead when used as a "search" return value, since you are not likely to prepend or even append to that
- only makes sense if index access is a must, for optimal prepend and insert performance a linked list might be a better option.
The CON's marginally outweigh the PROs, meaning that while in "casual" use QList
might be acceptable, you definitely don't want to use it in situations where CPU time and/or memory usage are a critical factor. All in all, QList
is best suited for lazy and careless use, when you don't want to make the consideration of optimal storage container for the use case, which would typically be a QVector<T>
, a QVector<T*>
or a QLinkedList
(and I exclude "STL" containers, since we are talking Qt here, Qt containers are just as portable, sometimes faster, and most certainly easier and cleaner to use, whereas std
containers are needlessly verbose).
In Qt 5.7, the documentation was changed concerning the topic discussed here. In QVector it is now stated:
QVector
should be your default first choice.QVector<T>
will usually give better performance thanQList<T>
, becauseQVector<T>
always stores its items sequentially in memory, whereQList<T>
will allocate its items on the heap unlesssizeof(T)
<=sizeof(void*)
andT
has been declared to be either aQ_MOVABLE_TYPE
or aQ_PRIMITIVE_TYPE
usingQ_DECLARE_TYPEINFO
.
They refer to this article by Marc Mutz.
So the official point of view has changed.