FCL/sf/mw/qt: comparison doc/src/frameworks-technologies/containers.qdoc

equal deleted inserted replaced

-:dee5afe5301f
+:3f74d0d4af4c
+/****************************************************************************
+**
+** Copyright (C) 2010 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
+\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 QContiguousCache<T> provides an efficient way of caching data
+that is typically accessed in a contiguous way.
+\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.
+*/

branch	RCL_3
changeset 8	3f74d0d4af4c