Qt
Internal/Contributor docs for the Qt SDK. Note: These are NOT official API docs; those are found at https://doc.qt.io/
Loading...
Searching...
No Matches
containers.qdoc
Go to the documentation of this file.
1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GFDL-1.3-no-invariants-only
3
4/*!
5 \group containers
6 \noautolist
7 \title Container Classes
8 \ingroup groups
9 \ingroup qt-basic-concepts
10 \keyword container class
11 \keyword container classes
12
13 \brief Qt's template-based container classes.
14
15 \section1 Introduction
16
17 The Qt library provides a set of general purpose template-based
18 container classes. These classes can be used to store items of a
19 specified type. For example, if you need a resizable array of
20 \l{QString}s, use QList<QString>.
21
22 These container classes are designed to be lighter, safer, and
23 easier to use than the STL containers. If you are unfamiliar with
24 the STL, or prefer to do things the "Qt way", you can use these
25 classes instead of the STL classes.
26
27 The container classes are \l{implicitly shared}, they are
28 \l{reentrant}, and they are optimized for speed, low memory
29 consumption, and minimal inline code expansion, resulting in
30 smaller executables. In addition, they are \l{thread-safe}
31 in situations where they are used as read-only containers
32 by all threads used to access them.
33
34 The containers provide iterators for traversal. \l{STL-style iterators}
35 are the most efficient ones and can be used together with Qt's and
36 STL's \l{generic algorithms}.
37 \l{Java-style Iterators} are provided for backwards compatibility.
38
39 \note Since Qt 5.14, range constructors are available for most of the
40 container classes. QMultiMap is a notable exception. Their use is
41 encouraged to replace of the various deprecated from/to methods of Qt 5.
42 For example:
43
44 \snippet code/doc_src_containers.cpp 25
45
46 \section1 The Container Classes
47
48 Qt provides the following sequential containers: QList,
49 QStack, and QQueue. For most
50 applications, QList is the best type to use. It provides very fast
51 appends. If you really need a linked-list, use std::list.
52 QStack and QQueue are convenience classes that provide LIFO and
53 FIFO semantics.
54
55 Qt also provides these associative containers: QMap,
56 QMultiMap, QHash, QMultiHash, and QSet. The "Multi" containers
57 conveniently support multiple values associated with a single
58 key. The "Hash" containers provide faster lookup by using a hash
59 function instead of a binary search on a sorted set.
60
61 As special cases, the QCache and QContiguousCache classes provide
62 efficient hash-lookup of objects in a limited cache storage.
63
64 \table
65 \header \li Class \li Summary
66
67 \row \li \l{QList}<T>
68 \li This is by far the most commonly used container class. It
69 stores a list of values of a given type (T) that can be accessed
70 by index. Internally, it stores an array of values of a
71 given type at adjacent
72 positions in memory. Inserting at the front or in the middle of
73 a list can be quite slow, because it can lead to large numbers
74 of items having to be moved by one position in memory.
75
76 \row \li \l{QVarLengthArray}<T, Prealloc>
77 \li This provides a low-level variable-length array. It can be used
78 instead of QList in places where speed is particularly important.
79
80 \row \li \l{QStack}<T>
81 \li This is a convenience subclass of QList that provides
82 "last in, first out" (LIFO) semantics. It adds the following
83 functions to those already present in QList:
84 \l{QStack::push()}{push()}, \l{QStack::pop()}{pop()},
85 and \l{QStack::top()}{top()}.
86
87 \row \li \l{QQueue}<T>
88 \li This is a convenience subclass of QList that provides
89 "first in, first out" (FIFO) semantics. It adds the following
90 functions to those already present in QList:
91 \l{QQueue::enqueue()}{enqueue()},
92 \l{QQueue::dequeue()}{dequeue()}, and \l{QQueue::head()}{head()}.
93
94 \row \li \l{QSet}<T>
95 \li This provides a single-valued mathematical set with fast
96 lookups.
97
98 \row \li \l{QMap}<Key, T>
99 \li This provides a dictionary (associative array) that maps keys
100 of type Key to values of type T. Normally each key is associated
101 with a single value. QMap stores its data in Key order; if order
102 doesn't matter QHash is a faster alternative.
103
104 \row \li \l{QMultiMap}<Key, T>
105 \li This provides a dictionary, like QMap, except it allows
106 inserting multiple equivalent keys.
107
108 \row \li \l{QHash}<Key, T>
109 \li This has almost the same API as QMap, but provides
110 significantly faster lookups. QHash stores its data in an
111 arbitrary order.
112
113 \row \li \l{QMultiHash}<Key, T>
114 \li This provides a hash-table-based dictionary, like QHash,
115 except it allows inserting multiple equivalent keys.
116
117 \endtable
118
119 Containers can be nested. For example, it is perfectly possible
120 to use a QMap<QString, QList<int>>, where the key type is
121 QString and the value type QList<int>.
122
123 The containers are defined in individual header files with the
124 same name as the container (e.g., \c <QList>). For
125 convenience, the containers are forward declared in \c
126 <QtContainerFwd>.
127
128 \target assignable data type
129 \target assignable data types
130
131 The values stored in the various containers can be of any
132 \e{assignable data type}. To qualify, a type must provide a
133 copy constructor, and an assignment operator. For some
134 operations a default constructor is also required. This
135 covers most data types you are likely to want to
136 store in a container, including basic types such as \c int and \c
137 double, pointer types, and Qt data types such as QString, QDate,
138 and QTime, but it doesn't cover QObject or any QObject subclass
139 (QWidget, QDialog, QTimer, etc.). If you attempt to instantiate a
140 QList<QWidget>, the compiler will complain that QWidget's copy
141 constructor and assignment operators are disabled. If you want to
142 store these kinds of objects in a container, store them as
143 pointers, for example as QList<QWidget *>.
144
145 Here's an example custom data type that meets the requirement of
146 an assignable data type:
147
148 \snippet code/doc_src_containers.cpp 0
149
150 If we don't provide a copy constructor or an assignment operator,
151 C++ provides a default implementation that performs a
152 member-by-member copy. In the example above, that would have been
153 sufficient. Also, if you don't provide any constructors, C++
154 provides a default constructor that initializes its member using
155 default constructors. Although it doesn't provide any
156 explicit constructors or assignment operator, the following data
157 type can be stored in a container:
158
159 \snippet streaming/main.cpp 0
160
161 Some containers have additional requirements for the data types
162 they can store. For example, the Key type of a QMap<Key, T> must
163 provide \c operator<(). Such special requirements are documented
164 in a class's detailed description. In some cases, specific
165 functions have special requirements; these are described on a
166 per-function basis. The compiler will always emit an error if a
167 requirement isn't met.
168
169 Qt's containers provide operator<<() and operator>>() so that they
170 can easily be read and written using a QDataStream. This means
171 that the data types stored in the container must also support
172 operator<<() and operator>>(). Providing such support is
173 straightforward; here's how we could do it for the Movie struct
174 above:
175
176 \snippet streaming/main.cpp 1
177 \codeline
178 \snippet streaming/main.cpp 2
179
180 \target default-constructed value
181
182 The documentation of certain container class functions refer to
183 \e{default-constructed values}; for example, QList
184 automatically initializes its items with default-constructed
185 values, and QMap::value() returns a default-constructed value if
186 the specified key isn't in the map. For most value types, this
187 simply means that a value is created using the default
188 constructor (e.g. an empty string for QString). But for primitive
189 types like \c{int} and \c{double}, as well as for pointer types,
190 the C++ language doesn't specify any initialization; in those
191 cases, Qt's containers automatically initialize the value to 0.
192
193 \section1 Iterating over Containers
194
195 \section2 Range-based for
196
197 Range-based \c for should preferably be used for containers:
198
199 \snippet code/doc_src_containers.cpp range_for
200
201 Note that when using a Qt container in a non-const context,
202 \l{implicit sharing} may perform an undesired detach of the container.
203 To prevent this, use \c std::as_const():
204
205 \snippet code/doc_src_containers.cpp range_for_as_const
206
207 For associative containers, this will loop over the values.
208
209 \section2 Index-based
210
211 For sequential containers that store their items contiguously in memory
212 (for example, QList), index-based iteration can be used:
213
214 \snippet code/doc_src_containers.cpp index
215
216 \section2 The Iterator Classes
217
218 Iterators provide a uniform means to access items in a container.
219 Qt's container classes provide two types of iterators: STL-style
220 iterators and Java-style iterators. Iterators of both types are
221 invalidated when the data in the container is modified or detached
222 from \l{Implicit Sharing}{implicitly shared copies} due to a call
223 to a non-const member function.
224
225 \target iterator-begin
226 \target iterator-end
227 \section3 STL-Style Iterators
228
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.
232
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.
237
238 \table
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
249 \endtable
250
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 *}.
259
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.
264
265 Here's a typical loop for iterating through all the elements of a
266 QList<QString> in order and converting them to lowercase:
267
268 \snippet code/doc_src_containers.cpp 10
269
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.
277
278 The diagram below shows the valid iterator positions as red
279 arrows for a list containing four items:
280
281 \image stliterators1.svg STL-style iterators point to items
282
283 Iterating backward with an STL-style iterator is done with reverse iterators:
284
285 \snippet code/doc_src_containers.cpp 11
286
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.
290
291 For read-only access, you can use const_iterator, \l{QList::cbegin}{cbegin()},
292 and \l{QList::cend()}{cend()}. For example:
293
294 \snippet code/doc_src_containers.cpp 12
295
296 The following table summarizes the STL-style iterators' API:
297
298 \table
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
306 \endtable
307
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
315 slightly faster.
316
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.
319
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:
325
326 \snippet code/doc_src_containers.cpp 13
327
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:
334
335 \snippet code/doc_src_containers.cpp 14
336
337 This problem doesn't occur with functions that return a const or
338 non-const reference to a container.
339
340 \section4 Implicit sharing iterator problem
341
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:
347
348 \snippet code/doc_src_containers.cpp 24
349
350 The above example only shows a problem with QList, but
351 the problem exists for all the implicitly shared Qt containers.
352
353 \section3 Java-Style Iterators
354 \l{java-style-iterators}{Java-Style iterators}
355 are modelled
356 on Java's iterator classes.
357 New code should prefer \l{STL-Style Iterators}.
358
359 \section1 Qt containers compared with std containers
360
361 \table
362 \header \li Qt container \li Closest std container
363
364 \row \li \l{QList}<T>
365 \li Similar to std::vector<T>
366
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.
369
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.
373
374 \row \li \l{QVarLengthArray}<T, Prealloc>
375 \li Resembles a mix of std::array<T> and std::vector<T>.
376
377 For performance reasons, QVarLengthArray lives on the stack unless
378 resized. Resizing it automatically causes it to use the heap instead.
379
380 \row \li \l{QStack}<T>
381 \li Similar to std::stack<T>, inherits from \l{QList}.
382
383 \row \li \l{QQueue}<T>
384 \li Similar to std::queue<T>, inherits from \l{QList}.
385
386 \row \li \l{QSet}<T>
387 \li Similar to std::unordered_set<T>. Internally, \l{QSet} is implemented with a
388 \l{QHash}.
389
390 \row \li \l{QMap}<Key, T>
391 \li Similar to std::map<Key, T>.
392
393 \row \li \l{QMultiMap}<Key, T>
394 \li Similar to std::multimap<Key, T>.
395
396 \row \li \l{QHash}<Key, T>
397 \li Most similar to std::unordered_map<Key, T>.
398
399 \row \li \l{QMultiHash}<Key, T>
400 \li Most similar to std::unordered_multimap<Key, T>.
401
402 \endtable
403
404 \section1 Qt containers and std algorithms
405
406 You can use Qt containers with functions from \c{#include <algorithm>}.
407
408 \snippet code/doc_src_containers.cpp 26
409
410 \section1 Qt container algorithms
411
412 Qt also provides additional generic algorithms in \l {<QtAlgorithms>} that
413 work with any container supporting STL-style iterators, such as \l {qJoin()}
414 for joining container elements into a single value, and \l {qDeleteAll()}
415 for invoking \c{operator delete} on all items in a container or in a given
416 range.
417
418 \section1 Other Container-Like Classes
419
420 Qt includes other template classes that resemble containers in
421 some respects. These classes don't provide iterators and cannot
422 be used with the \l foreach keyword.
423
424 \list
425 \li QCache<Key, T> provides a cache to store objects of a certain
426 type T associated with keys of type Key.
427
428 \li QContiguousCache<T> provides an efficient way of caching data
429 that is typically accessed in a contiguous way.
430 \endlist
431
432 Additional non-template types that compete with Qt's template
433 containers are QBitArray, QByteArray, QString, and QStringList.
434
435 \section1 Algorithmic Complexity
436
437 Algorithmic complexity is concerned about how fast (or slow) each
438 function is as the number of items in the container grow. For
439 example, inserting an item in the middle of a std::list is an
440 extremely fast operation, irrespective of the number of items
441 stored in the list. On the other hand, inserting an item
442 in the middle of a QList is potentially very expensive if the
443 QList contains many items, since half of the items must be
444 moved one position in memory.
445
446 To describe algorithmic complexity, we use the following
447 terminology, based on the "big Oh" notation:
448
449 \target constant time
450 \target logarithmic time
451 \target linear time
452 \target linear-logarithmic time
453 \target quadratic time
454
455 \list
456 \li \b{Constant time:} O(1). A function is said to run in constant
457 time if it requires the same amount of time no matter how many
458 items are present in the container. One example is
459 QList::push_back().
460
461 \li \b{Logarithmic time:} O(log \e n). A function that runs in
462 logarithmic time is a function whose running time is
463 proportional to the logarithm of the number of items in the
464 container. One example is the binary search algorithm.
465
466 \li \b{Linear time:} O(\e n). A function that runs in linear time
467 will execute in a time directly proportional to the number of
468 items stored in the container. One example is
469 QList::insert().
470
471 \li \b{Linear-logarithmic time:} O(\e{n} log \e n). A function
472 that runs in linear-logarithmic time is asymptotically slower
473 than a linear-time function, but faster than a quadratic-time
474 function.
475
476 \li \b{Quadratic time:} O(\e{n}\unicode{178}). A quadratic-time function
477 executes in a time that is proportional to the square of the
478 number of items stored in the container.
479 \endlist
480
481 The following table summarizes the algorithmic complexity of the sequential
482 container QList<T>:
483
484 \table
485 \header \li \li Index lookup \li Insertion \li Prepending \li Appending
486 \row \li QList<T> \li O(1) \li O(n) \li O(n) \li Amort. O(1)
487 \endtable
488
489 In the table, "Amort." stands for "amortized behavior". For
490 example, "Amort. O(1)" means that if you call the function
491 only once, you might get O(\e n) behavior, but if you call it
492 multiple times (e.g., \e n times), the average behavior will be
493 O(1).
494
495 The following table summarizes the algorithmic complexity of Qt's
496 associative containers and sets:
497
498 \table
499 \header \li{1,2} \li{2,1} Key lookup \li{2,1} Insertion
500 \header \li Average \li Worst case \li Average \li Worst case
501 \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)
502 \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)
503 \row \li QHash<Key, T> \li Amort. O(1) \li O(\e n) \li Amort. O(1) \li O(\e n)
504 \row \li QSet<Key> \li Amort. O(1) \li O(\e n) \li Amort. O(1) \li O(\e n)
505 \endtable
506
507 With QList, QHash, and QSet, the performance of appending items
508 is amortized O(log \e n). It can be brought down to O(1) by
509 calling QList::reserve(), QHash::reserve(), or QSet::reserve()
510 with the expected number of items before you insert the items.
511 The next section discusses this topic in more depth.
512
513 \section1 Optimizations for Primitive and Relocatable Types
514
515 Qt containers can use optimized code paths if the stored
516 elements are relocatable or even primitive.
517 However, whether types are primitive or relocatable
518 cannot be detected in all cases.
519 You can declare your types to be primitive or relocatable
520 by using the Q_DECLARE_TYPEINFO macro with the Q_PRIMITIVE_TYPE
521 flag or the Q_RELOCATABLE_TYPE flag. See the documentation
522 of Q_DECLARE_TYPEINFO for further details and usage examples.
523
524 If you do not use Q_DECLARE_TYPEINFO,
525 Qt will use
526 \l {https://en.cppreference.com/w/cpp/types/is_trivial} {std::is_trivial_v<T>}
527 to identify primitive
528 types and it will require both
529 \l {https://en.cppreference.com/w/cpp/types/is_trivially_copyable} {std::is_trivially_copyable_v<T>}
530 and
531 \l {https://en.cppreference.com/w/cpp/types/is_destructible} {std::is_trivially_destructible_v<T>}
532 to identify relocatable types.
533 This is always a safe choice, albeit
534 of maybe suboptimal performance.
535
536 \section1 Growth Strategies
537
538 QList<T>, QString, and QByteArray store their items
539 contiguously in memory; QHash<Key, T> keeps a
540 hash table whose size is proportional to the number
541 of items in the hash. To avoid reallocating the data every single
542 time an item is added at the end of the container, these classes
543 typically allocate more memory than necessary.
544
545 Consider the following code, which builds a QString from another
546 QString:
547
548 \snippet code/doc_src_containers.cpp 23
549
550 We build the string \c out dynamically by appending one character
551 to it at a time. Let's assume that we append 15000 characters to
552 the QString string. Then the following 11 reallocations (out of a
553 possible 15000) occur when QString runs out of space: 8, 24, 56,
554 120, 248, 504, 1016, 2040, 4088, 8184, 16376.
555 At the end, the QString has 16376 Unicode
556 characters allocated, 15000 of which are occupied.
557
558 The values above may seem a bit strange, but there is a guiding
559 principle. It advances by doubling the size each time.
560 More precisely, it advances to the next power of two, minus
561 16 bytes. 16 bytes corresponds to eight characters, as QString
562 uses UTF-16 internally.
563
564 QByteArray uses the same algorithm as
565 QString, but 16 bytes correspond to 16 characters.
566
567 QList<T> also uses that algorithm, but 16 bytes correspond to
568 16/sizeof(T) elements.
569
570 QHash<Key, T> is a totally different case. QHash's internal hash
571 table grows by powers of two, and each time it grows, the items
572 are relocated in a new bucket, computed as qHash(\e key) %
573 QHash::capacity() (the number of buckets). This remark applies to
574 QSet<T> and QCache<Key, T> as well.
575
576 For most applications, the default growing algorithm provided by
577 Qt does the trick. If you need more control, QList<T>,
578 QHash<Key, T>, QSet<T>, QString, and QByteArray provide a trio of
579 functions that allow you to check and specify how much memory to
580 use to store the items:
581
582 \list
583 \li \l{QString::capacity()}{capacity()} returns the
584 number of items for which memory is allocated (for QHash and
585 QSet, the number of buckets in the hash table).
586 \li \l{QString::reserve()}{reserve}(\e size) explicitly
587 preallocates memory for \e size items.
588 \li \l{QString::squeeze()}{squeeze()} frees any memory
589 not required to store the items.
590 \endlist
591
592 If you know approximately how many items you will store in a
593 container, you can start by calling \l{QString::reserve()}{reserve()}, and when you are
594 done populating the container, you can call \l{QString::squeeze()}{squeeze()} to release
595 the extra preallocated memory.
596*/