Understand the Qt containers

Container classes are one of the cornerstones of object-oriented programming, invaluable tools that free us from having to permanently think about memory management.

Qt comes with its own set of container classes, closely modeled after those in the STL, but with subtle and not-so-subtle differences, some of them clever additions, others; not quite so. As a Qt programmer, it is important to understand when to use which Qt container class, and, if you have the option, when to use STL containers instead.

Qt containers and their STL counterparts

The following table summarises the main sequential and associative Qt containers and their STL counterparts. For the most part, we will ignore the string classes, even though technically, they are also containers.

Qt	STL
Sequential Containers
QVector	std::vector
—	std::deque
QList	—
QLinkedList	std::list
—	std::forward_list
Associative Containers
QMap	std::map
QMultiMap	std::multimap
—	std::set
—	std::multiset
QHash	std::unordered_map
QMultiHash	std::unordered_multimap
QSet	std::unordered_set
—	std::unordered_multiset

As you can see, there are no Qt containers corresponding to std::deque, std::forward_list and std::{multi,}set, and there is no STL container that is quite like QList. There are also two gotchas: QList isn’t at all like std::list, and QSet isn’t at all like std::set. For some reason, there’s also no QMultiSet.

Guideline: Remember that QList has nothing to do with std::list, and QSet has nothing to do with std::set.

General differences between Qt and STL containers

There are a handful of differences that affect all containers.

Duplicated API

First and foremost, the Qt containers have a duplicated “Qt-ish” and “STL-compatible” API. So, there’s append() and push_back(); count() and size(); and isEmpty() and empty(). Depending on the scope of your Qt usage, you should pick one of the two APIs, and stick to it. Immersive applications may use the Qt-ish API, while layered applications should go for the STL-compatible one, for consistency with STL containers used elsewhere in the project. If in doubt, go with the STL API — it won’t change come Qt 5.

Guideline: Be aware of the two Qt container APIs, Qt-ish and STL-compatible, and avoid mixing their use in the same project.

STL Features Lacking in Qt

The STL containers also sport a few features that might look esoteric at first glance:

• Most of them have rbegin()/rend(), which return reverse iterators:

  const std::vector<int> v = { 1, 2, 4, 8 };
  for ( auto it = v.rbegin(), end = v.rend() ; it != end ; ++it )
     std::cout << *it << std::endl; // prints 8 4 2 1
  

  In Qt, you have to use the normal iterators and decrement to get the same effect:

  const QVector<int> v = ...;
  auto it = v.end(), end = v.begin();
  while ( it != end ) {
      --it;
     std::cout << *it << std::endl;
  }
  

  or use the Java-style iterators (but see below):

  QVectorIterator it( v );
  it.toBack();
  while ( it.hasPrevious() )
      std::cout << it.previous() << std::endl;
  

• All STL containers also have range-insertion, range-construction and assignment, as well as range-erase, all but the last templated so that you can fill—say—a std::vector from a pair of iterators to—say—a std::set:

  const std::set<T> s = ...;
  std::vector<S> v( s.begin(), s.end() ) ; // 'T' needs to be convertible to 'S'
  

  This greatly removes the need to use the qCopy()/std::copy() algorithms.

  Qt containers only have range-erase.

• All STL containers have an Allocator template argument. While rather arcane, the allocator allows to place the elements of an STL container into—say—shared memory, or allocate them with a pool allocator.

  Qt containers cannot use special memory allocators, so their elements (and, by extension, they themselves) cannot be placed into shared memory.

• Last not least I should mention the availability of very good debug modes for virtually any STL implementation. These debug modes find bugs at runtime that without debug mode manifest themselves through crashes or undefined behaviour. Among those bugs found by virtually any STL debug mode are:
  • Advancing an iterator past its valid range.
  • Comparing iterators that don’t point into the same container.
  • Using invalidated iterators in any way except assigning to them.
  • Dereferencing an invalid or past-the-end iterator.

  See your compiler’s manual for how to enable the STL debug mode. You will thank yourself.

  Nothing of that sort exists for the Qt containers.

Guideline: Familiarise yourself with the STL containers and the additional features they offer.

Copy-On-Write

On the plus side, Qt containers are implicitly shared, so copies are shallow. In contrast, all STL containers except std::string are required to use deep copy. While this sounds like a waste of resources, the Jury is still out there about whether copy-on-write is that great an optimisation to begin with.

In any case, judicious use of the swap() member function (also available in Qt containers in Qt ≥ 4.7) and C++11 move semantics greatly removes the need to actually copy container contents:

