Update copyright headers
[qt:qt.git] / doc / src / frameworks-technologies / containers.qdoc
1 /****************************************************************************
2 **
3 ** Copyright (C) 2015 The Qt Company Ltd.
4 ** Contact: http://www.qt.io/licensing/
5 **
6 ** This file is part of the documentation of the Qt Toolkit.
7 **
8 ** $QT_BEGIN_LICENSE:FDL$
9 ** Commercial License Usage
10 ** Licensees holding valid commercial Qt licenses may use this file in
11 ** accordance with the commercial license agreement provided with the
12 ** Software or, alternatively, in accordance with the terms contained in
13 ** a written agreement between you and The Qt Company. For licensing terms
14 ** and conditions see http://www.qt.io/terms-conditions. For further
15 ** information use the contact form at http://www.qt.io/contact-us.
16 **
17 ** GNU Free Documentation License Usage
18 ** Alternatively, this file may be used under the terms of the GNU Free
19 ** Documentation License version 1.3 as published by the Free Software
20 ** Foundation and appearing in the file included in the packaging of
21 ** this file.  Please review the following information to ensure
22 ** the GNU Free Documentation License version 1.3 requirements
23 ** will be met: http://www.gnu.org/copyleft/fdl.html.
24 ** $QT_END_LICENSE$
25 **
26 ****************************************************************************/
27
28 /*!
29     \group tools
30     \title Non-GUI Classes
31     \ingroup groups
32
33     \brief Collection classes such as list, queue, stack and string, along
34     with other classes that can be used without needing QApplication.
35
36     The non-GUI classes are general-purpose collection and string classes
37     that may be used independently of the GUI classes.
38
39     In particular, these classes do not depend on QApplication at all,
40     and so can be used in non-GUI programs.
41
42 */
43
44 /*!
45     \page containers.html
46     \title Container Classes
47     \ingroup technology-apis
48     \ingroup groups
49     \ingroup qt-basic-concepts
50     \keyword container class
51     \keyword container classes
52
53     \brief Qt's template-based container classes.
54
55     \tableofcontents
56
57     \section1 Introduction
58
59     The Qt library provides a set of general purpose template-based
60     container classes. These classes can be used to store items of a
61     specified type. For example, if you need a resizable array of
62     \l{QString}s, use QVector<QString>.
63
64     These container classes are designed to be lighter, safer, and
65     easier to use than the STL containers. If you are unfamiliar with
66     the STL, or prefer to do things the "Qt way", you can use these
67     classes instead of the STL classes.
68
69     The container classes are \l{implicitly shared}, they are
70     \l{reentrant}, and they are optimized for speed, low memory
71     consumption, and minimal inline code expansion, resulting in
72     smaller executables. In addition, they are \l{thread-safe}
73     in situations where they are used as read-only containers
74     by all threads used to access them.
75
76     For traversing the items stored in a container, you can use one
77     of two types of iterators: \l{Java-style iterators} and
78     \l{STL-style iterators}. The Java-style iterators are easier to
79     use and provide high-level functionality, whereas the STL-style
80     iterators are slightly more efficient and can be used together
81     with Qt's and STL's \l{generic algorithms}.
82
83     Qt also offers a \l{foreach} keyword that make it very
84     easy to iterate over all the items stored in a container.
85
86     \section1 The Container Classes
87
88     Qt provides the following sequential containers: QList,
89     QLinkedList, QVector, QStack, and QQueue. For most
90     applications, QList is the best type to use. Although it is
91     implemented as an array-list, it provides very fast prepends and
92     appends. If you really need a linked-list, use QLinkedList; if you
93     want your items to occupy consecutive memory locations, use QVector.
94     QStack and QQueue are convenience classes that provide LIFO and
95     FIFO semantics.
96
97     Qt also provides these associative containers: QMap,
98     QMultiMap, QHash, QMultiHash, and QSet. The "Multi" containers
99     conveniently support multiple values associated with a single
100     key. The "Hash" containers provide faster lookup by using a hash
101     function instead of a binary search on a sorted set.
102
103     As special cases, the QCache and QContiguousCache classes provide
104     efficient hash-lookup of objects in a limited cache storage.
105
106     \table
107     \header \o Class \o Summary
108
109     \row \o \l{QList}<T>
110     \o This is by far the most commonly used container class. It
111     stores a list of values of a given type (T) that can be accessed
112     by index. Internally, the QList is implemented using an array,
113     ensuring that index-based access is very fast.
114
115     Items can be added at either end of the list using
116     QList::append() and QList::prepend(), or they can be inserted in
117     the middle using QList::insert(). More than any other container
118     class, QList is highly optimized to expand to as little code as
119     possible in the executable. QStringList inherits from
120     QList<QString>.
121
122     \row \o \l{QLinkedList}<T>
123     \o This is similar to QList, except that it uses
124     iterators rather than integer indexes to access items. It also
125     provides better performance than QList when inserting in the
126     middle of a huge list, and it has nicer iterator semantics.
127     (Iterators pointing to an item in a QLinkedList remain valid as
128     long as the item exists, whereas iterators to a QList can become
129     invalid after any insertion or removal.)
130
131     \row \o \l{QVector}<T>
132     \o This stores an array of values of a given type at adjacent
133     positions in memory. Inserting at the front or in the middle of
134     a vector can be quite slow, because it can lead to large numbers
135     of items having to be moved by one position in memory.
136
137     \row \o \l{QStack}<T>
138     \o This is a convenience subclass of QVector that provides
139     "last in, first out" (LIFO) semantics. It adds the following
140     functions to those already present in QVector:
141     \l{QStack::push()}{push()}, \l{QStack::pop()}{pop()},
142     and \l{QStack::top()}{top()}.
143
144     \row \o \l{QQueue}<T>
145     \o This is a convenience subclass of QList that provides
146     "first in, first out" (FIFO) semantics. It adds the following
147     functions to those already present in QList:
148     \l{QQueue::enqueue()}{enqueue()},
149     \l{QQueue::dequeue()}{dequeue()}, and \l{QQueue::head()}{head()}.
150
151     \row \o \l{QSet}<T>
152     \o This provides a single-valued mathematical set with fast
153     lookups.
154
155     \row \o \l{QMap}<Key, T>
156     \o This provides a dictionary (associative array) that maps keys
157     of type Key to values of type T. Normally each key is associated
158     with a single value. QMap stores its data in Key order; if order
159     doesn't matter QHash is a faster alternative.
160
161     \row \o \l{QMultiMap}<Key, T>
162     \o This is a convenience subclass of QMap that provides a nice
163     interface for multi-valued maps, i.e. maps where one key can be
164     associated with multiple values.
165
166     \row \o \l{QHash}<Key, T>
167     \o This has almost the same API as QMap, but provides
168     significantly faster lookups. QHash stores its data in an
169     arbitrary order.
170
171     \row \o \l{QMultiHash}<Key, T>
172     \o This is a convenience subclass of QHash that
173     provides a nice interface for multi-valued hashes.
174
175     \endtable
176
177     Containers can be nested. For example, it is perfectly possible
178     to use a QMap<QString, QList<int> >, where the key type is
179     QString and the value type QList<int>. The only pitfall is that
180     you must insert a space between the closing angle brackets (>);
181     otherwise the C++ compiler will misinterpret the two >'s as a
182     right-shift operator (>>) and report a syntax error.
183
184     The containers are defined in individual header files with the
185     same name as the container (e.g., \c <QLinkedList>). For
186     convenience, the containers are forward declared in \c
187     <QtContainerFwd>.
188
189     \keyword assignable data type
190     \keyword assignable data types
191
192     The values stored in the various containers can be of any
193     \e{assignable data type}. To qualify, a type must provide a
194     default constructor, a copy constructor, and an assignment
195     operator. This covers most data types you are likely to want to
196     store in a container, including basic types such as \c int and \c
197     double, pointer types, and Qt data types such as QString, QDate,
198     and QTime, but it doesn't cover QObject or any QObject subclass
199     (QWidget, QDialog, QTimer, etc.). If you attempt to instantiate a
200     QList<QWidget>, the compiler will complain that QWidget's copy
201     constructor and assignment operators are disabled. If you want to
202     store these kinds of objects in a container, store them as
203     pointers, for example as QList<QWidget *>.
204
205     Here's an example custom data type that meets the requirement of
206     an assignable data type:
207
208     \snippet doc/src/snippets/code/doc_src_containers.cpp 0
209
210     If we don't provide a copy constructor or an assignment operator,
211     C++ provides a default implementation that performs a
212     member-by-member copy. In the example above, that would have been
213     sufficient. Also, if you don't provide any constructors, C++
214     provides a default constructor that initializes its member using
215     default constructors. Although it doesn't provide any
216     explicit constructors or assignment operator, the following data
217     type can be stored in a container:
218
219     \snippet doc/src/snippets/streaming/main.cpp 0
220
221     Some containers have additional requirements for the data types
222     they can store. For example, the Key type of a QMap<Key, T> must
223     provide \c operator<(). Such special requirements are documented
224     in a class's detailed description. In some cases, specific
225     functions have special requirements; these are described on a
226     per-function basis. The compiler will always emit an error if a
227     requirement isn't met.
228
229     Qt's containers provide operator<<() and operator>>() so that they
230     can easily be read and written using a QDataStream. This means
231     that the data types stored in the container must also support
232     operator<<() and operator>>(). Providing such support is
233     straightforward; here's how we could do it for the Movie struct
234     above:
235
236     \snippet doc/src/snippets/streaming/main.cpp 1
237     \codeline
238     \snippet doc/src/snippets/streaming/main.cpp 2
239
240     \keyword default-constructed values
241
242     The documentation of certain container class functions refer to
243     \e{default-constructed values}; for example, QVector
244     automatically initializes its items with default-constructed
245     values, and QMap::value() returns a default-constructed value if
246     the specified key isn't in the map. For most value types, this
247     simply means that a value is created using the default
248     constructor (e.g. an empty string for QString). But for primitive
249     types like \c{int} and \c{double}, as well as for pointer types,
250     the C++ language doesn't specify any initialization; in those
251     cases, Qt's containers automatically initialize the value to 0.
252
253     \section1 The Iterator Classes
254
255     Iterators provide a uniform means to access items in a container.
256     Qt's container classes provide two types of iterators: Java-style
257     iterators and STL-style iterators. Iterators of both types are
258     invalidated when the data in the container is modified or detached
259     from \l{Implicit Sharing}{implicitly shared copies} due to a call
260     to a non-const member function.
261
262     \section2 Java-Style Iterators
263
264     The Java-style iterators are new in Qt 4 and are the standard
265     ones used in Qt applications. They are more convenient to use than
266     the STL-style iterators, at the price of being slightly less
267     efficient. Their API is modelled on Java's iterator classes.
268
269     For each container class, there are two Java-style iterator data
270     types: one that provides read-only access and one that provides
271     read-write access.
272
273     \table
274     \header \o Containers                         \o Read-only iterator
275                                                   \o Read-write iterator
276     \row    \o QList<T>, QQueue<T>                \o QListIterator<T>
277                                                   \o QMutableListIterator<T>
278     \row    \o QLinkedList<T>                     \o QLinkedListIterator<T>
279                                                   \o QMutableLinkedListIterator<T>
280     \row    \o QVector<T>, QStack<T>              \o QVectorIterator<T>
281                                                   \o QMutableVectorIterator<T>
282     \row    \o QSet<T>                            \o QSetIterator<T>
283                                                   \o QMutableSetIterator<T>
284     \row    \o QMap<Key, T>, QMultiMap<Key, T>    \o QMapIterator<Key, T>
285                                                   \o QMutableMapIterator<Key, T>
286     \row    \o QHash<Key, T>, QMultiHash<Key, T>  \o QHashIterator<Key, T>
287                                                   \o QMutableHashIterator<Key, T>
288     \endtable
289
290     In this discussion, we will concentrate on QList and QMap. The
291     iterator types for QLinkedList, QVector, and QSet have exactly
292     the same interface as QList's iterators; similarly, the iterator
293     types for QHash have the same interface as QMap's iterators.
294
295     Unlike STL-style iterators (covered \l{STL-style
296     iterators}{below}), Java-style iterators point \e between items
297     rather than directly \e at items. For this reason, they are
298     either pointing to the very beginning of the container (before
299     the first item), at the very end of the container (after the last
300     item), or between two items. The diagram below shows the valid
301     iterator positions as red arrows for a list containing four
302     items:
303
304     \img javaiterators1.png
305
306     Here's a typical loop for iterating through all the elements of a
307     QList<QString> in order and printing them to the console:
308
309     \snippet doc/src/snippets/code/doc_src_containers.cpp 1
310
311     It works as follows: The QList to iterate over is passed to the
312     QListIterator constructor. At that point, the iterator is located
313     just in front of the first item in the list (before item "A").
314     Then we call \l{QListIterator::hasNext()}{hasNext()} to
315     check whether there is an item after the iterator. If there is, we
316     call \l{QListIterator::next()}{next()} to jump over that
317     item. The next() function returns the item that it jumps over. For
318     a QList<QString>, that item is of type QString.
319
320     Here's how to iterate backward in a QList:
321
322     \snippet doc/src/snippets/code/doc_src_containers.cpp 2
323
324     The code is symmetric with iterating forward, except that we
325     start by calling \l{QListIterator::toBack()}{toBack()}
326     to move the iterator after the last item in the list.
327
328     The diagram below illustrates the effect of calling
329     \l{QListIterator::next()}{next()} and
330     \l{QListIterator::previous()}{previous()} on an iterator:
331
332     \img javaiterators2.png
333
334     The following table summarizes the QListIterator API:
335
336     \table
337     \header \o Function \o Behavior
338     \row    \o \l{QListIterator::toFront()}{toFront()}
339             \o Moves the iterator to the front of the list (before the first item)
340     \row    \o \l{QListIterator::toBack()}{toBack()}
341             \o Moves the iterator to the back of the list (after the last item)
342     \row    \o \l{QListIterator::hasNext()}{hasNext()}
343             \o Returns true if the iterator isn't at the back of the list
344     \row    \o \l{QListIterator::next()}{next()}
345             \o Returns the next item and advances the iterator by one position
346     \row    \o \l{QListIterator::peekNext()}{peekNext()}
347             \o Returns the next item without moving the iterator
348     \row    \o \l{QListIterator::hasPrevious()}{hasPrevious()}
349             \o Returns true if the iterator isn't at the front of the list
350     \row    \o \l{QListIterator::previous()}{previous()}
351             \o Returns the previous item and moves the iterator back by one position
352     \row    \o \l{QListIterator::peekPrevious()}{peekPrevious()}
353             \o Returns the previous item without moving the iterator
354     \endtable
355
356     QListIterator provides no functions to insert or remove items
357     from the list as we iterate. To accomplish this, you must use
358     QMutableListIterator. Here's an example where we remove all
359     odd numbers from a QList<int> using QMutableListIterator:
360
361     \snippet doc/src/snippets/code/doc_src_containers.cpp 3
362
363     The next() call in the loop is made every time. It jumps over the
364     next item in the list. The
365     \l{QMutableListIterator::remove()}{remove()} function removes the
366     last item that we jumped over from the list. The call to
367     \l{QMutableListIterator::remove()}{remove()} does not invalidate
368     the iterator, so it is safe to continue using it. This works just
369     as well when iterating backward:
370
371     \snippet doc/src/snippets/code/doc_src_containers.cpp 4
372
373     If we just want to modify the value of an existing item, we can
374     use \l{QMutableListIterator::setValue()}{setValue()}. In the code
375     below, we replace any value larger than 128 with 128:
376
377     \snippet doc/src/snippets/code/doc_src_containers.cpp 5
378
379     Just like \l{QMutableListIterator::remove()}{remove()},
380     \l{QMutableListIterator::setValue()}{setValue()} operates on the
381     last item that we jumped over. If we iterate forward, this is the
382     item just before the iterator; if we iterate backward, this is
383     the item just after the iterator.
384
385     The \l{QMutableListIterator::next()}{next()} function returns a
386     non-const reference to the item in the list. For simple
387     operations, we don't even need
388     \l{QMutableListIterator::setValue()}{setValue()}:
389
390     \snippet doc/src/snippets/code/doc_src_containers.cpp 6
391
392     As mentioned above, QLinkedList's, QVector's, and QSet's iterator
393     classes have exactly the same API as QList's. We will now turn to
394     QMapIterator, which is somewhat different because it iterates on
395     (key, value) pairs.
396
397     Like QListIterator, QMapIterator provides 
398     \l{QMapIterator::toFront()}{toFront()}, 
399     \l{QMapIterator::toBack()}{toBack()}, 
400     \l{QMapIterator::hasNext()}{hasNext()}, 
401     \l{QMapIterator::next()}{next()}, 
402     \l{QMapIterator::peekNext()}{peekNext()}, 
403     \l{QMapIterator::hasPrevious()}{hasPrevious()}, 
404     \l{QMapIterator::previous()}{previous()}, and
405     \l{QMapIterator::peekPrevious()}{peekPrevious()}. The key and
406     value components are extracted by calling key() and value() on
407     the object returned by next(), peekNext(), previous(), or
408     peekPrevious().
409
410     The following example removes all (capital, country) pairs where
411     the capital's name ends with "City":
412
413     \snippet doc/src/snippets/code/doc_src_containers.cpp 7
414
415     QMapIterator also provides a key() and a value() function that
416     operate directly on the iterator and that return the key and
417     value of the last item that the iterator jumped above. For
418     example, the following code copies the contents of a QMap into a
419     QHash:
420
421     \snippet doc/src/snippets/code/doc_src_containers.cpp 8
422
423     If we want to iterate through all the items with the same
424     value, we can use \l{QMapIterator::findNext()}{findNext()}
425     or \l{QMapIterator::findPrevious()}{findPrevious()}.
426     Here's an example where we remove all the items with a particular
427     value:
428
429     \snippet doc/src/snippets/code/doc_src_containers.cpp 9
430
431     \section2 STL-Style Iterators
432
433     STL-style iterators have been available since the release of Qt
434     2.0. They are compatible with Qt's and STL's \l{generic
435     algorithms} and are optimized for speed.
436
437     For each container class, there are two STL-style iterator types:
438     one that provides read-only access and one that provides
439     read-write access. Read-only iterators should be used wherever
440     possible because they are faster than read-write iterators.
441
442     \table
443     \header \o Containers                         \o Read-only iterator
444                                                   \o Read-write iterator
445     \row    \o QList<T>, QQueue<T>                \o QList<T>::const_iterator
446                                                   \o QList<T>::iterator
447     \row    \o QLinkedList<T>                     \o QLinkedList<T>::const_iterator
448                                                   \o QLinkedList<T>::iterator
449     \row    \o QVector<T>, QStack<T>              \o QVector<T>::const_iterator
450                                                   \o QVector<T>::iterator
451     \row    \o QSet<T>                            \o QSet<T>::const_iterator
452                                                   \o QSet<T>::iterator
453     \row    \o QMap<Key, T>, QMultiMap<Key, T>    \o QMap<Key, T>::const_iterator
454                                                   \o QMap<Key, T>::iterator
455     \row    \o QHash<Key, T>, QMultiHash<Key, T>  \o QHash<Key, T>::const_iterator
456                                                   \o QHash<Key, T>::iterator
457     \endtable
458
459     The API of the STL iterators is modelled on pointers in an array.
460     For example, the \c ++ operator advances the iterator to the next
461     item, and the \c * operator returns the item that the iterator
462     points to. In fact, for QVector and QStack, which store their
463     items at adjacent memory positions, the
464     \l{QVector::iterator}{iterator} type is just a typedef for \c{T *},
465     and the \l{QVector::iterator}{const_iterator} type is
466     just a typedef for \c{const T *}.
467
468     In this discussion, we will concentrate on QList and QMap. The
469     iterator types for QLinkedList, QVector, and QSet have exactly
470     the same interface as QList's iterators; similarly, the iterator
471     types for QHash have the same interface as QMap's iterators.
472
473     Here's a typical loop for iterating through all the elements of a
474     QList<QString> in order and converting them to lowercase:
475
476     \snippet doc/src/snippets/code/doc_src_containers.cpp 10
477
478     Unlike \l{Java-style iterators}, STL-style iterators point
479     directly at items. The begin() function of a container returns an
480     iterator that points to the first item in the container. The
481     end() function of a container returns an iterator to the
482     imaginary item one position past the last item in the container.
483     end() marks an invalid position; it must never be dereferenced.
484     It is typically used in a loop's break condition. If the list is
485     empty, begin() equals end(), so we never execute the loop.
486
487     The diagram below shows the valid iterator positions as red
488     arrows for a vector containing four items:
489
490     \img stliterators1.png
491
492     Iterating backward with an STL-style iterator requires us to
493     decrement the iterator \e before we access the item. This
494     requires a \c while loop:
495
496     \snippet doc/src/snippets/code/doc_src_containers.cpp 11
497
498     In the code snippets so far, we used the unary \c * operator to
499     retrieve the item (of type QString) stored at a certain iterator
500     position, and we then called QString::toLower() on it. Most C++
501     compilers also allow us to write \c{i->toLower()}, but some
502     don't.
503
504     For read-only access, you can use const_iterator, constBegin(),
505     and constEnd(). For example:
506
507     \snippet doc/src/snippets/code/doc_src_containers.cpp 12
508
509     The following table summarizes the STL-style iterators' API:
510
511     \table
512     \header \o Expression \o Behavior
513     \row    \o \c{*i}     \o Returns the current item
514     \row    \o \c{++i}    \o Advances the iterator to the next item
515     \row    \o \c{i += n} \o Advances the iterator by \c n items
516     \row    \o \c{--i}    \o Moves the iterator back by one item
517     \row    \o \c{i -= n} \o Moves the iterator back by \c n items
518     \row    \o \c{i - j}  \o Returns the number of items between iterators \c i and \c j
519     \endtable
520
521     The \c{++} and \c{--} operators are available both as prefix
522     (\c{++i}, \c{--i}) and postfix (\c{i++}, \c{i--}) operators. The
523     prefix versions modify the iterators and return a reference to
524     the modified iterator; the postfix versions take a copy of the
525     iterator before they modify it, and return that copy. In
526     expressions where the return value is ignored, we recommend that
527     you use the prefix operators (\c{++i}, \c{--i}), as these are
528     slightly faster.
529
530     For non-const iterator types, the return value of the unary \c{*}
531     operator can be used on the left side of the assignment operator.
532
533     For QMap and QHash, the \c{*} operator returns the value
534     component of an item. If you want to retrieve the key, call key()
535     on the iterator. For symmetry, the iterator types also provide a
536     value() function to retrieve the value. For example, here's how
537     we would print all items in a QMap to the console:
538
539     \snippet doc/src/snippets/code/doc_src_containers.cpp 13
540
541     Thanks to \l{implicit sharing}, it is very inexpensive for a
542     function to return a container per value. The Qt API contains
543     dozens of functions that return a QList or QStringList per value
544     (e.g., QSplitter::sizes()). If you want to iterate over these
545     using an STL iterator, you should always take a copy of the
546     container and iterate over the copy. For example:
547
548     \snippet doc/src/snippets/code/doc_src_containers.cpp 14
549
550     This problem doesn't occur with functions that return a const or
551     non-const reference to a container.
552
553     \l{Implicit sharing} has another consequence on STL-style
554     iterators: You must not take a copy of a container while
555     non-const iterators are active on that container. Java-style
556     iterators don't suffer from that limitation.
557
558     \keyword foreach
559     \section1 The foreach Keyword
560
561     If you just want to iterate over all the items in a container
562     in order, you can use Qt's \c foreach keyword. The keyword is a
563     Qt-specific addition to the C++ language, and is implemented
564     using the preprocessor.
565
566     Its syntax is: \c foreach (\e variable, \e container) \e
567     statement. For example, here's how to use \c foreach to iterate
568     over a QLinkedList<QString>:
569
570     \snippet doc/src/snippets/code/doc_src_containers.cpp 15
571
572     The \c foreach code is significantly shorter than the equivalent
573     code that uses iterators:
574
575     \snippet doc/src/snippets/code/doc_src_containers.cpp 16
576
577     Unless the data type contains a comma (e.g., \c{QPair<int,
578     int>}), the variable used for iteration can be defined within the
579     \c foreach statement:
580
581     \snippet doc/src/snippets/code/doc_src_containers.cpp 17
582
583     And like any other C++ loop construct, you can use braces around
584     the body of a \c foreach loop, and you can use \c break to leave
585     the loop:
586
587     \snippet doc/src/snippets/code/doc_src_containers.cpp 18
588
589     With QMap and QHash, \c foreach accesses the value component of
590     the (key, value) pairs. If you want to iterate over both the keys
591     and the values, you can use iterators (which are fastest), or you
592     can write code like this:
593
594     \snippet doc/src/snippets/code/doc_src_containers.cpp 19
595
596     For a multi-valued map:
597
598     \snippet doc/src/snippets/code/doc_src_containers.cpp 20
599
600     Qt automatically takes a copy of the container when it enters a
601     \c foreach loop. If you modify the container as you are
602     iterating, that won't affect the loop. (If you do not modify the
603     container, the copy still takes place, but thanks to \l{implicit
604     sharing} copying a container is very fast.)
605
606     Since foreach creates a copy of the container, using a non-const
607     reference for the variable does not allow you to modify the original
608     container. It only affects the copy, which is probably not what you
609     want.
610
611     In addition to \c foreach, Qt also provides a \c forever
612     pseudo-keyword for infinite loops:
613
614     \snippet doc/src/snippets/code/doc_src_containers.cpp 21
615
616     If you're worried about namespace pollution, you can disable
617     these macros by adding the following line to your \c .pro file:
618
619     \snippet doc/src/snippets/code/doc_src_containers.cpp 22
620
621     \section1 Other Container-Like Classes
622
623     Qt includes three template classes that resemble containers in
624     some respects. These classes don't provide iterators and cannot
625     be used with the \c foreach keyword.
626
627     \list
628     \o QVarLengthArray<T, Prealloc> provides a low-level
629        variable-length array. It can be used instead of QVector in
630        places where speed is particularly important.
631
632     \o QCache<Key, T> provides a cache to store objects of a certain
633        type T associated with keys of type Key.
634
635     \o QContiguousCache<T> provides an efficient way of caching data
636     that is typically accessed in a contiguous way.
637
638     \o QPair<T1, T2> stores a pair of elements.
639     \endlist
640
641     Additional non-template types that compete with Qt's template
642     containers are QBitArray, QByteArray, QString, and QStringList.
643
644     \section1 Algorithmic Complexity
645
646     Algorithmic complexity is concerned about how fast (or slow) each
647     function is as the number of items in the container grow. For
648     example, inserting an item in the middle of a QLinkedList is an
649     extremely fast operation, irrespective of the number of items
650     stored in the QLinkedList. On the other hand, inserting an item
651     in the middle of a QVector is potentially very expensive if the
652     QVector contains many items, since half of the items must be
653     moved one position in memory.
654
655     To describe algorithmic complexity, we use the following
656     terminology, based on the "big Oh" notation:
657
658     \keyword constant time
659     \keyword logarithmic time
660     \keyword linear time
661     \keyword linear-logarithmic time
662     \keyword quadratic time
663
664     \list
665     \o \bold{Constant time:} O(1). A function is said to run in constant
666        time if it requires the same amount of time no matter how many
667        items are present in the container. One example is
668        QLinkedList::insert().
669
670     \o \bold{Logarithmic time:} O(log \e n). A function that runs in
671        logarithmic time is a function whose running time is
672        proportional to the logarithm of the number of items in the
673        container. One example is qBinaryFind().
674
675     \o \bold{Linear time:} O(\e n). A function that runs in linear time
676        will execute in a time directly proportional to the number of
677        items stored in the container. One example is
678        QVector::insert().
679
680     \o \bold{Linear-logarithmic time:} O(\e{n} log \e n). A function
681        that runs in linear-logarithmic time is asymptotically slower
682        than a linear-time function, but faster than a quadratic-time
683        function.
684
685     \o \bold{Quadratic time:} O(\e{n}\unicode{178}). A quadratic-time function
686        executes in a time that is proportional to the square of the
687        number of items stored in the container.
688     \endlist
689
690     The following table summarizes the algorithmic complexity of Qt's
691     sequential container classes:
692
693     \table
694     \header \o                \o Index lookup \o Insertion \o Prepending         \o Appending
695     \row    \o QLinkedList<T> \o O(\e n)      \o O(1)      \o O(1)               \o O(1)
696     \row    \o QList<T>       \o O(1)         \o O(n)      \o Amort. O(1)        \o Amort. O(1)
697     \row    \o QVector<T>     \o O(1)         \o O(n)      \o O(n)               \o Amort. O(1)
698     \endtable
699
700     In the table, "Amort." stands for "amortized behavior". For
701     example, "Amort. O(1)" means that if you call the function
702     only once, you might get O(\e n) behavior, but if you call it
703     multiple times (e.g., \e n times), the average behavior will be
704     O(1).
705
706     The following table summarizes the algorithmic complexity of Qt's
707     associative containers and sets:
708
709     \table
710     \header \o{1,2}          \o{2,1} Key lookup            \o{2,1} Insertion
711     \header                  \o Average     \o Worst case  \o Average            \o Worst case
712     \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)
713     \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)
714     \row    \o QHash<Key, T> \o Amort. O(1) \o O(\e n)     \o Amort. O(1)        \o O(\e n)
715     \row    \o QSet<Key>     \o Amort. O(1) \o O(\e n)     \o Amort. O(1)        \o O(\e n)
716     \endtable
717
718     With QVector, QHash, and QSet, the performance of appending items
719     is amortized O(log \e n). It can be brought down to O(1) by
720     calling QVector::reserve(), QHash::reserve(), or QSet::reserve()
721     with the expected number of items before you insert the items.
722     The next section discusses this topic in more depth.
723
724     \section1 Growth Strategies
725
726     QVector<T>, QString, and QByteArray store their items
727     contiguously in memory; QList<T> maintains an array of pointers
728     to the items it stores to provide fast index-based access (unless
729     T is a pointer type or a basic type of the size of a pointer, in
730     which case the value itself is stored in the array); QHash<Key,
731     T> keeps a hash table whose size is proportional to the number
732     of items in the hash. To avoid reallocating the data every single
733     time an item is added at the end of the container, these classes
734     typically allocate more memory than necessary.
735
736     Consider the following code, which builds a QString from another
737     QString:
738
739     \snippet doc/src/snippets/code/doc_src_containers.cpp 23
740
741     We build the string \c out dynamically by appending one character
742     to it at a time. Let's assume that we append 15000 characters to
743     the QString string. Then the following 18 reallocations (out of a
744     possible 15000) occur when QString runs out of space: 4, 8, 12,
745     16, 20, 52, 116, 244, 500, 1012, 2036, 4084, 6132, 8180, 10228,
746     12276, 14324, 16372. At the end, the QString has 16372 Unicode
747     characters allocated, 15000 of which are occupied.
748
749     The values above may seem a bit strange, but here are the guiding
750     principles:
751     \list
752     \o QString allocates 4 characters at a time until it reaches size 20.
753     \o From 20 to 4084, it advances by doubling the size each time.
754        More precisely, it advances to the next power of two, minus
755        12. (Some memory allocators perform worst when requested exact
756        powers of two, because they use a few bytes per block for
757        book-keeping.)
758     \o From 4084 on, it advances by blocks of 2048 characters (4096
759        bytes). This makes sense because modern operating systems
760        don't copy the entire data when reallocating a buffer; the
761        physical memory pages are simply reordered, and only the data
762        on the first and last pages actually needs to be copied.
763     \endlist
764
765     QByteArray and QList<T> use more or less the same algorithm as
766     QString.
767
768     QVector<T> also uses that algorithm for data types that can be
769     moved around in memory using memcpy() (including the basic C++
770     types, the pointer types, and Qt's \l{shared classes}) but uses a
771     different algorithm for data types that can only be moved by
772     calling the copy constructor and a destructor. Since the cost of
773     reallocating is higher in that case, QVector<T> reduces the
774     number of reallocations by always doubling the memory when
775     running out of space.
776
777     QHash<Key, T> is a totally different case. QHash's internal hash
778     table grows by powers of two, and each time it grows, the items
779     are relocated in a new bucket, computed as qHash(\e key) %
780     QHash::capacity() (the number of buckets). This remark applies to
781     QSet<T> and QCache<Key, T> as well.
782
783     For most applications, the default growing algorithm provided by
784     Qt does the trick. If you need more control, QVector<T>,
785     QHash<Key, T>, QSet<T>, QString, and QByteArray provide a trio of
786     functions that allow you to check and specify how much memory to
787     use to store the items:
788
789     \list
790     \o \l{QString::capacity()}{capacity()} returns the
791        number of items for which memory is allocated (for QHash and
792        QSet, the number of buckets in the hash table).
793     \o \l{QString::reserve()}{reserve}(\e size) explicitly
794        preallocates memory for \e size items.
795     \o \l{QString::squeeze()}{squeeze()} frees any memory
796        not required to store the items.
797     \endlist
798
799     If you know approximately how many items you will store in a
800     container, you can start by calling reserve(), and when you are
801     done populating the container, you can call squeeze() to release
802     the extra preallocated memory.
803 */