path: root/src/corelib/doc/src/containers.qdoc

/****************************************************************************
**
** Copyright (C) 2016 The Qt Company Ltd.
** Contact: https://www.qt.io/licensing/
**
** This file is part of the documentation of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:FDL$
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
** a written agreement between you and The Qt Company. For licensing terms
** and conditions see https://www.qt.io/terms-conditions. For further
** information use the contact form at https://www.qt.io/contact-us.
**
** GNU Free Documentation License Usage
** Alternatively, this file may be used under the terms of the GNU Free
** Documentation License version 1.3 as published by the Free Software
** Foundation and appearing in the file included in the packaging of
** this file. Please review the following information to ensure
** the GNU Free Documentation License version 1.3 requirements
** will be met: https://www.gnu.org/licenses/fdl-1.3.html.
** $QT_END_LICENSE$
**
****************************************************************************/

/*!
    \page containers.html
    \title Container Classes
    \ingroup groups
    \ingroup qt-basic-concepts
    \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 QList<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.

    The containers provide iterators for traversal. \l{STL-style iterators}
    are the most efficient ones and can be used together with Qt's and
    STL's \l{generic algorithms}.
    \l{Java-style Iterators} are provided for backwards compatibility.

    Qt also offers a \l{foreach} keyword that make it very
    easy to iterate over all the items stored in a container.

    \note Since Qt 5.14, range constructors are available for most of the
    container classes. QMultiMap is a notable exception. Their use is
    encouraged in place of the various from/to methods. For example:

    \snippet code/doc_src_containers.cpp 25

    \section1 The Container Classes

    Qt provides the following sequential containers: QList,
    QStack, and QQueue. For most
    applications, QList is the best type to use. It provides very fast
    appends. If you really need a linked-list, use std::list.
    QStack and QQueue are convenience classes that provide LIFO and
    FIFO semantics.

    Qt also provides these associative containers: QMap,
    QMultiMap, QHash, QMultiHash, and QSet. The "Multi" containers
    conveniently support multiple values associated with a single
    key. The "Hash" containers provide faster lookup by using a hash
    function instead of a binary search on a sorted set.

    As special cases, the QCache and QContiguousCache classes provide
    efficient hash-lookup of objects in a limited cache storage.

    \table
    \header \li Class \li Summary

    \row \li \l{QList}<T>
    \li 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, it stores an array of values of a
    given type at adjacent
    positions in memory. Inserting at the front or in the middle of
    a list can be quite slow, because it can lead to large numbers
    of items having to be moved by one position in memory.

    \row \li \l{QVarLengthArray}<T, Prealloc>
    \li This provides a low-level variable-length array. It can be used
    instead of QList in places where speed is particularly important.

    \row \li \l{QStack}<T>
    \li This is a convenience subclass of QList that provides
    "last in, first out" (LIFO) semantics. It adds the following
    functions to those already present in QList:
    \l{QStack::push()}{push()}, \l{QStack::pop()}{pop()},
    and \l{QStack::top()}{top()}.

    \row \li \l{QQueue}<T>
    \li 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 \li \l{QSet}<T>
    \li This provides a single-valued mathematical set with fast
    lookups.

    \row \li \l{QMap}<Key, T>
    \li 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 \li \l{QMultiMap}<Key, T>
    \li 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 \li \l{QHash}<Key, T>
    \li This has almost the same API as QMap, but provides
    significantly faster lookups. QHash stores its data in an
    arbitrary order.

    \row \li \l{QMultiHash}<Key, T>
    \li 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 containers are defined in individual header files with the
    same name as the container (e.g., \c <QList>). For
    convenience, the containers are forward declared in \c
    <QtContainerFwd>.

    \target assignable data type
    \target 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
    copy constructor, and an assignment operator. For some
    operations a default constructor is also required. 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 code/doc_src_containers.cpp 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 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 streaming/main.cpp 1
    \codeline
    \snippet streaming/main.cpp 2

    \target default-constructed value

    The documentation of certain container class functions refer to
    \e{default-constructed values}; for example, QList
    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: STL-style
    iterators and Java-style iterators. Iterators of both types are
    invalidated when the data in the container is modified or detached
    from \l{Implicit Sharing}{implicitly shared copies} due to a call
    to a non-const member function.

    \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 \li Containers                        \li Read-only iterator
                                                  \li Read-write iterator
    \row    \li QList<T>, QStack<T>, QQueue<T>    \li QList<T>::const_iterator
                                                  \li QList<T>::iterator
    \row    \li QSet<T>                           \li QSet<T>::const_iterator
                                                  \li QSet<T>::iterator
    \row    \li QMap<Key, T>, QMultiMap<Key, T>   \li QMap<Key, T>::const_iterator
                                                  \li QMap<Key, T>::iterator
    \row    \li QHash<Key, T>, QMultiHash<Key, T> \li QHash<Key, T>::const_iterator
                                                  \li 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 QList and QStack, which store their
    items at adjacent memory positions, the
    \l{QList::iterator}{iterator} type is just a typedef for \c{T *},
    and the \l{QList::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 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 code/doc_src_containers.cpp 10

    STL-style iterators point directly at items. The \l{QList::begin()}{begin()}
    function of a container returns an iterator that points to the first item in the
    container. The \l{QList::end()}{end()} function of a container returns an iterator to the
    imaginary item one position past the last item in the container.
    \l {QList::end()}{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, \l{QList::begin}{begin()} equals \l{QList::end()}{end()}, so we never execute the loop.

    The diagram below shows the valid iterator positions as red
    arrows for a list containing four items:

    \image stliterators1.png

    Iterating backward with an STL-style iterator is done with reverse iterators:

    \snippet code/doc_src_containers.cpp 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, \l{QList::constBegin}{constBegin()},
    and \l{QList::constEnd()}{constEnd()}. For example:

    \snippet code/doc_src_containers.cpp 12

    The following table summarizes the STL-style iterators' API:

    \table
    \header \li Expression \li Behavior
    \row    \li \c{*i}     \li Returns the current item
    \row    \li \c{++i}    \li Advances the iterator to the next item
    \row    \li \c{i += n} \li Advances the iterator by \c n items
    \row    \li \c{--i}    \li Moves the iterator back by one item
    \row    \li \c{i -= n} \li Moves the iterator back by \c n items
    \row    \li \c{i - j}  \li 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 code/doc_src_containers.cpp 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 code/doc_src_containers.cpp 14

    This problem doesn't occur with functions that return a const or
    non-const reference to a container.

    \section3 Implicit sharing iterator problem

    \l{Implicit sharing} has another consequence on STL-style
    iterators: you should avoid copying a container while
    iterators are active on that container. The iterators
    point to an internal structure, and if you copy a container
    you should be very careful with your iterators. E.g:

    \snippet code/doc_src_containers.cpp 24

     The above example only shows a problem with QList, but
     the problem exists for all the implicitly shared Qt containers.

    \section2 Java-Style Iterators
    \l{java-style-iterators}{Java-Style iterators} were introduced in Qt 4. Their API is modelled
    on Java's iterator classes.
    New code should should prefer \l{STL-Style Iterators}.

    \target 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 QList<QString>:

    \snippet code/doc_src_containers.cpp 15

    The \c foreach code is significantly shorter than the equivalent
    code that uses iterators:

    \snippet code/doc_src_containers.cpp 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 code/doc_src_containers.cpp 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 code/doc_src_containers.cpp 18

    With QMap and QHash, \c foreach accesses the value component of
    the (key, value) pairs automatically, so you should not call
    values() on the container (it would generate an unnecessary copy,
    see below). If you want to iterate over both the keys and the
    values, you can use iterators (which are faster), or you can
    obtain the keys, and use them to get the values too:

    \snippet code/doc_src_containers.cpp 19

    For a multi-valued map:

    \snippet code/doc_src_containers.cpp 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 do not modify the
    container, the copy still takes place, but thanks to \l{implicit
    sharing} copying a container is very fast.)

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

    An alternative to Qt's \c foreach loop is the range-based \c for that is
    part of C++ 11 and newer. However, keep in mind that the range-based
    \c for might force a Qt container to \l{Implicit Sharing}{detach}, whereas
    \c foreach would not. But using \c foreach always copies the container,
    which is usually not cheap for STL containers. If in doubt, prefer
    \c foreach for Qt containers, and range based \c for for STL ones.

    In addition to \c foreach, Qt also provides a \c forever
    pseudo-keyword for infinite loops:

    \snippet code/doc_src_containers.cpp 21

    If you're worried about namespace pollution, you can disable
    these macros by adding the following line to your \c .pro file:

    \snippet code/doc_src_containers.cpp 22

    \section1 Other Container-Like Classes

    Qt includes other template classes that resemble containers in
    some respects. These classes don't provide iterators and cannot
    be used with the \c foreach keyword.

    \list
    \li QCache<Key, T> provides a cache to store objects of a certain
       type T associated with keys of type Key.

    \li QContiguousCache<T> provides an efficient way of caching data
    that is typically accessed in a contiguous way.
    \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 std::list is an
    extremely fast operation, irrespective of the number of items
    stored in the list. On the other hand, inserting an item
    in the middle of a QList is potentially very expensive if the
    QList 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:

    \target constant time
    \target logarithmic time
    \target linear time
    \target linear-logarithmic time
    \target quadratic time

    \list
    \li \b{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
       QList::push_back().

    \li \b{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 the binary search algorithm.

    \li \b{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
       QList::insert().

    \li \b{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.

    \li \b{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 the sequential
    container QList<T>:

    \table
    \header \li          \li Index lookup \li Insertion \li Prepending \li Appending
    \row    \li QList<T> \li O(1)         \li O(n)      \li O(n)       \li 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 \li{1,2}          \li{2,1} Key lookup            \li{2,1} Insertion
    \header                  \li Average     \li Worst case  \li Average            \li Worst case
    \row    \li QMap<Key, T>  \li O(log \e n) \li O(log \e n) \li O(log \e n)        \li O(log \e n)
    \row    \li QMultiMap<Key, T>  \li O(log \e n) \li O(log \e n) \li O(log \e n)   \li O(log \e n)
    \row    \li QHash<Key, T> \li Amort. O(1) \li O(\e n)     \li Amort. O(1)        \li O(\e n)
    \row    \li QSet<Key>     \li Amort. O(1) \li O(\e n)     \li Amort. O(1)        \li O(\e n)
    \endtable

    With QList, QHash, and QSet, the performance of appending items
    is amortized O(log \e n). It can be brought down to O(1) by
    calling QList::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

    QList<T>, QString, and QByteArray store their items
    contiguously in memory; 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 code/doc_src_containers.cpp 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
    \li QString allocates 4 characters at a time until it reaches size 20.
    \li 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.)
    \li 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 uses more or less the same algorithm as
    QString.

    QList<T> also uses that algorithm for data types that can be
    moved around in memory using \c 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, QList<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, QList<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
    \li \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).
    \li \l{QString::reserve()}{reserve}(\e size) explicitly
       preallocates memory for \e size items.
    \li \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 \l{QString::reserve()}{reserve()}, and when you are
    done populating the container, you can call \l{QString::squeeze()}{squeeze()} to release
    the extra preallocated memory.
*/