Container c;
// populate 'c'
m_container = c; // wrong: copy
m_container.swap( c ); // correct: C++98 move by swapping
m_container = std::move( c ); // correct: C++11 move

Returning a collection from a function should already be a no-op with most compilers because of the return value optimisation.

BTW, here’s how to move an element into a container in C++98:

// the item to move-append:
Type item = ...;
// the container to move-append it to:
Container c = ...;
// make space in the container
// (assumes that a default-constructed Type is efficient to create)
c.resize( c.size() + 1 ); // or: c.push_back( Type() );
// then move 'item' into the new position using swap:
c.back().swap( item );

and in C++11:

c.push_back( std::move( item ) );

Guideline: Prefer member-swap over assignment wherever possible to express move semantics. Use C++11 rvalue move semantics if the class and the compiler support them.

That said, there’s one use-case where I’d recommend the Qt containers over the STL ones: Concurrent read/write access. By using COW, the Qt containers can minimise the time spent under mutex protection, e.g. with a transaction-based approach:

// global shared data:
QVector<Data> g_data;
QMutex g_mutex;
void reader() {
    QMutexLocker locker( &g_mutex );
    // make a (shallow) copy under mutex protection:
    const QVector<Data> copy = g_data;
    // can already unlock the mutex again:
    locker.unlock();
    // work on 'copy'
}
void writer() {
try_again:
    QMutexLocker locker( &g_mutex );
    // make a (shallow) copy under mutex protection:
    QVector<Data> copy = g_data;
    // remember the d-pointer of g_data (QVector lacks the usual data_ptr() member):
    const void * const g_data_data = reinterpret_cast<void*>(g_data);
    // can already unlock the mutex again:
    locker.unlock();
    // modify 'copy' (will detach, but _outside_ critical section!)
    // lock the mutex again in order to commit the result:
    locker.relock();
    // check that no-one else has modified g_data:
    // (only necessary if this isn't the only possible writer thread):
    if ( g_data_data == reinterpret_cast<void*>(g_data) )
        g_data.swap( copy ); // commit (member-swap requires Qt >= 4.8)
    else
        goto try_again;      // oops, someone else was faster, do the whole thing again
}

This is not possible with the STL containers.

Guideline: Prefer the Qt containers over the STL ones if you can make good use of the Copy-On-Write feature they offer.

One caveat with all COW implementations is hidden detaches. A COW container that is going to be modified (written to) needs to ensure that it has a unique copy of the data, so that other container instances with whom it happens to share the data will not be affected by the write. If the data the container references is shared with other containers at the time of the write, the container performs a deep copy to obtain an unshared copy of the data. It is, of course, imperative that the number of such deep copies be kept to the strict minimum required for satisfying COW semantics.

There are, however, operations where detecting actual writes is hard. Take, for example, the indexing operator operator[]( int ). In all containers that support indexing, there are two overloads of the indexing operator:

T & operator[]( int idx ); // mutable
const T & operator[]( int idx ) const; // const

The first overload can be used to write to the container:

c[1] = T();

or, it can be used where the second one could be used, too: for read access:

T t = c[1];

In the first case, the container would have to detach, in the second, it should not. Yet, operator[]( int ) hands out a reference to an element, and for the container, writes through the reference are indistinguishable from reads. It must assume the worst and pre-emptively detach. Alternatively, it can return a user-defined types rather than a naked reference, and decide on detaching only when an actual write occurs. The interested reader may skim the definition of QCharRef/QString::operator[]( int ) or QByteRef/QByteArray::operator[]( int ), which implement this scheme. These two containers are the only ones which employ this technique in Qt, though.

And there’s another problem: Iterators. Just as the mutable (better: potentially-mutable) operator[] needs to pre-emptively detach, so must begin()/end(), unless the iterator returned is sufficiently intelligent to distinguish writes from reads. A look at the Qt sources confirms that none are.

What does this mean for us, users of the containers? First, since the STL containers (except for std::string) are forbidden to implement COW semantics, the problem doesn’t exist there. For Qt containers, however, you should pay meticulous attention not to perform read-only iterations using mutable iterators. That’s easier said than done, however, since the (preliminarily detaching) potentially-mutable begin()/end() functions are called in preference over the const ones:

QString str = ...;
const QString cstr = ...;
for ( QString::const_iterator it = str.begin(), end = str.end() ; it != end ; ++it ) // detaches
    ...;
