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