Qvector VS Qlist

QVector vs QList

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.

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).

What is the difference between QByteArray and QListunsigned char or QVectorunsigned char?

QByteArray is a usefull wrapper around char*. Suitable for streaming with QDataStream, string operations and other data management.
From the docs you also can find that:

Behind the scenes, it always ensures that the data is followed by a
'\0' terminator, and uses implicit sharing (copy-on-write) to reduce
memory usage and avoid needless copying of data.

QList, at first is not linear(subsequent) in memory (you should use QVector), and have no such usefull API

Why use QVector(Qt) instead of std::vector

This article loooks good. It compares Qt Template Library with Standard Template Library:

QTL vs STL

Hope, you'll find it interesting seeing all the differences listed there in the article.

EDIT:

Here is what I find interesting:

My opinion is that the biggest
advantage of the QTL is that it has
the same implementation (including
binary compatibility) on all OSes
supported by Qt. Some STL
implementations might be below par
when it comes to performance or they
might be missing functionality. Some
platforms don’t even have an STL! On
the other hand, the STL is more
customizable and is available in its
entirety in header files… Like I said,
there is no clear winner.

Like he said, no clear winner. But still reading the article makes lots of things clear. Its better to know the difference than going for one, without knowing the other.

QList, QVector or std::vector multi-threaded usage

Your solution is not thread-safe without a locking mechanism.

You can use tbb::concurrent_vector or Concurrency::concurrent_vector for multiple insertion and access simultaneously. No extra locking required. It is unsafe to erase elements from those vectors, but you are ok with it I guess.

How does QListQString, QListQByteArray in Qt6 retrieve data?

QByteArray and QString themselves won't contain any data, just a pointer to a dynamically allocated array (try running sizeof(QByteArray) and sizeof(QString), you'll get a small constant size for both).

All instances of a the same class in C++ have the same size so in an array of objects accessing an index is just a case of seeking to element_size * index bytes from the beginning of the array.

Strange (huge) performance difference between std::vector, QList and std::list

In contrast to what i mentionend in the question (shame on me), i had another check for the size of the std::list in the for-loop to determine whether to use insert() or push_back() on the list.
Since this function doesn't have the time complexity of O(1) but O(n) this slowed down the whole insertion a lot. Thanks to Leeor for pointing this out.

After moving this check out of the for-loop the std::list performed as expetected and even faster than the QList.

QList of Qvectors clear

Not only it is useless, but is can be "harmful".

It is useless because QList<T>::clear() will destroy every T it owns effectively calling ~T(). In your case that means that you end up calling ~QVector<QPointF>() for every vector in the QList. And then ~QVector<QPointF>() will call ~QPointF() for every point.

It can be harmful performance wise because QList and QVector use Copy-on-Write. That means that when you copy a list you do not copy the internal data, but a copy will happen as soon as you perform an action that will modify one of the list.

So if m_data shares its internal data with another QList, changing any of its element (eg. by calling QVector::clear() on one of them) will trigger a hard copy of the QList internal data. And this copy is completely useless as you discard it just after by calling m_data.clear().

Also worth noting that:

foreach (QVector<QPointF> row, m_data)
    row.clear();

Does not change m_data. You clear row which is a local variable. And even if you en up writing:

foreach (QVector<QPointF> &row, m_data)
        row.clear();

It will have no effect as, quoting Qt doc:

Since foreach creates a copy of the container, using a non-const
reference for the variable does not allow you to modify the original
container. It only affects the copy, which is probably not what you
want.