for ( QString::const_iterator it = cstr.begin(), end = cstr.end() ; it != end ; ++it ) // doesn't
    ...;

While we use const_iterator in both loops, the first one is implicitly converted from the iterator that QString::begin() (non-const) returns. By that time, the detach has already happened.

A solution that works with all containers is to alias the container with a constant reference, and use the reference to iterate over:

const QString & crstr = str;
for ( QString::const_iterator it = crstr.begin(), end = crstr.end() ; it != end ; ++it ) // no detach
    ...;

Alternatively, all Qt containers come with constBegin()/constEnd() that always return const_iterator, even when called on a mutable instance:

for ( QString::const_iterator it = str.constBegin(), end = str.constEnd() ; it != end ; ++it ) // no detach
    ...;

While much more important for the Qt containers (to prevent accidental detaching), the STL containers, in C++11, have gained their own version of constBegin()/constEnd(), called cbegin()/cend(). We can expect the Qt APIs to catch up soon.

Guideline: Always use constBegin()/constEnd() (cbegin()/cend()) when assigning the result to a const_iterator.

You can inhibit the implicit conversion from iterator to const_iterator by defining QT_STRICT_ITERATORS.

Iterators

Iterators into Qt associative containers also differ from their STL counterparts in that they return the value rather than a pair of key and value. This is a nice change from the rather ugly it->second of the STL’s associative containers. The STL interface comes across as ivory-tower material instead.

This means, however, that you can’t use—say—a QMap as a drop-in replacement for a std::map and vice versa.

In addition to the (mostly) STL-compatible iterators, Qt containers also sport so-called “Java-style” iterators. You can detect them by their name: QContainerIterator instead of QContainer::const_iterator and QMutableContainerIterator instead of QContainer::iterator.

The fundamental difference between the STL- and Java-style iterators is that STL iterators point onto elements while Java-style iterators conceptually point between elements, the idea being that such iterators can never (conceptually) become invalid: If elements are added or removed around them, they still point between elements, and iteration can proceed normally.

But there are a few drawbacks, to wit:

• The Java-style iterators are implemented on top of the STL-compatible ones, so by definition they cannot be more efficient (and since they internally work on a pair of STL-iterators, it takes a very powerful compiler indeed to keep them up to the STL-iterator efficiency).
• For the same reason, they don’t really point between elements. A Java-style iterator is invalidated in the same way an STL-compatible one is if the container is modified outside the iterator’s API, e.g. by modifying the container directly, or through a second Java-style iterator. In other words: the Java-style iterators do not monitor the container for changes in any other way than an STL-compatible iterator does (ie. not at all); there is no change notification protocol that could provide this. So if you are considering using Java-style iterators as a stable alternative to STL-compatible ones for remembering state, you will be disappointed.
• While the semantics of in-between-element iterators are conceptually pleasing, the API of mutable iterators violates this principle by providing functions such as value(), setValue(), and remove(). As a consequence, there is confusion on which elements these functions act, in particular when it is unknown whether next() or previous() has been called before. While the three functions mentioned are at least consistent in that they always act on the “last returned element”, the insert() function ignores the last returned element, and positions the iterator after the inserted element — in container order (as opposed to iteration order). That means that when iterating backwards (with toBack() and previous()) inserted elements will be iterated over, whereas when iterating forwards (with toFront() and next()), they will not.

  This isn’t something we should blame the Java-style iterator for, though. Modifying the container while iterating over it is complicated no matter which iterator concept is being used, and is best hidden in algorithms such as std::remove().

  Guideline: Avoid modifying a container (remove/insert elements) while iterating. If you have to, use an STL algorithm, such as one of the std::remove() family.

Guideline: Prefer the STL-compatible iterators over the Java-style ones.
Guideline: If you do use the Java-style iterators, avoid using the mutating ones.

Q_FOREACH

Closely related to the concept of iterators is Q_FOREACH (also available as foreach if you compile without QT_NO_KETYWORDS defined, which you shouldn’t), a macro that eases iteration over containers by hiding all the iterators involved. An example for a Q_FOREACH loop might look as follows:

const QStringList list = ...;
Q_FOREACH( const QString & item, list )
    qDebug() << item;

When using Q_FOREACH, you need to keep a few things in mind:

