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