diff options
Diffstat (limited to 'doc/src/frameworks-technologies/containers.qdoc')
| -rw-r--r-- | doc/src/frameworks-technologies/containers.qdoc | 810 |
1 files changed, 810 insertions, 0 deletions
diff --git a/doc/src/frameworks-technologies/containers.qdoc b/doc/src/frameworks-technologies/containers.qdoc new file mode 100644 index 0000000..be3e3eb --- /dev/null +++ b/doc/src/frameworks-technologies/containers.qdoc @@ -0,0 +1,810 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** 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. + + \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. +*/ |