• Q_FOREACH, being a preprocessor macro, does not play well with elements of class template type with more than one template argument:

  const QVector<QPair<QString,int>> list = ...;
  Q_FOREACH( const QPair<QString,int> & item, list ) // error: Q_FOREACH requires 2 arguments, 3 given
      qDebug() << item;
  

  This is because the C/C++ preprocessor doesn’t recognize angle brackets (<>) as a bracketing construct and parses the comma in QPair as separating Q_FOREACH arguments. In this case, you need to use a typedef:

  const QVector<QPair<QString,int>> list = ...;
  typedef QPair<QString,int> Item;
  Q_FOREACH( const Item & item, list ) // ok
      qDebug() << item;
  

• As you might have noticed, the examples have used const references in the first argument to Q_FOREACH, ie. instead of Q_FOREACH( QString item, list ) we have used Q_FOREACH( const QString & item, list ). This pattern has two effects: First, by using a reference, we avoid a copy being made of the element. Second, by using a const reference, we avoid stupid mistakes such as assigning to the loop’s control variable (expecting the element in the container to be updated alongside it). Of course, for types that you would normally pass by value instead of const reference (built-in types, mostly), the loop would consequently read:

  const QVector<int> list = ...;
  Q_FOREACH( const int item, list )
      qDebug() << item;
  

• So now we know how to write a constant loop with Q_FOREACH, you might be tempted to try writing a mutable loop like this:

  QStringList list = ...;
  Q_FOREACH( QString & item, list )
      item += QLatin1String( ".txt" );
  

  (note the non-const reference used to declare item). This, however, does not work, since internally, Q_FOREACH always uses const_iterators. If you need this feature, turn to BOOST_FOREACH, which also works with the Qt containers (at least those that are STL compatible).

• TODO: copies

Guideline: Prefer to use const references as the first argument of Q_FOREACH, unless the element type is customarily passed by value.
Guideline: Familiarise yourself with BOOST_FOREACH, and the additional features it offers.

QTypeInfo

We also need to talk about a system for type classification that the Qt containers use for optimisation, and without which you will not get optimal speed and/or memory use for your own types (and not for a long list of other, including Qt, types, either): QTypeInfo.

QTypeInfo is a traits class that Qt uses to enable certain optimisations, mostly in the Qt containers.

The public interface to specialise QTypeInfo for your own types is Q_DECLARE_TYPEINFO( Type, Flags ), which declares Type to be of kind Flags.

Two of the optimisations made possible by QTypeInfo are to leave the memory uninitialised for POD types (Flags = Q_PRIMITIVE_TYPE), and using std::memcpy() instead of the copy constructor to move instances around (Flags = Q_MOVABLE_TYPE), and, as we shall see, it’s the latter of the two that makes a real difference in Qt containers, but especially in QList.

So, when should you declare your types as either Q_PRIMITIVE_TYPE or Q_MOVABLE_TYPE? (the third option, Q_COMPLEX_TYPE is the default, so types would usually not be explicitly declared as complex, unless you want to prevent users from declaring them as something else)

• Q_PRIMITIVE_TYPE is the correct one for all PODs (in the C++03 sense). Oversimplified, PODs are all those types that would also compile as C types: built-in types, (C-)arrays, and structs thereof.
• Q_MOVABLE_TYPE is the correct one for almost all other types. A movable type is one that can be relocated in memory without its contents changing (I’m using EASTL’s notion of relocation here to separate the concept from C++11’s move semantics, which is a different thing altogether). This is true for the vast majority of value-like types. An example of a type for which this is not true is a pimpl’ed class with a back-link: If the public class is moved, the q-pointer (back-link) will still point to the old class (thanks to David Faure for this example). The consolation is that such classes are usually not used as container elements anyway (only pointers to them, but those are of course of Q_PRIMITIVE_TYPE).

In the next section, we will see which kind of optimisations the various containers perform based on this classification scheme.

Guideline: Declare your enums and QFlags as Q_PRIMITIVE_TYPE if there’s a chance they will be held in Qt containers.
Guideline: Declare your value-types Q_MOVABLE_TYPE if there’s a chance they will be held in Qt containers.
Guideline: Don’t change the classification of a type if you need to maintain binary compatibility.

In case you want to make use of this information for your own collections, you can use the QTypeInfo trait class yourself. Unfortunately, the API of QTypeInfo has not much in common with the flags that are used in Q_DECLARE_TYPEINFO, so here’s the 10,000ft view:

• QTypeInfo<T>::isComplex is a compile-time constant that evaluates to true if you need to run the constructors and destructors of type T, and to false if not. This is true for both Q_MOVABLE_TYPE and Q_COMPLEX_TYPE.
• QTypeInfo<T>::isStatic is a compile-time constant that evaluates to true if you need to use the copy constructor to relocate objects of type T, and to false if you can use memcpy() instead. This is true for Q_COMPLEX_TYPE.
• QTypeInfo<T>::isLarge is equivalent to sizeof(T) > sizeof(void*).

