QList vs QVector revisited
My question is basically when to choose QVector and when to choose QList as your Qt container. What I already know:
- Qt docs: QList class
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.
The same is written is this very popular Q&A: QVector vs QList. It also favors QList.
But: on recent Qt World Summit 2015 KDAB presented "Why QList is harmful", this is basically here:
Don't use QList, use Q_DECLARE_TYPEINFO
As far as I understand the idea is that QList for almost all types is inefficient when allocating new elements in heap. Each time you are adding new element, it calls new (once per element) and this is inefficient compared to QVector.
This is why now I am trying to understand: is it QVector which we should choose as default container?
Answer
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
QVectorwith 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).