source: trunk/doc/src/frameworks-technologies/containers.qdoc@ 846

/****************************************************************************
**
** Copyright (C) 2011 Nokia Corporation and/or its subsidiary(-ies).
** All rights reserved.
** Contact: Nokia Corporation ([email protected])
**
** This file is part of the documentation of the Qt Toolkit.
**
** $QT_BEGIN_LICENSE:FDL$
** Commercial Usage
** Licensees holding valid Qt Commercial licenses may use this file in
** accordance with the Qt Commercial License Agreement provided with the
** Software or, alternatively, in accordance with the terms contained in a
** written agreement between you and Nokia.
**
** GNU Free Documentation License
** 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.
**
** If you have questions regarding the use of this file, please contact
** Nokia at [email protected].
** $QT_END_LICENSE$
**
****************************************************************************/

/*!
    \group tools
    \title Non-GUI Classes
    \ingroup groups

    \brief Collection classes such as list, queue, stack and string, along
    with other classes that can be used without needing QApplication.

    The non-GUI classes are general-purpose collection and string classes
    that may be used independently of the GUI classes.

    In particular, these classes do not depend on QApplication at all,
    and so can be used in non-GUI programs.

*/

/*!
    \page containers.html
    \title Container Classes
    \ingroup technology-apis
    \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 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 sequential containers: QList,
    QLinkedList, QVector, QStack, and QQueue. For most
    applications, QList is the best type to use. Although it is
    implemented as an array-list, it provides very fast prepends and
    appends. If you really need a linked-list, use QLinkedList; if you
    want your items to occupy consecutive memory locations, use QVector.
    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 \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