There are some more flags in there, but these are the most important ones.

Looking beyond Qt, C++11 is catching up with the type_traits library and introduces is_trivial and is_trivially_copyably ([class.6], [meta.unary.prop]). Here, is_trivial should roughly correspond to Q_PRIMITIVE_TYPE, but there’s no (standard) type trait to express Q_MOVABLE_TYPE. Even though EASTL introduces has_trivial_relocate, C++11 only has is_trivially_copyable, which is, however, a much stronger property than Q_MOVABLE_TYPE: It indicates that such classes can be copied using memcpy(), while Q_MOVABLE_TYPE/has_trivial_relocate only says they can be relocated in memory that way. In particular, all ref-counted classes are trivially relocatable, but most certainly not trivially copyable.

It can only be hoped that a TR2 will eventually standardise an is_trivially_relocatable trait, too.

Size Types

The STL containers consistently use unsigned integer types (size_t) for indexes and sizes, whereas the Qt containers consistently use signed integers (int). This means that when you switch from Qt to STL containers, you will often need to change variable signedness to prevent compiler errors. Careful use of the nested Container::size_type can make your code more robust against this.

Associative Container Insertions

A rather nasty difference exists between the associative STL and Qt containers: The STL Unique Associative Container concept requires all insert() overloads to insert if and only if the key is not already present in the container (of course, map[key] = value will always store value even if key was already present in map). Qt associative containers, however, do the opposite and replace the old value on insert() (except when using QMulti{Hash,Map}).

Personally, I find the STL behaviour more consistent (insert() never changes an existing key’s value, neither in map nor in multimap), but regardless of what you personally like better, you should be aware of the difference.

Error Handling

The STL rule of thumb is that the index operators ([]) are unchecked, while the at() member functions throw std::out_of_range. You can therefore choose which behaviour suits you best, and only pay the price of the check-on-access if you think it’s worth it. In Qt containers, on the other hand, both the index operator and the at() function simply assert an out-of-range situation.

Container-Specific Discussion

In this section, I will talk about each of the containers in turn, and point out gotchas and incompatibilities between the Qt and STL variants.

In writing this, I tried to not repeat all the advice on data structures in general and STL containers in particular that is contained in Scott Meyer’s Effective STL, and The Good Book, and that is largely applicable to the Qt variants of the containers, too. I can’t say that succeeded in that, though 🙂

QVector

So let’s break the spell right away: The default container should be vector (std or Q).

While programmers trained in the STL won’t think about using anything else than a std::vector as a sequential container (until the profiler tells them to), and many who have read about the trick will even replace some uses of associative containers with (sorted) vectors, people who have (only) received Qt training reach out to QList by default.

If you don’t yet understand why vectors should be preferred, please read The Good Book, or Effective STL, or, for that matter, Ulrich Drepper’s excellent paper What Every Programmer Should Know About Memory. However, while Amazon gets the shipment ready, do continue reading this article and start following the

Guideline: Prefer vector (std or Q) over QList.

QVector is perhaps the Qt container closest akin to its STL counterpart. That it nonetheless performs worse than std::vector on many platforms is due to the fact that its internal structure is more complex (another indirection through the d-pointer, e.g.). You can see this by comparing the code generated by GCC 4.3.2 (x86-64) with -O2 for iteration over QVector (Qt 4.6.3) and its own std::vector:

QVector	std::vector
void iterateQt( const QVector<int> & v ) { for ( QVector<int>::const_iterator it = v.begin(), end = v.end() ; it != end ; ++it ) doSomething( *it ); }	void iterateSTL( const std::vector<int> & v ) { for ( std::vector<int>::const_iterator it = v.begin(), end = v.end() ; it != end ; ++it ) doSomething( *it ); }
_Z9iterateQtRK7QVectorIiE: .LFB1803: pushq %rbp .LCFI3: pushq %rbx .LCFI4: subq $8, %rsp .LCFI5: movq (%rdi), %rax movslq 8(%rax),%rdx leaq 16(%rax), %rbx leaq 16(%rax,%rdx,4), %rbp cmpq %rbp, %rbx je .L10 .p2align 4,,10 .p2align 3 .L11: movl (%rbx), %edi addq $4, %rbx call _Z11doSomethingi cmpq %rbx, %rbp jne .L11 .L10: addq $8, %rsp popq %rbx popq %rbp ret	_Z10iterateSTLRKSt6vectorIiSaIiEE: .LFB1804: pushq %rbp .LCFI0: pushq %rbx .LCFI1: subq $8, %rsp .LCFI2: movq (%rdi), %rax movq 8(%rdi), %rbp cmpq %rbp, %rax je .L4 movq %rax, %rbx .p2align 4,,10 .p2align 3 .L3: movl (%rbx), %edi addq $4, %rbx call _Z11doSomethingi cmpq %rbx, %rbp jne .L3 .L4: addq $8, %rsp popq %rbx popq %rbp ret

The actual loop (.L11/.L3) is identical, showing that the compiler can see through the iterator abstractions equally well in both cases. The difference, however, is in filling %rbx (it) and %rbp (end) before the loop (.LCFI5/.LCFI2): The code for QVector is decidedly more complex (more commands, more complex addressing modes, calculations depend on previous results), and will execute slower.

This means that the setup overhead for iterations over empty and small collections will be higher for QVector than for std::vector. QVector iteration also produces slightly more code than std::vector iteration.

In any other class, this would not be worth talking about. And maybe it isn’t for your application. But for bread-and-butter classes such as vectors, the best performance is just good enough.

That said, the results of course depend on the actual STL implementation. Unless you use crippled STLs like the one that ships with SunCC (not STLport, the default one), though, you will find that you can trust std::vector to outperform QVector, if not by much.

One thing that QVector has going for it is its growth optimisation. When the element type is Q_MOVABLE_TYPE or Q_PRIMITIVE_TYPE, QVector will use realloc() to grow the capacity. The STL containers also do this, however due to lack of a portable type classification scheme, they only do so for built-in types, and/or with non-portable declarations (see the section on QTypeInfo above).

You can remove the influence of this by using reserve() liberally. This is not only an advantage for the STL vector, it also speeds up and saves memory in the Qt vector.

It should also be mentioned that due to the way the internal function QVector::realloc() is implemented, QVector requires that the element type provide a default constructor even for a simple push_back(). In contrast, std::vector does not require element types to be DefaultConstructible, unless you call a std::vector function that explicitly requires this, e.g. std::vector(int). Personally, I see that as big drawback of QVector, because it forces the element type to have a (potentially artificial) “empty” state.

QList

Woe unto you, scribes and Pharisees, hypocrites! for ye are like unto whited sepulchres, which indeed appear beautiful outward, but are within full of dead [men’s] bones, and of all uncleanness.
— Matthew 23:27, 1769 Oxford King James Bible ‘Authorized Version’

QList is the whited sepulchre of Qt containers.

As mentioned above, QList has nothing to do with std::list. It is implemented as a so-called array list, effectively a contiguous chunk of void*s, with a bit of space before and after, to allow both prepending (very rare) and appending (very common). The void* slots contain pointers to the individual elements (which are copy-constructed into dynamic memory, ie. with new), unless the element type is movable, i.e. declared to be Q_MOVABLE_TYPE, and small enough, i.e. not larger than a void*, in which case the element is placed directly into the void* slot.

Let’s examine the pros and cons of the design:

On the positive side, QList is a real memory saver when we talk about the amount of code generated. That is because QList is but a thin wrapper around an internal class that maintains the memory for void*s. This leads to more compact code, because all the memory management code is shared between QLists of different types.

QList also allows reasonably fast insertions in the middle and reasonably efficient growing of the container (only the pointers need to be moved, not the data itself, so QList can always use realloc() to grow itself). That said, this efficiency will not be much higher than can be expected from a QVector<void*>, and vectors are not in general known for fast insertions in the middle.

On the negative side, QList is a real memory waster when it comes to holding most data types.

There are two effects at play here:

First, if the element type is movable and small enough (see above), QList wastes memory when the element type’s size is less than sizeof(void*): sizeof(void*)-sizeof(T), to be precise. That is because each element requires at least sizeof(void*) storage. In other words: a QList<char> uses 4×/8× (32/64-bit platforms) the memory a QVector<char> would use!

Second, if the element type is either not movable or too large (sizeof(T) > sizeof(void*)), it is allocated on the heap. So per element, you pay for the heap allocation overhead (depends on the allocator, between zero and a dozen or two bytes, usually), plus the 4/8 bytes it takes to hold the pointer.

