QList vs QVector revisited

Question

My question is basically when to choose QVector and when to choose QList as your Qt container. What I already know:

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

2. The same is written is this very popular Q&A: QVector vs QList. It also favors QList.

3. But: on recent Qt World Summit 2015 KDAB presented "Why QList is harmful", this is basically here:

QList considered harmful

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 1

Imagine, that we have DataType class.

QVector - array of objects, such as:

// QVector<DataType> internal structure
DataType* pArray = new DataType[100];

QList - array of pointers to objects, such as:

// QList<DataType> internal structure
DataType** pPointersArray = new DataType*[100];

Therefore, direct access by index will be faster for QVector:

{
// ...
cout << pArray[index]; //fast
cout << *pPointersArray[index]; //slow, need additional operation for dereferencing
// ...
}

But swaping will be faster for QList, if sizeof(DataType) > sizeof(DataType*):

{
// QVector swaping
DataType copy = pArray[index];
pArray[index] = pArray[index + 1];
pArray[index + 1] = copy; // copy object

// QList swaping
DataType* pCopy = pPointersArray [index];
pPointersArray[index] = pPointersArray [index + 1];
pPointersArray[index + 1] = pCopy; // copy pointer
// ...
}

So, if you need direct access without swaping operations between elements (such as sorting, for example), or sizeof(DataType) <= sizeof(DataType*), your better way is use QVector. In other case use QList.