Long live Qt 4.5!

1 files changed, 775 insertions, 0 deletions

diff --git a/doc/src/containers.qdoc b/doc/src/containers.qdoc
new file mode 100644
index 0000000..d107277
--- /dev/null
+++ b/doc/src/containers.qdoc
@@ -0,0 +1,775 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** Contact: Qt Software Information (qt-info@nokia.com)
+**
+** This file is part of the documentation of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the either Technology Preview License Agreement or the
+** Beta Release License Agreement.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain
+** additional rights. These rights are described in the Nokia Qt LGPL
+** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this
+** package.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 3.0 as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU General Public License version 3.0 requirements will be
+** met: http://www.gnu.org/copyleft/gpl.html.
+**
+** If you are unsure which license is appropriate for your use, please
+** contact the sales department at qt-sales@nokia.com.
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+/*!
+    \group containers
+    \title Generic Containers
+    \ingroup architecture
+    \ingroup groups
+    \keyword container class
+    \keyword container classes
+
+    \brief Qt's template-based container classes.
+
+    \tableofcontents
+
+    \section1 Introduction
+
+    The Qt library provides a set of general purpose template-based
+    container classes. These classes can be used to store items of a
+    specified type. For example, if you need a resizable array of
+    \l{QString}s, use QVector<QString>.
+
+    These container classes are designed to be lighter, safer, and
+    easier to use than the STL containers. If you are unfamiliar with
+    the STL, or prefer to do things the "Qt way", you can use these
+    classes instead of the STL classes.
+
+    The container classes are \l{implicitly shared}, they are
+    \l{reentrant}, and they are optimized for speed, low memory
+    consumption, and minimal inline code expansion, resulting in
+    smaller executables. In addition, they are \l{thread-safe}
+    in situations where they are used as read-only containers
+    by all threads used to access them.
+
+    For traversing the items stored in a container, you can use one
+    of two types of iterators: \l{Java-style iterators} and
+    \l{STL-style iterators}. The Java-style iterators are easier to
+    use and provide high-level functionality, whereas the STL-style
+    iterators are slightly more efficient and can be used together
+    with Qt's and STL's \l{generic algorithms}.
+
+    Qt also offers a \l{foreach} keyword that make it very
+    easy to iterate over all the items stored in a container.
+
+    \section1 The Container Classes
+
+    Qt provides the following container classes:
+
+    \table
+    \header \o Class \o Summary
+
+    \row \o \l{QList}<T>
+    \o This is by far the most commonly used container class. It
+    stores a list of values of a given type (T) that can be accessed
+    by index. Internally, the QList is implemented using an array,
+    ensuring that index-based access is very fast.
+
+    Items can be added at either end of the list using
+    QList::append() and QList::prepend(), or they can be inserted in
+    the middle using QList::insert(). More than any other container
+    class, QList is highly optimized to expand to as little code as
+    possible in the executable. QStringList inherits from
+    QList<QString>.
+
+    \row \o \l{QLinkedList}<T>
+    \o This is similar to QList, except that it uses
+    iterators rather than integer indexes to access items. It also
+    provides better performance than QList when inserting in the
+    middle of a huge list, and it has nicer iterator semantics.
+    (Iterators pointing to an item in a QLinkedList remain valid as
+    long as the item exists, whereas iterators to a QList can become
+    invalid after any insertion or removal.)
+
+    \row \o \l{QVector}<T>
+    \o This stores an array of values of a given type at adjacent
+    positions in memory. Inserting at the front or in the middle of
+    a vector can be quite slow, because it can lead to large numbers
+    of items having to be moved by one position in memory.
+
+    \row \o \l{QStack}<T>
+    \o This is a convenience subclass of QVector that provides
+    "last in, first out" (LIFO) semantics. It adds the following
+    functions to those already present in QVector:
+    \l{QStack::push()}{push()}, \l{QStack::pop()}{pop()},
+    and \l{QStack::top()}{top()}.
+
+    \row \o \l{QQueue}<T>
+    \o This is a convenience subclass of QList that provides
+    "first in, first out" (FIFO) semantics. It adds the following
+    functions to those already present in QList:
+    \l{QQueue::enqueue()}{enqueue()},
+    \l{QQueue::dequeue()}{dequeue()}, and \l{QQueue::head()}{head()}.
+
+    \row \o \l{QSet}<T>
+    \o This provides a single-valued mathematical set with fast
+    lookups.
+
+    \row \o \l{QMap}<Key, T>
+    \o This provides a dictionary (associative array) that maps keys
+    of type Key to values of type T. Normally each key is associated
+    with a single value. QMap stores its data in Key order; if order
+    doesn't matter QHash is a faster alternative.
+
+    \row \o \l{QMultiMap}<Key, T>
+    \o This is a convenience subclass of QMap that provides a nice
+    interface for multi-valued maps, i.e. maps where one key can be
+    associated with multiple values.
+
+    \row \o \l{QHash}<Key, T>
+    \o This has almost the same API as QMap, but provides
+    significantly faster lookups. QHash stores its data in an
+    arbitrary order.
+
+    \row \o \l{QMultiHash}<Key, T>
+    \o This is a convenience subclass of QHash that
+    provides a nice interface for multi-valued hashes.
+
+    \endtable
+
+    Containers can be nested. For example, it is perfectly possible
+    to use a QMap<QString, QList<int> >, where the key type is
+    QString and the value type QList<int>. The only pitfall is that
+    you must insert a space between the closing angle brackets (>);
+    otherwise the C++ compiler will misinterpret the two >'s as a
+    right-shift operator (>>) and report a syntax error.
+
+    The containers are defined in individual header files with the
+    same name as the container (e.g., \c <QLinkedList>). For
+    convenience, the containers are forward declared in \c
+    <QtContainerFwd>.
+
+    \keyword assignable data type
+    \keyword assignable data types
+
+    The values stored in the various containers can be of any
+    \e{assignable data type}. To qualify, a type must provide a
+    default constructor, a copy constructor, and an assignment
+    operator. This covers most data types you are likely to want to
+    store in a container, including basic types such as \c int and \c
+    double, pointer types, and Qt data types such as QString, QDate,
+    and QTime, but it doesn't cover QObject or any QObject subclass
+    (QWidget, QDialog, QTimer, etc.). If you attempt to instantiate a
+    QList<QWidget>, the compiler will complain that QWidget's copy
+    constructor and assignment operators are disabled. If you want to
+    store these kinds of objects in a container, store them as
+    pointers, for example as QList<QWidget *>.
+
+    Here's an example custom data type that meets the requirement of
+    an assignable data type:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 0
+
+    If we don't provide a copy constructor or an assignment operator,
+    C++ provides a default implementation that performs a
+    member-by-member copy. In the example above, that would have been
+    sufficient. Also, if you don't provide any constructors, C++
+    provides a default constructor that initializes its member using
+    default constructors. Although it doesn't provide any
+    explicit constructors or assignment operator, the following data
+    type can be stored in a container:
+
+    \snippet doc/src/snippets/streaming/main.cpp 0
+
+    Some containers have additional requirements for the data types
+    they can store. For example, the Key type of a QMap<Key, T> must
+    provide \c operator<(). Such special requirements are documented
+    in a class's detailed description. In some cases, specific
+    functions have special requirements; these are described on a
+    per-function basis. The compiler will always emit an error if a
+    requirement isn't met.
+
+    Qt's containers provide operator<<() and operator>>() so that they
+    can easily be read and written using a QDataStream. This means
+    that the data types stored in the container must also support
+    operator<<() and operator>>(). Providing such support is
+    straightforward; here's how we could do it for the Movie struct
+    above:
+
+    \snippet doc/src/snippets/streaming/main.cpp 1
+    \codeline
+    \snippet doc/src/snippets/streaming/main.cpp 2
+
+    \keyword default-constructed values
+
+    The documentation of certain container class functions refer to
+    \e{default-constructed values}; for example, QVector
+    automatically initializes its items with default-constructed
+    values, and QMap::value() returns a default-constructed value if
+    the specified key isn't in the map. For most value types, this
+    simply means that a value is created using the default
+    constructor (e.g. an empty string for QString). But for primitive
+    types like \c{int} and \c{double}, as well as for pointer types,
+    the C++ language doesn't specify any initialization; in those
+    cases, Qt's containers automatically initialize the value to 0.
+
+    \section1 The Iterator Classes
+
+    Iterators provide a uniform means to access items in a container.
+    Qt's container classes provide two types of iterators: Java-style
+    iterators and STL-style iterators.
+
+    \section2 Java-Style Iterators
+
+    The Java-style iterators are new in Qt 4 and are the standard
+    ones used in Qt applications. They are more convenient to use than
+    the STL-style iterators, at the price of being slightly less
+    efficient. Their API is modelled on Java's iterator classes.
+
+    For each container class, there are two Java-style iterator data
+    types: one that provides read-only access and one that provides
+    read-write access.
+
+    \table
+    \header \o Containers                         \o Read-only iterator
+                                                  \o Read-write iterator
+    \row    \o QList<T>, QQueue<T>                \o QListIterator<T>
+                                                  \o QMutableListIterator<T>
+    \row    \o QLinkedList<T>                     \o QLinkedListIterator<T>
+                                                  \o QMutableLinkedListIterator<T>
+    \row    \o QVector<T>, QStack<T>              \o QVectorIterator<T>
+                                                  \o QMutableVectorIterator<T>
+    \row    \o QSet<T>                            \o QSetIterator<T>
+                                                  \o QMutableSetIterator<T>
+    \row    \o QMap<Key, T>, QMultiMap<Key, T>    \o QMapIterator<Key, T>
+                                                  \o QMutableMapIterator<Key, T>
+    \row    \o QHash<Key, T>, QMultiHash<Key, T>  \o QHashIterator<Key, T>
+                                                  \o QMutableHashIterator<Key, T>
+    \endtable
+
+    In this discussion, we will concentrate on QList and QMap. The
+    iterator types for QLinkedList, QVector, and QSet have exactly
+    the same interface as QList's iterators; similarly, the iterator
+    types for QHash have the same interface as QMap's iterators.
+
+    Unlike STL-style iterators (covered \l{STL-style
+    iterators}{below}), Java-style iterators point \e between items
+    rather than directly \e at items. For this reason, they are
+    either pointing to the very beginning of the container (before
+    the first item), at the very end of the container (after the last
+    item), or between two items. The diagram below shows the valid
+    iterator positions as red arrows for a list containing four
+    items:
+
+    \img javaiterators1.png
+
+    Here's a typical loop for iterating through all the elements of a
+    QList<QString> in order and printing them to the console:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 1
+
+    It works as follows: The QList to iterate over is passed to the
+    QListIterator constructor. At that point, the iterator is located
+    just in front of the first item in the list (before item "A").
+    Then we call \l{QListIterator::hasNext()}{hasNext()} to
+    check whether there is an item after the iterator. If there is, we
+    call \l{QListIterator::next()}{next()} to jump over that
+    item. The next() function returns the item that it jumps over. For
+    a QList<QString>, that item is of type QString.
+
+    Here's how to iterate backward in a QList:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 2
+
+    The code is symmetric with iterating forward, except that we
+    start by calling \l{QListIterator::toBack()}{toBack()}
+    to move the iterator after the last item in the list.
+
+    The diagram below illustrates the effect of calling
+    \l{QListIterator::next()}{next()} and
+    \l{QListIterator::previous()}{previous()} on an iterator:
+
+    \img javaiterators2.png
+
+    The following table summarizes the QListIterator API:
+
+    \table
+    \header \o Function \o Behavior
+    \row    \o \l{QListIterator::toFront()}{toFront()}
+            \o Moves the iterator to the front of the list (before the first item)
+    \row    \o \l{QListIterator::toBack()}{toBack()}
+            \o Moves the iterator to the back of the list (after the last item)
+    \row    \o \l{QListIterator::hasNext()}{hasNext()}
+            \o Returns true if the iterator isn't at the back of the list
+    \row    \o \l{QListIterator::next()}{next()}
+            \o Returns the next item and advances the iterator by one position
+    \row    \o \l{QListIterator::peekNext()}{peekNext()}
+            \o Returns the next item without moving the iterator
+    \row    \o \l{QListIterator::hasPrevious()}{hasPrevious()}
+            \o Returns true if the iterator isn't at the front of the list
+    \row    \o \l{QListIterator::previous()}{previous()}
+            \o Returns the previous item and moves the iterator back by one position
+    \row    \o \l{QListIterator::peekPrevious()}{peekPrevious()}
+            \o Returns the previous item without moving the iterator
+    \endtable
+
+    QListIterator provides no functions to insert or remove items
+    from the list as we iterate. To accomplish this, you must use
+    QMutableListIterator. Here's an example where we remove all
+    odd numbers from a QList<int> using QMutableListIterator:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 3
+
+    The next() call in the loop is made every time. It jumps over the
+    next item in the list. The
+    \l{QMutableListIterator::remove()}{remove()} function removes the
+    last item that we jumped over from the list. The call to
+    \l{QMutableListIterator::remove()}{remove()} does not invalidate
+    the iterator, so it is safe to continue using it. This works just
+    as well when iterating backward:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 4
+
+    If we just want to modify the value of an existing item, we can
+    use \l{QMutableListIterator::setValue()}{setValue()}. In the code
+    below, we replace any value larger than 128 with 128:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 5
+
+    Just like \l{QMutableListIterator::remove()}{remove()},
+    \l{QMutableListIterator::setValue()}{setValue()} operates on the
+    last item that we jumped over. If we iterate forward, this is the
+    item just before the iterator; if we iterate backward, this is
+    the item just after the iterator.
+
+    The \l{QMutableListIterator::next()}{next()} function returns a
+    non-const reference to the item in the list. For simple
+    operations, we don't even need
+    \l{QMutableListIterator::setValue()}{setValue()}:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 6
+
+    As mentioned above, QLinkedList's, QVector's, and QSet's iterator
+    classes have exactly the same API as QList's. We will now turn to
+    QMapIterator, which is somewhat different because it iterates on
+    (key, value) pairs.
+
+    Like QListIterator, QMapIterator provides 
+    \l{QMapIterator::toFront()}{toFront()}, 
+    \l{QMapIterator::toBack()}{toBack()}, 
+    \l{QMapIterator::hasNext()}{hasNext()}, 
+    \l{QMapIterator::next()}{next()}, 
+    \l{QMapIterator::peekNext()}{peekNext()}, 
+    \l{QMapIterator::hasPrevious()}{hasPrevious()}, 
+    \l{QMapIterator::previous()}{previous()}, and
+    \l{QMapIterator::peekPrevious()}{peekPrevious()}. The key and
+    value components are extracted by calling key() and value() on
+    the object returned by next(), peekNext(), previous(), or
+    peekPrevious().
+
+    The following example removes all (capital, country) pairs where
+    the capital's name ends with "City":
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 7
+
+    QMapIterator also provides a key() and a value() function that
+    operate directly on the iterator and that return the key and
+    value of the last item that the iterator jumped above. For
+    example, the following code copies the contents of a QMap into a
+    QHash:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 8
+
+    If we want to iterate through all the items with the same
+    value, we can use \l{QMapIterator::findNext()}{findNext()}
+    or \l{QMapIterator::findPrevious()}{findPrevious()}.
+    Here's an example where we remove all the items with a particular
+    value:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 9
+
+    \section2 STL-Style Iterators
+
+    STL-style iterators have been available since the release of Qt
+    2.0. They are compatible with Qt's and STL's \l{generic
+    algorithms} and are optimized for speed.
+
+    For each container class, there are two STL-style iterator types:
+    one that provides read-only access and one that provides
+    read-write access. Read-only iterators should be used wherever
+    possible because they are faster than read-write iterators.
+
+    \table
+    \header \o Containers                         \o Read-only iterator
+                                                  \o Read-write iterator
+    \row    \o QList<T>, QQueue<T>                \o QList<T>::const_iterator
+                                                  \o QList<T>::iterator
+    \row    \o QLinkedList<T>                     \o QLinkedList<T>::const_iterator
+                                                  \o QLinkedList<T>::iterator
+    \row    \o QVector<T>, QStack<T>              \o QVector<T>::const_iterator
+                                                  \o QVector<T>::iterator
+    \row    \o QSet<T>                            \o QSet<T>::const_iterator
+                                                  \o QSet<T>::iterator
+    \row    \o QMap<Key, T>, QMultiMap<Key, T>    \o QMap<Key, T>::const_iterator
+                                                  \o QMap<Key, T>::iterator
+    \row    \o QHash<Key, T>, QMultiHash<Key, T>  \o QHash<Key, T>::const_iterator
+                                                  \o QHash<Key, T>::iterator
+    \endtable
+
+    The API of the STL iterators is modelled on pointers in an array.
+    For example, the \c ++ operator advances the iterator to the next
+    item, and the \c * operator returns the item that the iterator
+    points to. In fact, for QVector and QStack, which store their
+    items at adjacent memory positions, the
+    \l{QVector::iterator}{iterator} type is just a typedef for \c{T *},
+    and the \l{QVector::iterator}{const_iterator} type is
+    just a typedef for \c{const T *}.
+
+    In this discussion, we will concentrate on QList and QMap. The
+    iterator types for QLinkedList, QVector, and QSet have exactly
+    the same interface as QList's iterators; similarly, the iterator
+    types for QHash have the same interface as QMap's iterators.
+
+    Here's a typical loop for iterating through all the elements of a
+    QList<QString> in order and converting them to lowercase:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 10
+
+    Unlike \l{Java-style iterators}, STL-style iterators point
+    directly at items. The begin() function of a container returns an
+    iterator that points to the first item in the container. The
+    end() function of a container returns an iterator to the
+    imaginary item one position past the last item in the container.
+    end() marks an invalid position; it must never be dereferenced.
+    It is typically used in a loop's break condition. If the list is
+    empty, begin() equals end(), so we never execute the loop.
+
+    The diagram below shows the valid iterator positions as red
+    arrows for a vector containing four items:
+
+    \img stliterators1.png
+
+    Iterating backward with an STL-style iterator requires us to
+    decrement the iterator \e before we access the item. This
+    requires a \c while loop:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 11
+
+    In the code snippets so far, we used the unary \c * operator to
+    retrieve the item (of type QString) stored at a certain iterator
+    position, and we then called QString::toLower() on it. Most C++
+    compilers also allow us to write \c{i->toLower()}, but some
+    don't.
+
+    For read-only access, you can use const_iterator, constBegin(),
+    and constEnd(). For example:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 12
+
+    The following table summarizes the STL-style iterators' API:
+
+    \table
+    \header \o Expression \o Behavior
+    \row    \o \c{*i}     \o Returns the current item
+    \row    \o \c{++i}    \o Advances the iterator to the next item
+    \row    \o \c{i += n} \o Advances the iterator by \c n items
+    \row    \o \c{--i}    \o Moves the iterator back by one item
+    \row    \o \c{i -= n} \o Moves the iterator back by \c n items
+    \row    \o \c{i - j}  \o Returns the number of items between iterators \c i and \c j
+    \endtable
+
+    The \c{++} and \c{--} operators are available both as prefix
+    (\c{++i}, \c{--i}) and postfix (\c{i++}, \c{i--}) operators. The
+    prefix versions modify the iterators and return a reference to
+    the modified iterator; the postfix versions take a copy of the
+    iterator before they modify it, and return that copy. In
+    expressions where the return value is ignored, we recommend that
+    you use the prefix operators (\c{++i}, \c{--i}), as these are
+    slightly faster.
+
+    For non-const iterator types, the return value of the unary \c{*}
+    operator can be used on the left side of the assignment operator.
+
+    For QMap and QHash, the \c{*} operator returns the value
+    component of an item. If you want to retrieve the key, call key()
+    on the iterator. For symmetry, the iterator types also provide a
+    value() function to retrieve the value. For example, here's how
+    we would print all items in a QMap to the console:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 13
+
+    Thanks to \l{implicit sharing}, it is very inexpensive for a
+    function to return a container per value. The Qt API contains
+    dozens of functions that return a QList or QStringList per value
+    (e.g., QSplitter::sizes()). If you want to iterate over these
+    using an STL iterator, you should always take a copy of the
+    container and iterate over the copy. For example:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 14
+
+    This problem doesn't occur with functions that return a const or
+    non-const reference to a container.
+
+    \l{Implicit sharing} has another consequence on STL-style
+    iterators: You must not take a copy of a container while
+    non-const iterators are active on that container. Java-style
+    iterators don't suffer from that limitation.
+
+    \keyword foreach
+    \section1 The foreach Keyword
+
+    If you just want to iterate over all the items in a container
+    in order, you can use Qt's \c foreach keyword. The keyword is a
+    Qt-specific addition to the C++ language, and is implemented
+    using the preprocessor.
+
+    Its syntax is: \c foreach (\e variable, \e container) \e
+    statement. For example, here's how to use \c foreach to iterate
+    over a QLinkedList<QString>:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 15
+
+    The \c foreach code is significantly shorter than the equivalent
+    code that uses iterators:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 16
+
+    Unless the data type contains a comma (e.g., \c{QPair<int,
+    int>}), the variable used for iteration can be defined within the
+    \c foreach statement:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 17
+
+    And like any other C++ loop construct, you can use braces around
+    the body of a \c foreach loop, and you can use \c break to leave
+    the loop:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 18
+
+    With QMap and QHash, \c foreach accesses the value component of
+    the (key, value) pairs. If you want to iterate over both the keys
+    and the values, you can use iterators (which are fastest), or you
+    can write code like this:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 19
+
+    For a multi-valued map:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 20
+
+    Qt automatically takes a copy of the container when it enters a
+    \c foreach loop. If you modify the container as you are
+    iterating, that won't affect the loop. (If you don't modify the
+    container, the copy still takes place, but thanks to \l{implicit
+    sharing} copying a container is very fast.) Similarly, declaring
+    the variable to be a non-const reference, in order to modify the
+    current item in the list will not work either.
+
+    In addition to \c foreach, Qt also provides a \c forever
+    pseudo-keyword for infinite loops:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 21
+
+    If you're worried about namespace pollution, you can disable
+    these macros by adding the following line to your \c .pro file:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 22
+
+    \section1 Other Container-Like Classes
+
+    Qt includes three template classes that resemble containers in
+    some respects. These classes don't provide iterators and cannot
+    be used with the \c foreach keyword.
+
+    \list
+    \o QVarLengthArray<T, Prealloc> provides a low-level
+       variable-length array. It can be used instead of QVector in
+       places where speed is particularly important.
+
+    \o QCache<Key, T> provides a cache to store objects of a certain
+       type T associated with keys of type Key.
+
+    \o QPair<T1, T2> stores a pair of elements.
+    \endlist
+
+    Additional non-template types that compete with Qt's template
+    containers are QBitArray, QByteArray, QString, and QStringList.
+
+    \section1 Algorithmic Complexity
+
+    Algorithmic complexity is concerned about how fast (or slow) each
+    function is as the number of items in the container grow. For
+    example, inserting an item in the middle of a QLinkedList is an
+    extremely fast operation, irrespective of the number of items
+    stored in the QLinkedList. On the other hand, inserting an item
+    in the middle of a QVector is potentially very expensive if the
+    QVector contains many items, since half of the items must be
+    moved one position in memory.
+
+    To describe algorithmic complexity, we use the following
+    terminology, based on the "big Oh" notation:
+
+    \keyword constant time
+    \keyword logarithmic time
+    \keyword linear time
+    \keyword linear-logarithmic time
+    \keyword quadratic time
+
+    \list
+    \o \bold{Constant time:} O(1). A function is said to run in constant
+       time if it requires the same amount of time no matter how many
+       items are present in the container. One example is
+       QLinkedList::insert().
+
+    \o \bold{Logarithmic time:} O(log \e n). A function that runs in
+       logarithmic time is a function whose running time is
+       proportional to the logarithm of the number of items in the
+       container. One example is qBinaryFind().
+
+    \o \bold{Linear time:} O(\e n). A function that runs in linear time
+       will execute in a time directly proportional to the number of
+       items stored in the container. One example is
+       QVector::insert().
+
+    \o \bold{Linear-logarithmic time:} O(\e{n} log \e n). A function
+       that runs in linear-logarithmic time is asymptotically slower
+       than a linear-time function, but faster than a quadratic-time
+       function.
+
+    \o \bold{Quadratic time:} O(\e{n}\unicode{178}). A quadratic-time function
+       executes in a time that is proportional to the square of the
+       number of items stored in the container.
+    \endlist
+
+    The following table summarizes the algorithmic complexity of Qt's
+    sequential container classes:
+
+    \table
+    \header \o                \o Index lookup \o Insertion \o Prepending         \o Appending
+    \row    \o QLinkedList<T> \o O(\e n)      \o O(1)      \o O(1)               \o O(1)
+    \row    \o QList<T>       \o O(1)         \o O(n)      \o Amort. O(1)        \o Amort. O(1)
+    \row    \o QVector<T>     \o O(1)         \o O(n)      \o O(n)               \o Amort. O(1)
+    \endtable
+
+    In the table, "Amort." stands for "amortized behavior". For
+    example, "Amort. O(1)" means that if you call the function
+    only once, you might get O(\e n) behavior, but if you call it
+    multiple times (e.g., \e n times), the average behavior will be
+    O(1).
+
+    The following table summarizes the algorithmic complexity of Qt's
+    associative containers and sets:
+
+    \table
+    \header \o{1,2}          \o{2,1} Key lookup            \o{2,1} Insertion
+    \header                  \o Average     \o Worst case  \o Average            \o Worst case
+    \row    \o QMap<Key, T>  \o O(log \e n) \o O(log \e n) \o O(log \e n)        \o O(log \e n)
+    \row    \o QMultiMap<Key, T>  \o O((log \e n) \o O(log \e n) \o O(log \e n)   \o O(log \e n)
+    \row    \o QHash<Key, T> \o Amort. O(1) \o O(\e n)     \o Amort. O(1)        \o O(\e n)
+    \row    \o QSet<Key>     \o Amort. O(1) \o O(\e n)     \o Amort. O(1)        \o O(\e n)
+    \endtable
+
+    With QVector, QHash, and QSet, the performance of appending items
+    is amortized O(log \e n). It can be brought down to O(1) by
+    calling QVector::reserve(), QHash::reserve(), or QSet::reserve()
+    with the expected number of items before you insert the items.
+    The next section discusses this topic in more depth.
+
+    \section1 Growth Strategies
+
+    QVector<T>, QString, and QByteArray store their items
+    contiguously in memory; QList<T> maintains an array of pointers
+    to the items it stores to provide fast index-based access (unless
+    T is a pointer type or a basic type of the size of a pointer, in
+    which case the value itself is stored in the array); QHash<Key,
+    T> keeps a hash table whose size is proportional to the number
+    of items in the hash. To avoid reallocating the data every single
+    time an item is added at the end of the container, these classes
+    typically allocate more memory than necessary.
+
+    Consider the following code, which builds a QString from another
+    QString:
+
+    \snippet doc/src/snippets/code/doc_src_containers.qdoc 23
+
+    We build the string \c out dynamically by appending one character
+    to it at a time. Let's assume that we append 15000 characters to
+    the QString string. Then the following 18 reallocations (out of a
+    possible 15000) occur when QString runs out of space: 4, 8, 12,
+    16, 20, 52, 116, 244, 500, 1012, 2036, 4084, 6132, 8180, 10228,
+    12276, 14324, 16372. At the end, the QString has 16372 Unicode
+    characters allocated, 15000 of which are occupied.
+
+    The values above may seem a bit strange, but here are the guiding
+    principles:
+    \list
+    \o QString allocates 4 characters at a time until it reaches size 20.
+    \o From 20 to 4084, it advances by doubling the size each time.
+       More precisely, it advances to the next power of two, minus
+       12. (Some memory allocators perform worst when requested exact
+       powers of two, because they use a few bytes per block for
+       book-keeping.)
+    \o From 4084 on, it advances by blocks of 2048 characters (4096
+       bytes). This makes sense because modern operating systems
+       don't copy the entire data when reallocating a buffer; the
+       physical memory pages are simply reordered, and only the data
+       on the first and last pages actually needs to be copied.
+    \endlist
+
+    QByteArray and QList<T> use more or less the same algorithm as
+    QString.
+
+    QVector<T> also uses that algorithm for data types that can be
+    moved around in memory using memcpy() (including the basic C++
+    types, the pointer types, and Qt's \l{shared classes}) but uses a
+    different algorithm for data types that can only be moved by
+    calling the copy constructor and a destructor. Since the cost of
+    reallocating is higher in that case, QVector<T> reduces the
+    number of reallocations by always doubling the memory when
+    running out of space.
+
+    QHash<Key, T> is a totally different case. QHash's internal hash
+    table grows by powers of two, and each time it grows, the items
+    are relocated in a new bucket, computed as qHash(\e key) %
+    QHash::capacity() (the number of buckets). This remark applies to
+    QSet<T> and QCache<Key, T> as well.
+
+    For most applications, the default growing algorithm provided by
+    Qt does the trick. If you need more control, QVector<T>,
+    QHash<Key, T>, QSet<T>, QString, and QByteArray provide a trio of
+    functions that allow you to check and specify how much memory to
+    use to store the items:
+
+    \list
+    \o \l{QString::capacity()}{capacity()} returns the
+       number of items for which memory is allocated (for QHash and
+       QSet, the number of buckets in the hash table).
+    \o \l{QString::reserve()}{reserve}(\e size) explicitly
+       preallocates memory for \e size items.
+    \o \l{QString::squeeze()}{squeeze()} frees any memory
+       not required to store the items.
+    \endlist
+
+    If you know approximately how many items you will store in a
+    container, you can start by calling reserve(), and when you are
+    done populating the container, you can call squeeze() to release
+    the extra preallocated memory.
+*/