Only if the element type is movable and of size sizeof(void*), is QList a good container. This happens to be the case for at least the most important of the implicitly shared Qt types (QString, QByteArray, but also QPen, QBrush, etc), with some notable exceptions. Here’s a list of types that, in Qt 4.6.3, are documented to be implicitly shared, and whether or not they make good elements for QList:

No: Too Large	No: Not Movable	OK
QBitmap, QFont, QGradient, QImage, QPalette, QPicture, QPixmap, QSqlField, QTextBoundaryFinder, QTextFormat, QVariant(!)	QContiguousCache, QCursor, QDir, QFontInfo, QFontMetrics, QFontMetricsF, QGLColormap, QHash, QLinkedList, QList, QMap, QMultiHash, QMultiMap, QPainterPath, QPolygon, QPolygonF, QQueue, QRegion, QSet, QSqlQuery, QSqlRecord, QStack, QStringList, QTextCursor, QTextDocumentFragment, QVector, QX11Info	QBitArray, QBrush, QByteArray, QFileInfo, QIcon, QKeySequence, QLocale, QPen, QRegExp, QString, QUrl

QCache is lacking the required copy constructor, so it can not be used as an element in a QList.

All the containers themselves would be small enough to fit into a QList slot, but QTypeInfo has not been partially specialised for them, so they’re not marked as movable, even though most probably could.

You can Q_DECLARE_TYPEINFO your own instantiations of these classes, like this:

Q_DECLARE_TYPEINFO( QList<MyType>, Q_MOVABLE_TYPE );

and they will be efficient when put into QList.

The problem, however, is that if you forgot the Q_DECLARE_TYPEINFO so far, you cannot add it now, at least not in a binary-compatible way, as declaring a type movable changes the memory layout of QLists of that type. This is probably the reason why the Trolls have not yet fixed the containers to be marked movable.

Some other types that are too large for a QList slot are QSharedPointer<T>, most QPairs, and QModelIndex(!), but not QPersistentModelIndex.

Here is an overview over the memory efficiency of some primitive types. They’re all movable, so potentially efficient as a QList element. In the table, “Size” is the size of the element type as reported by the sizeof operator, “Mem/Elem” is the memory (in bytes) used per element, for 32/64-bit platforms, and “Overhead” is the memory overhead of storing these types in a QList instead of a QVector, ignoring O(1) memory used by each container.

Type	Size	Mem/Elem	Overhead
bool/char	1	4/8	300%/700%
qint32/float	4	4/8	0%/100%
qint64/double	8	16+/8	100%+/0%

What is particularly troublesome is how a type can be efficient on a 32-bit platform and inefficient on a 64-bit platform (e.g. float), and vice versa (e.g. double).

This directly leads to the following, more fine-grained

Guideline: Avoid QList<T> where T is not declared as either Q_MOVABLE_TYPE or Q_PRIMITIVE_TYPE or where sizeof(T) != sizeof(void*) (remember to check both 32 and 64-bit platforms).

So, QList is not a good default container. But are there situations where QList is preferable over QVector? Sadly, the answer is no. It would be best if, come Qt 5, the Trolls just went and replaced all occurrences of QList with QVector. The few benchmarks in which QList outperforms QVector are either irrelevant in practice, or should be fixable by optimising QVector better.

That said, for the time being, you should think twice before writing QVector<QString>, even though it might perform slightly better. That is because QList is customarily used for collections of QStrings in Qt, and you should avoid using a vector where the Qt API uses QList, at least for the cases where the QList is actually efficient. Personally, I try to replace the inefficient QList<QModelIndex> with QVector<QModelIndex> wherever I can.

Guideline: Avoid using vectors of types for which Qt APIs customarily use QList, and for which QList is not inefficient.

To Be Continued…

The Data

In this section, I’ll discuss benchmarks and other data that underlie the guidelines in this article.

General Remarks

You can find the test-harness at http://www.kdab.com/~marc/effective-qt/containers/testharness.tar.gz. Each test has its own subdirectory. This tar-ball will be updated whenever I publish new tests.

The benchmarks are usually run

• over all containers (Qt and STL) for which they makes sense (currently, only sequential containers are considered)
• if the container has a reserve() method, runs the test with and without first calling it
• over element counts from one to roughly 4k and
• over a variety of element types, some of which require a word or two of explaination:

Type	Description
Enum	An enum, not marked Q_PRIMITIVE_TYPE
FastEnum	The same, but marked as Q_PRIMITIVE_TYPE
Flag	A QFlags<Enum>, not marked Q_PRIMITIVE_TYPE
FastFlag	The same, but marked as Q_PRIMITIVE_TYPE
Payload<N>	A simple struct { char a[N]; };, not marked.
PrimitivePayload<N>	The same, but marked as Q_PRIMITIVE_TYPE
MovablePayload<N>	The same, but marked as Q_MOVABLE_TYPE

