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

31 Responses to Understand the Qt containers

  1. Pingback: Sneak Preview: QList considered harmful « -Wmarc

  2. Meko says:

    Your blog is titled “Understand the Qt Containers” and everyone of your guidelines says “Prefer std::* over Q*”. Is there any case where you recommend a Qt container over an stl one?

    • marcmutz says:

      No. I have yet to find a reason to prefer Qt containers over the STL ones, if you have the choice.
      But I think that upon closer reading of the article, you will find tons of guidelines that don’t match “Prefer std::* over Q*” for when you don’t have a choice (e.g., when interfacing with Qt API, or if the application uses Qt in the immersive way).

      But your comment reminds me that, indeed, I haven’t written about when to actually prefer Qt containers (though there’s only one case I’m aware of: QList<Q*>), so I’ll add something along these lines to the text.

      Thanks.

  3. Sasha says:

    A very thorough explanations of Qt containers. I prefer to be as “standard complaint” as possible and avoid using framework specific containers.

  4. For all iterators that are bidirectional or random access (which I think is every QT’s STL style iterators), reverse iterators can be constructed using std::reverse_iterator. Which is a nice trick if you need to go through a QT container in reverse.

    • marcmutz says:

      Yes, it’s a nice trick, if a rather verbose one :)

      There’s also a technical problem with std::reverse_iterator: it changed significantly during standardisation — compare C++03 and SGI STL. IIRC, the standard Solaris STL (left in a pre-standard state due to binary compatibility concerns) still has the old definition, causing me headache in a project where Solaris and Windows were the main target platforms.

      That was only a problem when defining reverse iterators, not when using them. So I stand by my criticism that the Qt bidirectional containers do not provide rbegin()/rend() and reverse_iterator/const_reverse_iterator typedefs themselves, leaving container users to fight with incompatible APIs or hard-to-read loops.

  5. Pingback: Understand the Qt Containers: The Data « -Wmarc

  6. The User says:

    Aren’t deque and QList kinda similar, deque uses such blocks, too, I think, but the implementation is more generic.

    • marcmutz says:

      That’s what I thought for a long time, until I actually looked at the QList implementation. Hence, this article :)

      A QList is almost exactly like a QVector<void*>, with the (important) optimisation that if the element type is movable and fits into the void* slot, it is placed there directly instead of just a pointer to it.

      A std::deque, OTOH, is like a vector of fixed-size (e.g. 1k) vectors. If by appending/prepending the last/first fixed-size vector gets full, a new one is appended/prepended to vector of vectors, and the new fixed-size vector used to place the element in. If by popping from the front/back the first/last fixed-size vector gets empty, it’s removed from the vector of vectors.

      So they’re not at all similar, after all.

  7. Christoph says:

    Internally in Qt, the most prominent use of QList is for QObject storing its list of children. Given your deep understanding of containers, which of them would you have been chosing for this use case?

    • marcmutz says:

      Both when you can and can’t use reserve() (and reserve() is unlikely here), QVector outperforms QList.

      I have added QObject* to the test result (thanks, that one was indeed missing) and updated the append results.

      Quoting myself:

      [...] 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.

  8. Giuseppe D'Angelo says:

    - The QTypeInfo::isStatic explaination is somehow the opposite (?) — it’s a compile-time constant that is “true” for types which *cannot* be moved in memory, i.e. the COMPLEX ones, and “false” for both MOVABLE and PRIMITIVE types. In short: isStatic => cannot be moved (i.e. COMPLEX); isComplex => need to run ctors/dtor when creating/copying/destroying.

    – In your opinion, why does QList allocate pointers to the objects when T is a complex type _even if it’s not large_? To put it the other way: why does it not store the objects directly in the backing array, like it would do if the type was movable or primitive?

    Of course, the general idea of allocating complex objects that way is to avoid the cost of calling ctors/dtors when the array is reallocated (it becomes just a matter of copying the pointers, i.e. memcpy()); but, on the other hand, if someone forgets a Q_DECLARE_TYPEINFO for a type which is not large and could be movable (f.i. the containers themselves, as you pointed out, or pretty much any implicitly shared class…) then for Qt it’s a complex type, thus it get allocated that way — and worse, the macro cannot be added any more because it would break BC!

    Really great article. Kudos, and keep up the good work!

    • marcmutz says:

      Regarding QTypeInfo::isStatic: You are absolutely correct. Good catch. I’ve fixed the article.

      Regarding QList copy-allocating types that are complex (or, more generally, “static”, in the QTypeInfo sense) on the heap even if they’re not “large”:

      QList‘s memory management code is factored into a non-template class, QListData, which manages the void* array for all QList instantiations. This class, in realloc(), always uses std::realloc(), which means that the actual contents of the array must always be of a movable type. If a type is not movable, it isn’t put into the void* slots, even if, by size, it would fit.

      Restricting the container to movable types is the only way one can factor all of the memory management code out of all the class template instantiations (which is useful, since it reduces code bloat). That isn’t the main mistake in the QList design. The primary problem is that you can instantiate QLists over types that are not movable in the first place, and that, to allow this safely, QList implements a very inefficient fall-back instead of simply failing compilation.

      I should also mention that QList implements a so-called “array-list”, which in itself is a rather modern and efficient container if all your types are references, as is the case in languages such as Java. But C++ isn’t Java, and there’s a reason why there’s no std::arraylist: array lists in C++ are a poor and rather special-purpose containers, simply because types in C++ vary so much.

  9. David Faure says:

    As an example of a class that is not movable: any value class with a d pointer _and_ and a q pointer pointing back to the public class, right? The value of “q” will change if the class is moved.

    This makes “movable or not” quite dependent on the implementation indeed.

  10. Steve says:

    Hi Marc,

    I don’t see in your article any mention of a couple of major behavioural difference between Qt and STL containers – exceptions and sizes.

    If you ask for the position of something that isn’t there, an STL container will throw an exception as it can’t return a valid answer. Qt doesn’t explicitly use exceptions and will return -1, which in turn is only possible because it uses ‘int’ (ie: signed) as its size type; STL uses ‘size_type’ – normally a typedef for size_t. QVector is therefore limited to max 2GB, even on 64bit.

    This makes STL and Qt containers incompatible in quite a subtle way, that may not be picked up by the compiler. For anyone going between size_t usage and Qt, there are potential casting gotchas and more bounds checking to be dealt with.

    Steve

    • marcmutz says:

      Hi Steve,

      Thanks for the input, I’ve added sections on Size Types and Error Handling to the section on STL/Qt container differences.

  11. Pingback: Heise iX: QtQuick article, KDAB whitepaper; Qt Containers update « -Wmarc

  12. Paul Gideon Dann says:

    There’s a couple of points I’d like to make in defence of QList, and two in defence of Qt’s Container classes in general:

    * It can be a real pain to get halfway through a class implementation before discovering that you need queue semantics, for instance. QList is more versatile than QVector in this regard, because it acts as a Vector in most situations, but also acts well as a queue.

    * QList is faster at inserting items in the first half of the list. At least it *should* be. Because there’s room in front of the list, QList will always memmove() the smaller end when inserting an item.

    * Qt is portable, and you can be sure that its container classes will perform identically on each platform. The same is not true of the STL containers, which way differ significantly from platform to platform; they’re just not as dependable.

    * You really can’t discount ease-of-use. Qt has beautiful, well-documented APIs, and I simply *enjoy* using Qt more than STL.

    I found the following very helpful: http://doc.qt.nokia.com/qq/qq19-containers.html

    • marcmutz says:

      * It can be a real pain to get halfway through a class implementation before discovering that you need queue semantics, for instance. QList is more versatile than QVector in this regard, because it acts as a Vector in most situations, but also acts well as a queue.

      So what you’re saying is that this is happening so often that it’s much more complicated to just s/vector/deque/ in two files than it is to always use QList? And that you’re writing such classes more often than you run your program (since you’re trading typing speed over runtime efficiency)? Interesting.

      * QList is faster at inserting items in the first half of the list. At least it *should* be. Because there’s room in front of the list, QList will always memmove() the smaller end when inserting an item.

      So what you’re saying is that your application runtime, when limited to container use, (the few times it’s actually run, see above) is dominated by insertions in the first half of collections, instead of appends, like 99% of all other applications?

      You see where I’m going? In defense of the QTL, you’re picking marginal use-cases where Qt might perform better. That’s selective perception par excellence. You’re not providing data, only beliefs.

      * Qt is portable, and you can be sure that its container classes will perform identically on each platform. The same is not true of the STL containers, which way differ significantly from platform to platform; they’re just not as dependable.

      You’re comparing apples and oranges (API specification and implementation). Of course, a single implementation will perform the same on each platform. If you depend on that, use a single STL implementation across all your platforms, e.g. STLport or EASTL.

      * You really can’t discount ease-of-use. Qt has beautiful, well-documented APIs, and I simply *enjoy* using Qt more than STL.

      Yes, if you come to C++ by Qt, then you’re bound to like the Qt APIs better, because they’re documented together with the rest of Qt. Let me guess: you also don’t like Boost, in fact, you don’t like any library that isn’t Qt-ish? Well, that’s your opinion, and as such, it’s fine. I like the Qt style guide better than the STL one, too. But as a programmer, if I have the choice between a library that is more stable, more flexible, has more features, and has been independently implemented in at the very least three different flavours (SGI-style, RougeWave-style, and EASTL) partly by people who make a living off implementing that library alone, and that is documented in a book with more than 700 pages, versus a library that changes API every few years, is less flexible, has less features, has been only implemented once, by a company for which this library isn’t a core business, but whose minimal API docs are in the same format as the main library I use, which one should I choose? Well, the question must really be: how could I possibly defend the decision to not go with the former to my stakeholders?

      But that’s not really the point of the article. The point is that if you use the QTL, do so consciously trading the STL features for the convenience of the QTL. That’s fine, as long as you’re aware that you do so.

      • Paul Gideon Dann says:

        I should clarify that I found your article really helpful in raising issues that I hadn’t really considered carefully enough previously. However, I feel that it’s important to note that the article only really investigates raw speed, whereas in practice there are also issues of convenience, ease-of-use, and aesthetics (beautiful code is easier to maintain). Since the article is entitled “Understanding Qt Containers”, this is maybe a little one-sided; hence my defence of Qt.

        In reply:

        1) What I’m saying is that there are human considerations too. Ease-of-use is important, especially in the 80% of the code that isn’t performance-critical. For instance, consistently presenting QList in public member functions will improve the clarity of your API (and is possible because it’s a good all-rounder), but I concede that it looks like QVector may be more sensible in implementation. I’m particularly disappointed that QList is inefficient with QSharedPointers.

        2) I’m saying that for random insertions, QList should be on average twice as fast as QVector. There are many situations in which that’s important. In the interests of being fair, I think it’s worth mentioning.

        3) OK; fair enough. I don’t know much about portable STL implementations.

        4) I find Qt code easier to read and maintain. I’m also a Ruby programmer and find both Boost and Python ugly, even though I know they’re both very powerful. At the end of the day, certain people are attracted to different things. I follow Qt development pretty closely, and I’ve agreed with the Qt developers on so many decisions that I simply trust their work more than any other library I’ve come across.

        I’d also like to add that the very fact that Qt is so wide-ranging makes development significantly faster and easier. Using STL in combination with Qt would add complexity and inefficiency, and cutting out Qt altogether would mean pulling in several other, separate libraries. Making the most of what Qt offers leads to cleaner code, and for around 80% of the code, that’s more important that performance.

        Some may find this helpful, too: http://blog.codeimproved.net/2009/12/qtl-or-stl .

      • Felix says:

        I second Pauls answer to this in his points 1) and 4). The raw speed gain is definitely overrated in this discussion *for most applications*. In one of my project, I store billions of 3D-points, and it is definitely good to know that a std::vector is the right choice there, but containers are ubiquitous and mostly speed to the microsecond doesn’t matter.

        “But as a programmer, if I have the choice between a library that is more stable, more flexible, has more features, and has been independently implemented in at the very least three different flavours (SGI-style, RougeWave-style, and EASTL) partly by people who make a living off implementing that library alone, and that is documented in a book with more than 700 pages, versus a library that changes API every few years, is less flexible, has less features, has been only implemented once, by a company for which this library isn’t a core business, but whose minimal API docs are in the same format as the main library I use, which one should I choose? Well, the question must really be: how could I possibly defend the decision to not go with the former to my stakeholders?”

        Well, how could anyone then possibly defend the decision to use anything that is either new or progressing? With this simplified question how do people justify the use of java, let alone scripting languages? And speaking of java: Oracle is a company of which the core business isn’t java, is it? Now, of course, go ahead and dismiss java…

        I definitely enjoyed your article, but here I feel you condescend to the points of Paul Gideon Dann, uncompromisingly worshipping machine-performance.

      • Josh says:

        Saying proudly that you need a book of 700 pages to describe the implementation of your container classes makes you such a C++ programmer cliche (http://harmful.cat-v.org/software/c++/)

        Although you do raise a few interesting points in your article, it is heavily biased.

  13. Paul Gideon Dann says:

    I’ve put together some simple tests of my own, and made some interesting conclusions. It would be interesting to have them checked independently.

    Basically, I have this testcase, on a 64-bit machine:

    struct Type { char bla[n]; };

    Type object;
    QBENCHMARK {
    QList list;
    for (int i = 0; i < iterations; i++) {
    list.append(object);
    }
    }

    I do the same thing for QVector. I run the benchmark for different values of iterations (10, 100, 1000…100000), and for different sizes of payload (n). I ran it first with no typeinfo, and then with Type set to Q_MOVABLE_TYPE. I also tried appending QSharedPointer objects, which I initialised with a “new Type”. I found that empty QSharedPointers behaved differently; probably because their constructors become trivial.

    Without Type -> Q_MOVABLE_TYPE:
    * For low values of n (small payload), QList was slower (7.6ms vs 1.5ms over 100000 iterations at n=8, which is void* size).
    * For values of n around 128, the roles reversed, and QList was faster, initially only for a large number of iterations (10000+), and then by n=256, even 10 appends were faster in QList than QVector. It’s no surprise that vectors don’t deal well with wide types.
    * QSharedPointers were appended faster by QList, by a noticeable margin.

    With Type -> Q_MOVABLE_TYPE:
    * QVector is faster from n=1 to n=4, and then QList is faster until n=8, at which point QVector becomes faster again.
    * QSharedPointers were appended at the same speed by QList, but QVector was much faster, and beat QList by about the same margin as it lost by without Q_MOVABLE_TYPE, which indicates that QSharedPointer’s constructor plays an important role in copying performance.

    I also found that objects of implicitly-shared classes such as QByteArray resulted in identical performance between QList and QVector.

    Prepends were always extremely faster with QList.
    Middle-inserts (“list.insert(i/2, object)”) were always faster with QList.

    So basically, QList is better if:
    * You want to prepend or insert
    * Your value is not movable, and the constructor is non-trivial, such as for initialised QSharedPointers (which is a pleasant surprise!), and most custom classes.
    * Your value is really wide (unlikely)

    In particular, I think you need to further investigate the cost of object construction in your own test framework, as this is an important real-world case where QList performs better.

  14. Pingback: KDAB - Effective Qt – articles by KDAB’s Marc Mutz

  15. Benoit says:

    Nice article which explains pretty well why QList is far from being always the best choice.

    I still see an interesting use case for QList when mainting a large collection of items with both frequent random access and insertions.

    For example, when performing many insertions at random positions, I get the following benchmark results:
    – 10000 integers, 10000 insertions: QList 14ms, QVector/std::vector 32ms, QLinkedList/std::list 211ms
    – 10000 strings, 10000 insertions: QList 14ms, QVector 33ms, QLinkedList 211ms, std::vector 2082ms (!), std::list 213ms
    – 10000 QSharedPointers, 10000 insertions: QList 15ms, QVector/std::vector 4526ms/5805ms, QList/std::list 227ms

    While I agree that performing insertions in the middle of a list is not the most common case (append being used more often), we have here a quite interesting use case where QList significantly outperforms the other container classes. It is for example the case if you need to maintain an item model (thus with random access as requirement) while permanently inserting new elements to the model.

    Additionally, it should be noted that the overhead while appending items to a list can usually be neglected which is not necessarily the case when inserting elements in the middle of the list.

  16. Pingback: KDAB contributions to Qt 5.0 (part 2) - Bartle Doo

  17. Pingback: KDAB contributions to Qt 5.0 (part 2)Boredome | Boredome

  18. Cosmo says:

    Are STL containers thread safe?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: