1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GFDL-1.3-no-invariants-only
6 \title Container Classes
8 \ingroup qt-basic-concepts
9 \keyword container class
10 \keyword container classes
12 \brief Qt's template-based container classes.
16 \section1 Introduction
18 The Qt library provides a set of general purpose template-based
19 container classes. These classes can be used to store items of a
20 specified type. For example, if you need a resizable array of
21 \l{QString}s, use QList<QString>.
23 These container classes are designed to be lighter, safer, and
24 easier to use than the STL containers. If you are unfamiliar with
25 the STL, or prefer to do things the "Qt way", you can use these
26 classes instead of the STL classes.
28 The container classes are \l{implicitly shared}, they are
29 \l{reentrant}, and they are optimized for speed, low memory
30 consumption, and minimal inline code expansion, resulting in
31 smaller executables. In addition, they are \l{thread-safe}
32 in situations where they are used as read-only containers
33 by all threads used to access them.
35 The containers provide iterators for traversal. \l{STL-style iterators}
36 are the most efficient ones and can be used together with Qt's and
37 STL's \l{generic algorithms}.
38 \l{Java-style Iterators} are provided for backwards compatibility.
40 \note Since Qt 5.14, range constructors are available for most of the
41 container classes. QMultiMap is a notable exception. Their use is
42 encouraged to replace of the various deprecated from/to methods of Qt 5.
45 \snippet code/doc_src_containers.cpp 25
47 \section1 The Container Classes
49 Qt provides the following sequential containers: QList,
50 QStack, and QQueue. For most
51 applications, QList is the best type to use. It provides very fast
52 appends. If you really need a linked-list, use std::list.
53 QStack and QQueue are convenience classes that provide LIFO and
56 Qt also provides these associative containers: QMap,
57 QMultiMap, QHash, QMultiHash, and QSet. The "Multi" containers
58 conveniently support multiple values associated with a single
59 key. The "Hash" containers provide faster lookup by using a hash
60 function instead of a binary search on a sorted set.
62 As special cases, the QCache and QContiguousCache classes provide
63 efficient hash-lookup of objects in a limited cache storage.
66 \header \li Class \li Summary
69 \li This is by far the most commonly used container class. It
70 stores a list of values of a given type (T) that can be accessed
71 by index. Internally, it stores an array of values of a
72 given type at adjacent
73 positions in memory. Inserting at the front or in the middle of
74 a list can be quite slow, because it can lead to large numbers
75 of items having to be moved by one position in memory.
77 \row \li \l{QVarLengthArray}<T, Prealloc>
78 \li This provides a low-level variable-length array. It can be used
79 instead of QList in places where speed is particularly important.
81 \row \li \l{QStack}<T>
82 \li This is a convenience subclass of QList that provides
83 "last in, first out" (LIFO) semantics. It adds the following
84 functions to those already present in QList:
85 \l{QStack::push()}{push()}, \l{QStack::pop()}{pop()},
86 and \l{QStack::top()}{top()}.
88 \row \li \l{QQueue}<T>
89 \li This is a convenience subclass of QList that provides
90 "first in, first out" (FIFO) semantics. It adds the following
91 functions to those already present in QList:
92 \l{QQueue::enqueue()}{enqueue()},
93 \l{QQueue::dequeue()}{dequeue()}, and \l{QQueue::head()}{head()}.
96 \li This provides a single-valued mathematical set with fast
99 \row \li \l{QMap}<Key, T>
100 \li This provides a dictionary (associative array) that maps keys
101 of type Key to values of type T. Normally each key is associated
102 with a single value. QMap stores its data in Key order; if order
103 doesn't matter QHash is a faster alternative.
105 \row \li \l{QMultiMap}<Key, T>
106 \li This is a convenience subclass of QMap that provides a nice
107 interface for multi-valued maps, i.e. maps where one key can be
108 associated with multiple values.
110 \row \li \l{QHash}<Key, T>
111 \li This has almost the same API as QMap, but provides
112 significantly faster lookups. QHash stores its data in an
115 \row \li \l{QMultiHash}<Key, T>
116 \li This is a convenience subclass of QHash that
117 provides a nice interface for multi-valued hashes.
121 Containers can be nested. For example, it is perfectly possible
122 to use a QMap<QString, QList<int>>, where the key type is
123 QString and the value type QList<int>.
125 The containers are defined in individual header files with the
126 same name as the container (e.g., \c <QList>). For
127 convenience, the containers are forward declared in \c
130 \target assignable data type
131 \target assignable data types
133 The values stored in the various containers can be of any
134 \e{assignable data type}. To qualify, a type must provide a
135 copy constructor, and an assignment operator. For some
136 operations a default constructor is also required. This
137 covers most data types you are likely to want to
138 store in a container, including basic types such as \c int and \c
139 double, pointer types, and Qt data types such as QString, QDate,
140 and QTime, but it doesn't cover QObject or any QObject subclass
141 (QWidget, QDialog, QTimer, etc.). If you attempt to instantiate a
142 QList<QWidget>, the compiler will complain that QWidget's copy
143 constructor and assignment operators are disabled. If you want to
144 store these kinds of objects in a container, store them as
145 pointers, for example as QList<QWidget *>.
147 Here's an example custom data type that meets the requirement of
148 an assignable data type:
150 \snippet code/doc_src_containers.cpp 0
152 If we don't provide a copy constructor or an assignment operator,
153 C++ provides a default implementation that performs a
154 member-by-member copy. In the example above, that would have been
155 sufficient. Also, if you don't provide any constructors, C++
156 provides a default constructor that initializes its member using
157 default constructors. Although it doesn't provide any
158 explicit constructors or assignment operator, the following data
159 type can be stored in a container:
161 \snippet streaming/main.cpp 0
163 Some containers have additional requirements for the data types
164 they can store. For example, the Key type of a QMap<Key, T> must
165 provide \c operator<(). Such special requirements are documented
166 in a class's detailed description. In some cases, specific
167 functions have special requirements; these are described on a
168 per-function basis. The compiler will always emit an error if a
169 requirement isn't met.
171 Qt's containers provide operator<<() and operator>>() so that they
172 can easily be read and written using a QDataStream. This means
173 that the data types stored in the container must also support
174 operator<<() and operator>>(). Providing such support is
175 straightforward; here's how we could do it for the Movie struct
178 \snippet streaming/main.cpp 1
180 \snippet streaming/main.cpp 2
182 \target default-constructed value
184 The documentation of certain container class functions refer to
185 \e{default-constructed values}; for example, QList
186 automatically initializes its items with default-constructed
187 values, and QMap::value() returns a default-constructed value if
188 the specified key isn't in the map. For most value types, this
189 simply means that a value is created using the default
190 constructor (e.g. an empty string for QString). But for primitive
191 types like \c{int} and \c{double}, as well as for pointer types,
192 the C++ language doesn't specify any initialization; in those
193 cases, Qt's containers automatically initialize the value to 0.
195 \section1 Iterating over Containers
197 \section2 Range-based for
199 Range-based \c for should preferably be used for containers:
201 \snippet code/doc_src_containers.cpp range_for
203 Note that when using a Qt container in a non-const context,
204 \l{implicit sharing} may perform an undesired detach of the container.
205 To prevent this, use \c std::as_const():
207 \snippet code/doc_src_containers.cpp range_for_as_const
209 For associative containers, this will loop over the values.
211 \section2 Index-based
213 For sequential containers that store their items contiguously in memory
214 (for example, QList), index-based iteration can be used:
216 \snippet code/doc_src_containers.cpp index
218 \section2 The Iterator Classes
220 Iterators provide a uniform means to access items in a container.
221 Qt's container classes provide two types of iterators: STL-style
222 iterators and Java-style iterators. Iterators of both types are
223 invalidated when the data in the container is modified or detached
224 from \l{Implicit Sharing}{implicitly shared copies} due to a call
225 to a non-const member function.
227 \section3 STL-Style Iterators
229 STL-style iterators have been available since the release of Qt
230 2.0. They are compatible with Qt's and STL's \l{generic
231 algorithms} and are optimized for speed.
233 For each container class, there are two STL-style iterator types:
234 one that provides read-only access and one that provides
235 read-write access. Read-only iterators should be used wherever
236 possible because they are faster than read-write iterators.
239 \header \li Containers \li Read-only iterator
240 \li Read-write iterator
241 \row \li QList<T>, QStack<T>, QQueue<T> \li QList<T>::const_iterator
242 \li QList<T>::iterator
243 \row \li QSet<T> \li QSet<T>::const_iterator
244 \li QSet<T>::iterator
245 \row \li QMap<Key, T>, QMultiMap<Key, T> \li QMap<Key, T>::const_iterator
246 \li QMap<Key, T>::iterator
247 \row \li QHash<Key, T>, QMultiHash<Key, T> \li QHash<Key, T>::const_iterator
248 \li QHash<Key, T>::iterator
251 The API of the STL iterators is modelled on pointers in an array.
252 For example, the \c ++ operator advances the iterator to the next
253 item, and the \c * operator returns the item that the iterator
254 points to. In fact, for QList and QStack, which store their
255 items at adjacent memory positions, the
256 \l{QList::iterator}{iterator} type is just a typedef for \c{T *},
257 and the \l{QList::iterator}{const_iterator} type is
258 just a typedef for \c{const T *}.
260 In this discussion, we will concentrate on QList and QMap. The
261 iterator types for QSet have exactly
262 the same interface as QList's iterators; similarly, the iterator
263 types for QHash have the same interface as QMap's iterators.
265 Here's a typical loop for iterating through all the elements of a
266 QList<QString> in order and converting them to lowercase:
268 \snippet code/doc_src_containers.cpp 10
270 STL-style iterators point directly at items. The \l{QList::begin()}{begin()}
271 function of a container returns an iterator that points to the first item in the
272 container. The \l{QList::end()}{end()} function of a container returns an iterator to the
273 imaginary item one position past the last item in the container.
274 \l {QList::end()}{end()} marks an invalid position; it must never be dereferenced.
275 It is typically used in a loop's break condition. If the list is
276 empty, \l{QList::begin}{begin()} equals \l{QList::end()}{end()}, so we never execute the loop.
278 The diagram below shows the valid iterator positions as red
279 arrows for a list containing four items:
281 \image stliterators1.png
283 Iterating backward with an STL-style iterator is done with reverse iterators:
285 \snippet code/doc_src_containers.cpp 11
287 In the code snippets so far, we used the unary \c * operator to
288 retrieve the item (of type QString) stored at a certain iterator
289 position, and we then called QString::toLower() on it.
291 For read-only access, you can use const_iterator, \l{QList::cbegin}{cbegin()},
292 and \l{QList::cend()}{cend()}. For example:
294 \snippet code/doc_src_containers.cpp 12
296 The following table summarizes the STL-style iterators' API:
299 \header \li Expression \li Behavior
300 \row \li \c{*i} \li Returns the current item
301 \row \li \c{++i} \li Advances the iterator to the next item
302 \row \li \c{i += n} \li Advances the iterator by \c n items
303 \row \li \c{--i} \li Moves the iterator back by one item
304 \row \li \c{i -= n} \li Moves the iterator back by \c n items
305 \row \li \c{i - j} \li Returns the number of items between iterators \c i and \c j
308 The \c{++} and \c{--} operators are available both as prefix
309 (\c{++i}, \c{--i}) and postfix (\c{i++}, \c{i--}) operators. The
310 prefix versions modify the iterators and return a reference to
311 the modified iterator; the postfix versions take a copy of the
312 iterator before they modify it, and return that copy. In
313 expressions where the return value is ignored, we recommend that
314 you use the prefix operators (\c{++i}, \c{--i}), as these are
317 For non-const iterator types, the return value of the unary \c{*}
318 operator can be used on the left side of the assignment operator.
320 For QMap and QHash, the \c{*} operator returns the value
321 component of an item. If you want to retrieve the key, call key()
322 on the iterator. For symmetry, the iterator types also provide a
323 value() function to retrieve the value. For example, here's how
324 we would print all items in a QMap to the console:
326 \snippet code/doc_src_containers.cpp 13
328 Thanks to \l{implicit sharing}, it is very inexpensive for a
329 function to return a container per value. The Qt API contains
330 dozens of functions that return a QList or QStringList per value
331 (e.g., QSplitter::sizes()). If you want to iterate over these
332 using an STL iterator, you should always take a copy of the
333 container and iterate over the copy. For example:
335 \snippet code/doc_src_containers.cpp 14
337 This problem doesn't occur with functions that return a const or
338 non-const reference to a container.
340 \section4 Implicit sharing iterator problem
342 \l{Implicit sharing} has another consequence on STL-style
343 iterators: you should avoid copying a container while
344 iterators are active on that container. The iterators
345 point to an internal structure, and if you copy a container
346 you should be very careful with your iterators. E.g:
348 \snippet code/doc_src_containers.cpp 24
350 The above example only shows a problem with QList, but
351 the problem exists for all the implicitly shared Qt containers.
353 \section3 Java-Style Iterators
354 \l{java-style-iterators}{Java-Style iterators}
356 on Java's iterator classes.
357 New code should prefer \l{STL-Style Iterators}.
359 \section1 Qt containers compared with std containers
362 \header \li Qt container \li Closest std container
364 \row \li \l{QList}<T>
365 \li Similar to std::vector<T>
367 \l{QList} and \l{QVector} were unified in Qt 6. Both
368 use the datamodel from QVector. QVector is now an alias to QList.
370 This means that QList is not implemented as a linked list, so if
371 you need constant time insert, delete, append or prepend,
372 consider \c std::list<T>. See \l{QList} for details.
374 \row \li \l{QVarLengthArray}<T, Prealloc>
375 \li Resembles a mix of std::array<T> and std::vector<T>.
377 For performance reasons, QVarLengthArray lives on the stack unless
378 resized. Resizing it automatically causes it to use the heap instead.
380 \row \li \l{QStack}<T>
381 \li Similar to std::stack<T>, inherits from \l{QList}.
383 \row \li \l{QQueue}<T>
384 \li Similar to std::queue<T>, inherits from \l{QList}.
387 \li Similar to std::unordered_set<T>. Internally, \l{QSet} is implemented with a
390 \row \li \l{QMap}<Key, T>
391 \li Similar to std::map<Key, T>.
393 \row \li \l{QMultiMap}<Key, T>
394 \li Similar to std::multimap<Key, T>.
396 \row \li \l{QHash}<Key, T>
397 \li Most similar to std::unordered_map<Key, T>.
399 \row \li \l{QMultiHash}<Key, T>
400 \li Most similar to std::unordered_multimap<Key, T>.
404 \section1 Qt containers and std algorithms
406 You can use Qt containers with functions from \c{#include <algorithm>}.
408 \snippet code/doc_src_containers.cpp 26
410 \section1 Other Container-Like Classes
412 Qt includes other template classes that resemble containers in
413 some respects. These classes don't provide iterators and cannot
414 be used with the \l foreach keyword.
417 \li QCache<Key, T> provides a cache to store objects of a certain
418 type T associated with keys of type Key.
420 \li QContiguousCache<T> provides an efficient way of caching data
421 that is typically accessed in a contiguous way.
424 Additional non-template types that compete with Qt's template
425 containers are QBitArray, QByteArray, QString, and QStringList.
427 \section1 Algorithmic Complexity
429 Algorithmic complexity is concerned about how fast (or slow) each
430 function is as the number of items in the container grow. For
431 example, inserting an item in the middle of a std::list is an
432 extremely fast operation, irrespective of the number of items
433 stored in the list. On the other hand, inserting an item
434 in the middle of a QList is potentially very expensive if the
435 QList contains many items, since half of the items must be
436 moved one position in memory.
438 To describe algorithmic complexity, we use the following
439 terminology, based on the "big Oh" notation:
441 \target constant time
442 \target logarithmic time
444 \target linear-logarithmic time
445 \target quadratic time
448 \li \b{Constant time:} O(1). A function is said to run in constant
449 time if it requires the same amount of time no matter how many
450 items are present in the container. One example is
453 \li \b{Logarithmic time:} O(log \e n). A function that runs in
454 logarithmic time is a function whose running time is
455 proportional to the logarithm of the number of items in the
456 container. One example is the binary search algorithm.
458 \li \b{Linear time:} O(\e n). A function that runs in linear time
459 will execute in a time directly proportional to the number of
460 items stored in the container. One example is
463 \li \b{Linear-logarithmic time:} O(\e{n} log \e n). A function
464 that runs in linear-logarithmic time is asymptotically slower
465 than a linear-time function, but faster than a quadratic-time
468 \li \b{Quadratic time:} O(\e{n}\unicode{178}). A quadratic-time function
469 executes in a time that is proportional to the square of the
470 number of items stored in the container.
473 The following table summarizes the algorithmic complexity of the sequential
477 \header \li \li Index lookup \li Insertion \li Prepending \li Appending
478 \row \li QList<T> \li O(1) \li O(n) \li O(n) \li Amort. O(1)
481 In the table, "Amort." stands for "amortized behavior". For
482 example, "Amort. O(1)" means that if you call the function
483 only once, you might get O(\e n) behavior, but if you call it
484 multiple times (e.g., \e n times), the average behavior will be
487 The following table summarizes the algorithmic complexity of Qt's
488 associative containers and sets:
491 \header \li{1,2} \li{2,1} Key lookup \li{2,1} Insertion
492 \header \li Average \li Worst case \li Average \li Worst case
493 \row \li QMap<Key, T> \li O(log \e n) \li O(log \e n) \li O(log \e n) \li O(log \e n)
494 \row \li QMultiMap<Key, T> \li O(log \e n) \li O(log \e n) \li O(log \e n) \li O(log \e n)
495 \row \li QHash<Key, T> \li Amort. O(1) \li O(\e n) \li Amort. O(1) \li O(\e n)
496 \row \li QSet<Key> \li Amort. O(1) \li O(\e n) \li Amort. O(1) \li O(\e n)
499 With QList, QHash, and QSet, the performance of appending items
500 is amortized O(log \e n). It can be brought down to O(1) by
501 calling QList::reserve(), QHash::reserve(), or QSet::reserve()
502 with the expected number of items before you insert the items.
503 The next section discusses this topic in more depth.
505 \section1 Optimizations for Primitive and Relocatable Types
507 Qt containers can use optimized code paths if the stored
508 elements are relocatable or even primitive.
509 However, whether types are primitive or relocatable
510 cannot be detected in all cases.
511 You can declare your types to be primitive or relocatable
512 by using the Q_DECLARE_TYPEINFO macro with the Q_PRIMITIVE_TYPE
513 flag or the Q_RELOCATABLE_TYPE flag. See the documentation
514 of Q_DECLARE_TYPEINFO for further details and usage examples.
516 If you do not use Q_DECLARE_TYPEINFO,
518 \l {https://en.cppreference.com/w/cpp/types/is_trivial} {std::is_trivial_v<T>}
519 to identify primitive
520 types and it will require both
521 \l {https://en.cppreference.com/w/cpp/types/is_trivially_copyable} {std::is_trivially_copyable_v<T>}
523 \l {https://en.cppreference.com/w/cpp/types/is_destructible} {std::is_trivially_destructible_v<T>}
524 to identify relocatable types.
525 This is always a safe choice, albeit
526 of maybe suboptimal performance.
528 \section1 Growth Strategies
530 QList<T>, QString, and QByteArray store their items
531 contiguously in memory; QHash<Key, T> keeps a
532 hash table whose size is proportional to the number
533 of items in the hash. To avoid reallocating the data every single
534 time an item is added at the end of the container, these classes
535 typically allocate more memory than necessary.
537 Consider the following code, which builds a QString from another
540 \snippet code/doc_src_containers.cpp 23
542 We build the string \c out dynamically by appending one character
543 to it at a time. Let's assume that we append 15000 characters to
544 the QString string. Then the following 11 reallocations (out of a
545 possible 15000) occur when QString runs out of space: 8, 24, 56,
546 120, 248, 504, 1016, 2040, 4088, 8184, 16376.
547 At the end, the QString has 16376 Unicode
548 characters allocated, 15000 of which are occupied.
550 The values above may seem a bit strange, but there is a guiding
551 principle. It advances by doubling the size each time.
552 More precisely, it advances to the next power of two, minus
553 16 bytes. 16 bytes corresponds to eight characters, as QString
554 uses UTF-16 internally.
556 QByteArray uses the same algorithm as
557 QString, but 16 bytes correspond to 16 characters.
559 QList<T> also uses that algorithm, but 16 bytes correspond to
560 16/sizeof(T) elements.
562 QHash<Key, T> is a totally different case. QHash's internal hash
563 table grows by powers of two, and each time it grows, the items
564 are relocated in a new bucket, computed as qHash(\e key) %
565 QHash::capacity() (the number of buckets). This remark applies to
566 QSet<T> and QCache<Key, T> as well.
568 For most applications, the default growing algorithm provided by
569 Qt does the trick. If you need more control, QList<T>,
570 QHash<Key, T>, QSet<T>, QString, and QByteArray provide a trio of
571 functions that allow you to check and specify how much memory to
572 use to store the items:
575 \li \l{QString::capacity()}{capacity()} returns the
576 number of items for which memory is allocated (for QHash and
577 QSet, the number of buckets in the hash table).
578 \li \l{QString::reserve()}{reserve}(\e size) explicitly
579 preallocates memory for \e size items.
580 \li \l{QString::squeeze()}{squeeze()} frees any memory
581 not required to store the items.
584 If you know approximately how many items you will store in a
585 container, you can start by calling \l{QString::reserve()}{reserve()}, and when you are
586 done populating the container, you can call \l{QString::squeeze()}{squeeze()} to release
587 the extra preallocated memory.
1.10.0