I’ve run all tests on 64-bit Linux with Qt 4.7.3 and GCC 4.3, with CONFIG += release (-O2 in GCC terms).

Memory Usage

Test Harness	http://www.kdab.com/~marc/effective-qt/containers/testharness.tar.gz, massif/
Results	full range, low-size zoom

This test benchmarks the memory performance of the various containers by running them under Valgrind’s Massif tool. The numbers reported are the “max. total mem”, as reported by ms_print. Massif is run with the default parameters, in particular, the alignment (and therefore; minimum size) of heap allocations is left at the default of eight.

The test code is simple:

Container<Element> c;
c.reserve( N ); // if available and not suppressed
std::fill_n( std::back_inserter( c ), n, Element() );

Noteworthy findings:

• std::deque has a high cost for low element count, because (this implementation) allocates fixed 1k pages to hold the elements. It is optimised for efficient (O(1)) continuous push_front()/pop_back() (or push_back()/pop_front()), and this is the price you pay.
• QLinkedList/std::list consistently perform worst. They’re optimised for insertions in the middle, and this is the price you pay. (This implementation of) std::list appears to have a lower memory footprint than QLinkedList. The reason for that is unknown.
• QVector/std::vector consistently perform best, if you call reserve(). If you don’t, they may use up to twice the memory necessary (but at least in the std::vector case, it is all but guaranteed that the surplus memory is never touched).
• QList consistently performs between the “real” lists and the “real” vectors. At best, it performs exactly as QVector.

CPU Usage

Test Harness	http://www.kdab.com/~marc/effective-qt/containers/testharness.tar.gz, cpu/

This test benchmarks the (CPU) performance of the various containers by running them in QTestLib‘s QBENCHMARK macro. There are actually three separate tests: appending, iteration, and queuing (=push_back()/pop_front()). But since the test harness is so similar, they’re crammed into one binary.

I didn’t check prepending, because the results should be comparable to appending, at least for those containers which efficiently support them. I also didn’t test insertions in the middle, since they’re rather rare. That said, there are of course lots of other tests one could run (e.g. sorting), and I invite you, dear reader, to implement some of them in the test harness and contribute them back.

Appending

Results	tick-counters: 16-16k elements (Qt Types), 1-16 elements (Qt Types)
	(wallclock time) TBD
	(callgrind) TBD

The goal of the test is to get a feeling for the relative performance of the different containers when it comes to appending to them. Appending always stands at the beginning of a container’s life, and for some (temporary) containers, it should be the time that dominates the total time spent in them.

The test code:

std::vector<Element> v;
v.reserve( N );
std::fill_n( std::back_inserter( v ), N,
             Generator<Element>() );
QBENCHMARK {
    Container<Element> c;
    c.reserve( N ); // if available and not suppressed
    for ( auto it = v.cbegin(), end = v.cend() ; it != end ; ++it )
        c.push_back( *it );
}

It first creates a std::vector with the content. This is done to remove the influence of the generator on the test results. The actual test, then, is to copy the contents of the vector into the container under test. We don’t use std::copy here to remove any optimisations that may have been done by the STL vendor (such as calling reserve() if we wanted it suppressed, or using memcpy().

Noteworthy findings:

• TBD

Iteration (Cheap)

Results	(tick-counters) TBD
	(wallclock time) TBD
	(callgrind) TBD

The goal of the test is to get a feeling for the relative performance of the different containers when it comes to iterating over them. Of course, iteration in reality is dominated by the work performed on each element, so a crucial aspect of this benchmark is selecting just which work to perform. The test harness supports running a std::transform-like loop with arbitrary per-element work, expressed as function objects (Op in the code below). This test has been run with Cheap, which for arithmetic types (boost::is_arithmetic<T>) is x -> x * 2 and for all other types x -> x (ie. the identity transformation). Like in the Append test above, I have opted to use a hand-rolled loop, so as to remove the influence of std::container/std::algorithm effects.

The test code:

Container<Element> c;
std::fill_n( std::back_inserter( v ), N,
             Generator<Element>() );
Op op;
QBENCHMARK {
    for ( auto it = c.begin(), end = c.end() ; it != end ; ++it )
        *it = op( *it );
}

Noteworthy findings:

• TBD