/****************************************************************************

**

** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).

** All rights reserved.

** Contact: Nokia Corporation (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 Technology Preview License Agreement accompanying

** this package.

**

** 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.1, included in the file LGPL_EXCEPTION.txt in this package.

**

** If you have questions regarding the use of this file, please contact

** Nokia at qt-info@nokia.com.

**

**

**

**

**

**

**

**

** $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 Generic Containers

    \ingroup frameworks-technologies

    \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 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

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