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 \target iterator-begin
225 \target iterator-end
226 \section3 STL-Style Iterators
227
228 STL-style iterators have been available since the release of Qt
229 2.0. They are compatible with Qt's and STL's \l{generic
230 algorithms} and are optimized for speed.
231
232 For each container class, there are two STL-style iterator types:
233 one that provides read-only access and one that provides
234 read-write access. Read-only iterators should be used wherever
235 possible because they are faster than read-write iterators.
236
237 \table
238 \header \li Containers \li Read-only iterator
239 \li Read-write iterator
240 \row \li QList<T>, QStack<T>, QQueue<T> \li QList<T>::const_iterator
241 \li QList<T>::iterator
242 \row \li QSet<T> \li QSet<T>::const_iterator
243 \li QSet<T>::iterator
244 \row \li QMap<Key, T>, QMultiMap<Key, T> \li QMap<Key, T>::const_iterator
245 \li QMap<Key, T>::iterator
246 \row \li QHash<Key, T>, QMultiHash<Key, T> \li QHash<Key, T>::const_iterator
247 \li QHash<Key, T>::iterator
248 \endtable
249
250 The API of the STL iterators is modelled on pointers in an array.
251 For example, the \c ++ operator advances the iterator to the next
252 item, and the \c * operator returns the item that the iterator
253 points to. In fact, for QList and QStack, which store their
254 items at adjacent memory positions, the
255 \l{QList::iterator}{iterator} type is just a typedef for \c{T *},
256 and the \l{QList::iterator}{const_iterator} type is
257 just a typedef for \c{const T *}.
258
259 In this discussion, we will concentrate on QList and QMap. The
260 iterator types for QSet have exactly
261 the same interface as QList's iterators; similarly, the iterator
262 types for QHash have the same interface as QMap's iterators.
263
264 Here's a typical loop for iterating through all the elements of a
265 QList<QString> in order and converting them to lowercase:
266
267 \snippet code/doc_src_containers.cpp 10
268
269 STL-style iterators point directly at items. The \l{QList::begin()}{begin()}
270 function of a container returns an iterator that points to the first item in the
271 container. The \l{QList::end()}{end()} function of a container returns an iterator to the
272 imaginary item one position past the last item in the container.
273 \l {QList::end()}{end()} marks an invalid position; it must never be dereferenced.
274 It is typically used in a loop's break condition. If the list is
275 empty, \l{QList::begin}{begin()} equals \l{QList::end()}{end()}, so we never execute the loop.
276
277 The diagram below shows the valid iterator positions as red
278 arrows for a list containing four items:
279
280 \image stliterators1.svg STL-style iterators point to items
281
282 Iterating backward with an STL-style iterator is done with reverse iterators:
283
284 \snippet code/doc_src_containers.cpp 11
285
286 In the code snippets so far, we used the unary \c * operator to
287 retrieve the item (of type QString) stored at a certain iterator
288 position, and we then called QString::toLower() on it.
289
290 For read-only access, you can use const_iterator, \l{QList::cbegin}{cbegin()},
291 and \l{QList::cend()}{cend()}. For example:
292
293 \snippet code/doc_src_containers.cpp 12
294
295 The following table summarizes the STL-style iterators' API:
296
297 \table
298 \header \li Expression \li Behavior
299 \row \li \c{*i} \li Returns the current item
300 \row \li \c{++i} \li Advances the iterator to the next item
301 \row \li \c{i += n} \li Advances the iterator by \c n items
302 \row \li \c{--i} \li Moves the iterator back by one item
303 \row \li \c{i -= n} \li Moves the iterator back by \c n items
304 \row \li \c{i - j} \li Returns the number of items between iterators \c i and \c j
305 \endtable
306
307 The \c{++} and \c{--} operators are available both as prefix
308 (\c{++i}, \c{--i}) and postfix (\c{i++}, \c{i--}) operators. The
309 prefix versions modify the iterators and return a reference to
310 the modified iterator; the postfix versions take a copy of the
311 iterator before they modify it, and return that copy. In
312 expressions where the return value is ignored, we recommend that
313 you use the prefix operators (\c{++i}, \c{--i}), as these are
314 slightly faster.
315
316 For non-const iterator types, the return value of the unary \c{*}
317 operator can be used on the left side of the assignment operator.
318
319 For QMap and QHash, the \c{*} operator returns the value
320 component of an item. If you want to retrieve the key, call key()
321 on the iterator. For symmetry, the iterator types also provide a
322 value() function to retrieve the value. For example, here's how
323 we would print all items in a QMap to the console:
324
325 \snippet code/doc_src_containers.cpp 13
326
327 Thanks to \l{implicit sharing}, it is very inexpensive for a
328 function to return a container per value. The Qt API contains
329 dozens of functions that return a QList or QStringList per value
330 (e.g., QSplitter::sizes()). If you want to iterate over these
331 using an STL iterator, you should always take a copy of the
332 container and iterate over the copy. For example:
333
334 \snippet code/doc_src_containers.cpp 14
335
336 This problem doesn't occur with functions that return a const or
337 non-const reference to a container.
338
339 \section4 Implicit sharing iterator problem
340
341 \l{Implicit sharing} has another consequence on STL-style
342 iterators: you should avoid copying a container while
343 iterators are active on that container. The iterators
344 point to an internal structure, and if you copy a container
345 you should be very careful with your iterators. E.g:
346
347 \snippet code/doc_src_containers.cpp 24
348
349 The above example only shows a problem with QList, but
350 the problem exists for all the implicitly shared Qt containers.
351
352 \section3 Java-Style Iterators
353 \l{java-style-iterators}{Java-Style iterators}
354 are modelled
355 on Java's iterator classes.
356 New code should prefer \l{STL-Style Iterators}.
357
358 \section1 Qt containers compared with std containers
359
360 \table
361 \header \li Qt container \li Closest std container
362
363 \row \li \l{QList}<T>
364 \li Similar to std::vector<T>
365
366 \l{QList} and \l{QVector} were unified in Qt 6. Both
367 use the datamodel from QVector. QVector is now an alias to QList.
368
369 This means that QList is not implemented as a linked list, so if
370 you need constant time insert, delete, append or prepend,
371 consider \c std::list<T>. See \l{QList} for details.
372
373 \row \li \l{QVarLengthArray}<T, Prealloc>
374 \li Resembles a mix of std::array<T> and std::vector<T>.
375
376 For performance reasons, QVarLengthArray lives on the stack unless
377 resized. Resizing it automatically causes it to use the heap instead.
378
379 \row \li \l{QStack}<T>
380 \li Similar to std::stack<T>, inherits from \l{QList}.
381
382 \row \li \l{QQueue}<T>
383 \li Similar to std::queue<T>, inherits from \l{QList}.
384
385 \row \li \l{QSet}<T>
386 \li Similar to std::unordered_set<T>. Internally, \l{QSet} is implemented with a
387 \l{QHash}.
388
389 \row \li \l{QMap}<Key, T>
390 \li Similar to std::map<Key, T>.
391
392 \row \li \l{QMultiMap}<Key, T>
393 \li Similar to std::multimap<Key, T>.
394
395 \row \li \l{QHash}<Key, T>
396 \li Most similar to std::unordered_map<Key, T>.
397
398 \row \li \l{QMultiHash}<Key, T>
399 \li Most similar to std::unordered_multimap<Key, T>.
400
401 \endtable
402
403 \section1 Qt containers and std algorithms
404
405 You can use Qt containers with functions from \c{#include <algorithm>}.
406
407 \snippet code/doc_src_containers.cpp 26
408
409 \section1 Qt container algorithms
410
411 Qt also provides additional generic algorithms in \l {<QtAlgorithms>} that
412 work with any container supporting STL-style iterators, such as \l {qJoin()}
413 for joining container elements into a single value, and \l {qDeleteAll()}
414 for invoking \c{operator delete} on all items in a container or in a given
415 range.
416
417 \section1 Other Container-Like Classes
418
419 Qt includes other template classes that resemble containers in
420 some respects. These classes don't provide iterators and cannot
421 be used with the \l foreach keyword.
422
423 \list
424 \li QCache<Key, T> provides a cache to store objects of a certain
425 type T associated with keys of type Key.
426
427 \li QContiguousCache<T> provides an efficient way of caching data
428 that is typically accessed in a contiguous way.
429 \endlist
430
431 Additional non-template types that compete with Qt's template
432 containers are QBitArray, QByteArray, QString, and QStringList.
433
434 \section1 Algorithmic Complexity
435
436 Algorithmic complexity is concerned about how fast (or slow) each
437 function is as the number of items in the container grow. For
438 example, inserting an item in the middle of a std::list is an
439 extremely fast operation, irrespective of the number of items
440 stored in the list. On the other hand, inserting an item
441 in the middle of a QList is potentially very expensive if the
442 QList contains many items, since half of the items must be
443 moved one position in memory.
444
445 To describe algorithmic complexity, we use the following
446 terminology, based on the "big Oh" notation:
447
448 \target constant time
449 \target logarithmic time
450 \target linear time
451 \target linear-logarithmic time
452 \target quadratic time
453
454 \list
455 \li \b{Constant time:} O(1). A function is said to run in constant
456 time if it requires the same amount of time no matter how many
457 items are present in the container. One example is
458 QList::push_back().
459
460 \li \b{Logarithmic time:} O(log \e n). A function that runs in
461 logarithmic time is a function whose running time is
462 proportional to the logarithm of the number of items in the
463 container. One example is the binary search algorithm.
464
465 \li \b{Linear time:} O(\e n). A function that runs in linear time
466 will execute in a time directly proportional to the number of
467 items stored in the container. One example is
468 QList::insert().
469
470 \li \b{Linear-logarithmic time:} O(\e{n} log \e n). A function
471 that runs in linear-logarithmic time is asymptotically slower
472 than a linear-time function, but faster than a quadratic-time
473 function.
474
475 \li \b{Quadratic time:} O(\e{n}\unicode{178}). A quadratic-time function
476 executes in a time that is proportional to the square of the
477 number of items stored in the container.
478 \endlist
479
480 The following table summarizes the algorithmic complexity of the sequential
481 container QList<T>:
482
483 \table
484 \header \li \li Index lookup \li Insertion \li Prepending \li Appending
485 \row \li QList<T> \li O(1) \li O(n) \li O(n) \li Amort. O(1)
486 \endtable
487
488 In the table, "Amort." stands for "amortized behavior". For
489 example, "Amort. O(1)" means that if you call the function
490 only once, you might get O(\e n) behavior, but if you call it
491 multiple times (e.g., \e n times), the average behavior will be
492 O(1).
493
494 The following table summarizes the algorithmic complexity of Qt's
495 associative containers and sets:
496
497 \table
498 \header \li{1,2} \li{2,1} Key lookup \li{2,1} Insertion
499 \header \li Average \li Worst case \li Average \li Worst case
500 \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)
501 \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)
502 \row \li QHash<Key, T> \li Amort. O(1) \li O(\e n) \li Amort. O(1) \li O(\e n)
503 \row \li QSet<Key> \li Amort. O(1) \li O(\e n) \li Amort. O(1) \li O(\e n)
504 \endtable
505
506 With QList, QHash, and QSet, the performance of appending items
507 is amortized O(log \e n). It can be brought down to O(1) by
508 calling QList::reserve(), QHash::reserve(), or QSet::reserve()
509 with the expected number of items before you insert the items.
510 The next section discusses this topic in more depth.
511
512 \section1 Optimizations for Primitive and Relocatable Types
513
514 Qt containers can use optimized code paths if the stored
515 elements are relocatable or even primitive.
516 However, whether types are primitive or relocatable
517 cannot be detected in all cases.
518 You can declare your types to be primitive or relocatable
519 by using the Q_DECLARE_TYPEINFO macro with the Q_PRIMITIVE_TYPE
520 flag or the Q_RELOCATABLE_TYPE flag. See the documentation
521 of Q_DECLARE_TYPEINFO for further details and usage examples.
522
523 If you do not use Q_DECLARE_TYPEINFO,
524 Qt will use
525 \l {https://en.cppreference.com/w/cpp/types/is_trivial} {std::is_trivial_v<T>}
526 to identify primitive
527 types and it will require both
528 \l {https://en.cppreference.com/w/cpp/types/is_trivially_copyable} {std::is_trivially_copyable_v<T>}
529 and
530 \l {https://en.cppreference.com/w/cpp/types/is_destructible} {std::is_trivially_destructible_v<T>}
531 to identify relocatable types.
532 This is always a safe choice, albeit
533 of maybe suboptimal performance.
534
535 \section1 Growth Strategies
536
537 QList<T>, QString, and QByteArray store their items
538 contiguously in memory; QHash<Key, T> keeps a
539 hash table whose size is proportional to the number
540 of items in the hash. To avoid reallocating the data every single
541 time an item is added at the end of the container, these classes
542 typically allocate more memory than necessary.
543
544 Consider the following code, which builds a QString from another
545 QString:
546
547 \snippet code/doc_src_containers.cpp 23
548
549 We build the string \c out dynamically by appending one character
550 to it at a time. Let's assume that we append 15000 characters to
551 the QString string. Then the following 11 reallocations (out of a
552 possible 15000) occur when QString runs out of space: 8, 24, 56,
553 120, 248, 504, 1016, 2040, 4088, 8184, 16376.
554 At the end, the QString has 16376 Unicode
555 characters allocated, 15000 of which are occupied.
556
557 The values above may seem a bit strange, but there is a guiding
558 principle. It advances by doubling the size each time.
559 More precisely, it advances to the next power of two, minus
560 16 bytes. 16 bytes corresponds to eight characters, as QString
561 uses UTF-16 internally.
562
563 QByteArray uses the same algorithm as
564 QString, but 16 bytes correspond to 16 characters.
565
566 QList<T> also uses that algorithm, but 16 bytes correspond to
567 16/sizeof(T) elements.
568
569 QHash<Key, T> is a totally different case. QHash's internal hash
570 table grows by powers of two, and each time it grows, the items
571 are relocated in a new bucket, computed as qHash(\e key) %
572 QHash::capacity() (the number of buckets). This remark applies to
573 QSet<T> and QCache<Key, T> as well.
574
575 For most applications, the default growing algorithm provided by
576 Qt does the trick. If you need more control, QList<T>,
577 QHash<Key, T>, QSet<T>, QString, and QByteArray provide a trio of
578 functions that allow you to check and specify how much memory to
579 use to store the items:
580
581 \list
582 \li \l{QString::capacity()}{capacity()} returns the
583 number of items for which memory is allocated (for QHash and
584 QSet, the number of buckets in the hash table).
585 \li \l{QString::reserve()}{reserve}(\e size) explicitly
586 preallocates memory for \e size items.
587 \li \l{QString::squeeze()}{squeeze()} frees any memory
588 not required to store the items.
589 \endlist
590
591 If you know approximately how many items you will store in a
592 container, you can start by calling \l{QString::reserve()}{reserve()}, and when you are
593 done populating the container, you can call \l{QString::squeeze()}{squeeze()} to release
594 the extra preallocated memory.
595*/