1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtCore module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39
40#include "qmap.h"
41
42#include <stdlib.h>
43
44#ifdef QT_QMAP_DEBUG
45# include <qstring.h>
46# include <qvector.h>
47#endif
48
49QT_BEGIN_NAMESPACE
50
51const QMapDataBase QMapDataBase::shared_null = { Q_REFCOUNT_INITIALIZE_STATIC, .size: 0, .header: { .p: 0, .left: nullptr, .right: nullptr }, .mostLeftNode: nullptr };
52
53const QMapNodeBase *QMapNodeBase::nextNode() const
54{
55 const QMapNodeBase *n = this;
56 if (n->right) {
57 n = n->right;
58 while (n->left)
59 n = n->left;
60 } else {
61 const QMapNodeBase *y = n->parent();
62 while (y && n == y->right) {
63 n = y;
64 y = n->parent();
65 }
66 n = y;
67 }
68 return n;
69}
70
71const QMapNodeBase *QMapNodeBase::previousNode() const
72{
73 const QMapNodeBase *n = this;
74 if (n->left) {
75 n = n->left;
76 while (n->right)
77 n = n->right;
78 } else {
79 const QMapNodeBase *y = n->parent();
80 while (y && n == y->left) {
81 n = y;
82 y = n->parent();
83 }
84 n = y;
85 }
86 return n;
87}
88
89
90void QMapDataBase::rotateLeft(QMapNodeBase *x)
91{
92 QMapNodeBase *&root = header.left;
93 QMapNodeBase *y = x->right;
94 x->right = y->left;
95 if (y->left != nullptr)
96 y->left->setParent(x);
97 y->setParent(x->parent());
98 if (x == root)
99 root = y;
100 else if (x == x->parent()->left)
101 x->parent()->left = y;
102 else
103 x->parent()->right = y;
104 y->left = x;
105 x->setParent(y);
106}
107
108
109void QMapDataBase::rotateRight(QMapNodeBase *x)
110{
111 QMapNodeBase *&root = header.left;
112 QMapNodeBase *y = x->left;
113 x->left = y->right;
114 if (y->right != nullptr)
115 y->right->setParent(x);
116 y->setParent(x->parent());
117 if (x == root)
118 root = y;
119 else if (x == x->parent()->right)
120 x->parent()->right = y;
121 else
122 x->parent()->left = y;
123 y->right = x;
124 x->setParent(y);
125}
126
127
128void QMapDataBase::rebalance(QMapNodeBase *x)
129{
130 QMapNodeBase *&root = header.left;
131 x->setColor(QMapNodeBase::Red);
132 while (x != root && x->parent()->color() == QMapNodeBase::Red) {
133 if (x->parent() == x->parent()->parent()->left) {
134 QMapNodeBase *y = x->parent()->parent()->right;
135 if (y && y->color() == QMapNodeBase::Red) {
136 x->parent()->setColor(QMapNodeBase::Black);
137 y->setColor(QMapNodeBase::Black);
138 x->parent()->parent()->setColor(QMapNodeBase::Red);
139 x = x->parent()->parent();
140 } else {
141 if (x == x->parent()->right) {
142 x = x->parent();
143 rotateLeft(x);
144 }
145 x->parent()->setColor(QMapNodeBase::Black);
146 x->parent()->parent()->setColor(QMapNodeBase::Red);
147 rotateRight (x: x->parent()->parent());
148 }
149 } else {
150 QMapNodeBase *y = x->parent()->parent()->left;
151 if (y && y->color() == QMapNodeBase::Red) {
152 x->parent()->setColor(QMapNodeBase::Black);
153 y->setColor(QMapNodeBase::Black);
154 x->parent()->parent()->setColor(QMapNodeBase::Red);
155 x = x->parent()->parent();
156 } else {
157 if (x == x->parent()->left) {
158 x = x->parent();
159 rotateRight(x);
160 }
161 x->parent()->setColor(QMapNodeBase::Black);
162 x->parent()->parent()->setColor(QMapNodeBase::Red);
163 rotateLeft(x: x->parent()->parent());
164 }
165 }
166 }
167 root->setColor(QMapNodeBase::Black);
168}
169
170void QMapDataBase::freeNodeAndRebalance(QMapNodeBase *z)
171{
172 QMapNodeBase *&root = header.left;
173 QMapNodeBase *y = z;
174 QMapNodeBase *x;
175 QMapNodeBase *x_parent;
176 if (y->left == nullptr) {
177 x = y->right;
178 if (y == mostLeftNode) {
179 if (x)
180 mostLeftNode = x; // It cannot have (left) children due the red black invariant.
181 else
182 mostLeftNode = y->parent();
183 }
184 } else {
185 if (y->right == nullptr) {
186 x = y->left;
187 } else {
188 y = y->right;
189 while (y->left != nullptr)
190 y = y->left;
191 x = y->right;
192 }
193 }
194 if (y != z) {
195 z->left->setParent(y);
196 y->left = z->left;
197 if (y != z->right) {
198 x_parent = y->parent();
199 if (x)
200 x->setParent(y->parent());
201 y->parent()->left = x;
202 y->right = z->right;
203 z->right->setParent(y);
204 } else {
205 x_parent = y;
206 }
207 if (root == z)
208 root = y;
209 else if (z->parent()->left == z)
210 z->parent()->left = y;
211 else
212 z->parent()->right = y;
213 y->setParent(z->parent());
214 // Swap the colors
215 QMapNodeBase::Color c = y->color();
216 y->setColor(z->color());
217 z->setColor(c);
218 y = z;
219 } else {
220 x_parent = y->parent();
221 if (x)
222 x->setParent(y->parent());
223 if (root == z)
224 root = x;
225 else if (z->parent()->left == z)
226 z->parent()->left = x;
227 else
228 z->parent()->right = x;
229 }
230 if (y->color() != QMapNodeBase::Red) {
231 while (x != root && (x == nullptr || x->color() == QMapNodeBase::Black)) {
232 if (x == x_parent->left) {
233 QMapNodeBase *w = x_parent->right;
234 if (w->color() == QMapNodeBase::Red) {
235 w->setColor(QMapNodeBase::Black);
236 x_parent->setColor(QMapNodeBase::Red);
237 rotateLeft(x: x_parent);
238 w = x_parent->right;
239 }
240 if ((w->left == nullptr || w->left->color() == QMapNodeBase::Black) &&
241 (w->right == nullptr || w->right->color() == QMapNodeBase::Black)) {
242 w->setColor(QMapNodeBase::Red);
243 x = x_parent;
244 x_parent = x_parent->parent();
245 } else {
246 if (w->right == nullptr || w->right->color() == QMapNodeBase::Black) {
247 if (w->left)
248 w->left->setColor(QMapNodeBase::Black);
249 w->setColor(QMapNodeBase::Red);
250 rotateRight(x: w);
251 w = x_parent->right;
252 }
253 w->setColor(x_parent->color());
254 x_parent->setColor(QMapNodeBase::Black);
255 if (w->right)
256 w->right->setColor(QMapNodeBase::Black);
257 rotateLeft(x: x_parent);
258 break;
259 }
260 } else {
261 QMapNodeBase *w = x_parent->left;
262 if (w->color() == QMapNodeBase::Red) {
263 w->setColor(QMapNodeBase::Black);
264 x_parent->setColor(QMapNodeBase::Red);
265 rotateRight(x: x_parent);
266 w = x_parent->left;
267 }
268 if ((w->right == nullptr || w->right->color() == QMapNodeBase::Black) &&
269 (w->left == nullptr|| w->left->color() == QMapNodeBase::Black)) {
270 w->setColor(QMapNodeBase::Red);
271 x = x_parent;
272 x_parent = x_parent->parent();
273 } else {
274 if (w->left == nullptr || w->left->color() == QMapNodeBase::Black) {
275 if (w->right)
276 w->right->setColor(QMapNodeBase::Black);
277 w->setColor(QMapNodeBase::Red);
278 rotateLeft(x: w);
279 w = x_parent->left;
280 }
281 w->setColor(x_parent->color());
282 x_parent->setColor(QMapNodeBase::Black);
283 if (w->left)
284 w->left->setColor(QMapNodeBase::Black);
285 rotateRight(x: x_parent);
286 break;
287 }
288 }
289 }
290 if (x)
291 x->setColor(QMapNodeBase::Black);
292 }
293 free(ptr: y);
294 --size;
295}
296
297void QMapDataBase::recalcMostLeftNode()
298{
299 mostLeftNode = &header;
300 while (mostLeftNode->left)
301 mostLeftNode = mostLeftNode->left;
302}
303
304static inline int qMapAlignmentThreshold()
305{
306 // malloc on 32-bit platforms should return pointers that are 8-byte
307 // aligned or more while on 64-bit platforms they should be 16-byte aligned
308 // or more
309 return 2 * sizeof(void*);
310}
311
312static inline void *qMapAllocate(int alloc, int alignment)
313{
314 return alignment > qMapAlignmentThreshold()
315 ? qMallocAligned(size: alloc, alignment)
316 : ::malloc(size: alloc);
317}
318
319static inline void qMapDeallocate(QMapNodeBase *node, int alignment)
320{
321 if (alignment > qMapAlignmentThreshold())
322 qFreeAligned(ptr: node);
323 else
324 ::free(ptr: node);
325}
326
327QMapNodeBase *QMapDataBase::createNode(int alloc, int alignment, QMapNodeBase *parent, bool left)
328{
329 QMapNodeBase *node = static_cast<QMapNodeBase *>(qMapAllocate(alloc, alignment));
330 Q_CHECK_PTR(node);
331
332 memset(s: node, c: 0, n: alloc);
333 ++size;
334
335 if (parent) {
336 if (left) {
337 parent->left = node;
338 if (parent == mostLeftNode)
339 mostLeftNode = node;
340 } else {
341 parent->right = node;
342 }
343 node->setParent(parent);
344 rebalance(x: node);
345 }
346 return node;
347}
348
349void QMapDataBase::freeTree(QMapNodeBase *root, int alignment)
350{
351 if (root->left)
352 freeTree(root: root->left, alignment);
353 if (root->right)
354 freeTree(root: root->right, alignment);
355 qMapDeallocate(node: root, alignment);
356}
357
358QMapDataBase *QMapDataBase::createData()
359{
360 QMapDataBase *d = new QMapDataBase;
361
362 d->ref.initializeOwned();
363 d->size = 0;
364
365 d->header.p = 0;
366 d->header.left = nullptr;
367 d->header.right = nullptr;
368 d->mostLeftNode = &(d->header);
369
370 return d;
371}
372
373void QMapDataBase::freeData(QMapDataBase *d)
374{
375 delete d;
376}
377
378/*!
379 \class QMap
380 \inmodule QtCore
381 \brief The QMap class is a template class that provides a red-black-tree-based dictionary.
382
383 \ingroup tools
384 \ingroup shared
385
386 \reentrant
387
388 QMap\<Key, T\> is one of Qt's generic \l{container classes}. It
389 stores (key, value) pairs and provides fast lookup of the
390 value associated with a key.
391
392 QMap and QHash provide very similar functionality. The
393 differences are:
394
395 \list
396 \li QHash provides average faster lookups than QMap. (See \l{Algorithmic
397 Complexity} for details.)
398 \li When iterating over a QHash, the items are arbitrarily ordered.
399 With QMap, the items are always sorted by key.
400 \li The key type of a QHash must provide operator==() and a global
401 qHash(Key) function. The key type of a QMap must provide
402 operator<() specifying a total order. Since Qt 5.8.1 it is also safe
403 to use a pointer type as key, even if the underlying operator<()
404 does not provide a total order.
405 \endlist
406
407 Here's an example QMap with QString keys and \c int values:
408 \snippet code/src_corelib_tools_qmap.cpp 0
409
410 To insert a (key, value) pair into the map, you can use operator[]():
411
412 \snippet code/src_corelib_tools_qmap.cpp 1
413
414 This inserts the following three (key, value) pairs into the
415 QMap: ("one", 1), ("three", 3), and ("seven", 7). Another way to
416 insert items into the map is to use insert():
417
418 \snippet code/src_corelib_tools_qmap.cpp 2
419
420 To look up a value, use operator[]() or value():
421
422 \snippet code/src_corelib_tools_qmap.cpp 3
423
424 If there is no item with the specified key in the map, these
425 functions return a \l{default-constructed value}.
426
427 If you want to check whether the map contains a certain key, use
428 contains():
429
430 \snippet code/src_corelib_tools_qmap.cpp 4
431
432 There is also a value() overload that uses its second argument as
433 a default value if there is no item with the specified key:
434
435 \snippet code/src_corelib_tools_qmap.cpp 5
436
437 In general, we recommend that you use contains() and value()
438 rather than operator[]() for looking up a key in a map. The
439 reason is that operator[]() silently inserts an item into the
440 map if no item exists with the same key (unless the map is
441 const). For example, the following code snippet will create 1000
442 items in memory:
443
444 \snippet code/src_corelib_tools_qmap.cpp 6
445
446 To avoid this problem, replace \c map[i] with \c map.value(i)
447 in the code above.
448
449 If you want to navigate through all the (key, value) pairs stored
450 in a QMap, you can use an iterator. QMap provides both
451 \l{Java-style iterators} (QMapIterator and QMutableMapIterator)
452 and \l{STL-style iterators} (QMap::const_iterator and
453 QMap::iterator). Here's how to iterate over a QMap<QString, int>
454 using a Java-style iterator:
455
456 \snippet code/src_corelib_tools_qmap.cpp 7
457
458 Here's the same code, but using an STL-style iterator this time:
459
460 \snippet code/src_corelib_tools_qmap.cpp 8
461
462 The items are traversed in ascending key order.
463
464 Normally, a QMap allows only one value per key. If you call
465 insert() with a key that already exists in the QMap, the
466 previous value will be erased. For example:
467
468 \snippet code/src_corelib_tools_qmap.cpp 9
469
470 However, you can store multiple values per key by using
471 using the subclass QMultiMap. If you want
472 to retrieve all the values for a single key, you can use
473 values(const Key &key), which returns a QList<T>:
474
475 \snippet code/src_corelib_tools_qmap.cpp 10
476
477 The items that share the same key are available from most
478 recently to least recently inserted. Another approach is to call
479 find() to get the STL-style iterator for the first item with a
480 key and iterate from there:
481
482 \snippet code/src_corelib_tools_qmap.cpp 11
483
484 If you only need to extract the values from a map (not the keys),
485 you can also use \l{foreach}:
486
487 \snippet code/src_corelib_tools_qmap.cpp 12
488
489 Items can be removed from the map in several ways. One way is to
490 call remove(); this will remove any item with the given key.
491 Another way is to use QMutableMapIterator::remove(). In addition,
492 you can clear the entire map using clear().
493
494 QMap's key and value data types must be \l{assignable data
495 types}. This covers most data types you are likely to encounter,
496 but the compiler won't let you, for example, store a QWidget as a
497 value; instead, store a QWidget *. In addition, QMap's key type
498 must provide operator<(). QMap uses it to keep its items sorted,
499 and assumes that two keys \c x and \c y are equal if neither \c{x
500 < y} nor \c{y < x} is true.
501
502 Example:
503 \snippet code/src_corelib_tools_qmap.cpp 13
504
505 In the example, we start by comparing the employees' names. If
506 they're equal, we compare their dates of birth to break the tie.
507
508 \sa QMapIterator, QMutableMapIterator, QHash, QSet
509*/
510
511/*! \fn template <class Key, class T> QMap<Key, T>::QMap()
512
513 Constructs an empty map.
514
515 \sa clear()
516*/
517
518/*!
519 \fn template <class Key, class T> QMap<Key, T>::QMap(QMap<Key, T> &&other)
520
521 Move-constructs a QMap instance, making it point at the same
522 object that \a other was pointing to.
523
524 \since 5.2
525*/
526
527/*! \fn template <class Key, class T> QMap<Key, T>::QMap(const QMap<Key, T> &other)
528
529 Constructs a copy of \a other.
530
531 This operation occurs in \l{constant time}, because QMap is
532 \l{implicitly shared}. This makes returning a QMap from a
533 function very fast. If a shared instance is modified, it will be
534 copied (copy-on-write), and this takes \l{linear time}.
535
536 \sa operator=()
537*/
538
539/*! \fn template <class Key, class T> QMap<Key, T>::QMap(const typename std::map<Key, T> & other)
540
541 Constructs a copy of \a other.
542
543 \sa toStdMap()
544*/
545
546/*! \fn template <class Key, class T> QMap<Key, T>::QMap(std::initializer_list<std::pair<Key,T> > list)
547 \since 5.1
548
549 Constructs a map with a copy of each of the elements in the
550 initializer list \a list.
551
552 This function is only available if the program is being
553 compiled in C++11 mode.
554*/
555
556/*! \fn template <class Key, class T> std::map<Key, T> QMap<Key, T>::toStdMap() const
557
558 Returns an STL map equivalent to this QMap.
559*/
560
561/*! \fn template <class Key, class T> QMap<Key, T>::~QMap()
562
563 Destroys the map. References to the values in the map, and all
564 iterators over this map, become invalid.
565*/
566
567/*! \fn template <class Key, class T> QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other)
568
569 Assigns \a other to this map and returns a reference to this map.
570*/
571
572/*!
573 \fn template <class Key, class T> QMap<Key, T> &QMap<Key, T>::operator=(QMap<Key, T> &&other)
574
575 Move-assigns \a other to this QMap instance.
576
577 \since 5.2
578*/
579
580/*! \fn template <class Key, class T> void QMap<Key, T>::swap(QMap<Key, T> &other)
581 \since 4.8
582
583 Swaps map \a other with this map. This operation is very
584 fast and never fails.
585*/
586
587/*! \fn template <class Key, class T> void QMultiMap<Key, T>::swap(QMultiMap<Key, T> &other)
588 \since 4.8
589
590 Swaps map \a other with this map. This operation is very
591 fast and never fails.
592*/
593
594/*! \fn template <class Key, class T> bool QMap<Key, T>::operator==(const QMap<Key, T> &other) const
595
596 Returns \c true if \a other is equal to this map; otherwise returns
597 false.
598
599 Two maps are considered equal if they contain the same (key,
600 value) pairs.
601
602 This function requires the value type to implement \c
603 operator==().
604
605 \sa operator!=()
606*/
607
608/*! \fn template <class Key, class T> bool QMap<Key, T>::operator!=(const QMap<Key, T> &other) const
609
610 Returns \c true if \a other is not equal to this map; otherwise
611 returns \c false.
612
613 Two maps are considered equal if they contain the same (key,
614 value) pairs.
615
616 This function requires the value type to implement \c
617 operator==().
618
619 \sa operator==()
620*/
621
622/*! \fn template <class Key, class T> int QMap<Key, T>::size() const
623
624 Returns the number of (key, value) pairs in the map.
625
626 \sa isEmpty(), count()
627*/
628
629/*!
630 \fn template <class Key, class T> bool QMap<Key, T>::isEmpty() const
631
632 Returns \c true if the map contains no items; otherwise returns
633 false.
634
635 \sa size()
636*/
637
638/*! \fn template <class Key, class T> void QMap<Key, T>::detach()
639
640 \internal
641
642 Detaches this map from any other maps with which it may share
643 data.
644
645 \sa isDetached()
646*/
647
648/*! \fn template <class Key, class T> bool QMap<Key, T>::isDetached() const
649
650 \internal
651
652 Returns \c true if the map's internal data isn't shared with any
653 other map object; otherwise returns \c false.
654
655 \sa detach()
656*/
657
658/*! \fn template <class Key, class T> void QMap<Key, T>::setSharable(bool sharable)
659
660 \internal
661*/
662
663/*! \fn template <class Key, class T> bool QMap<Key, T>::isSharedWith(const QMap<Key, T> &other) const
664
665 \internal
666*/
667
668/*! \fn template <class Key, class T> void QMap<Key, T>::clear()
669
670 Removes all items from the map.
671
672 \sa remove()
673*/
674
675/*! \fn template <class Key, class T> int QMap<Key, T>::remove(const Key &key)
676
677 Removes all the items that have the key \a key from the map.
678 Returns the number of items removed which will be 1 if the key
679 exists in the map, and 0 otherwise.
680
681 \sa clear(), take(), QMultiMap::remove()
682*/
683
684/*! \fn template <class Key, class T> T QMap<Key, T>::take(const Key &key)
685
686 Removes the item with the key \a key from the map and returns
687 the value associated with it.
688
689 If the item does not exist in the map, the function simply
690 returns a \l{default-constructed value}. If there are multiple
691 items for \a key in the map, only the most recently inserted one
692 is removed and returned.
693
694 If you don't use the return value, remove() is more efficient.
695
696 \sa remove()
697*/
698
699/*! \fn template <class Key, class T> bool QMap<Key, T>::contains(const Key &key) const
700
701 Returns \c true if the map contains an item with key \a key;
702 otherwise returns \c false.
703
704 \sa count(), QMultiMap::contains()
705*/
706
707/*! \fn template <class Key, class T> const T QMap<Key, T>::value(const Key &key, const T &defaultValue) const
708
709 Returns the value associated with the key \a key.
710
711 If the map contains no item with key \a key, the function returns
712 \a defaultValue. If no \a defaultValue is specified, the function
713 returns a \l{default-constructed value}. If there are multiple
714 items for \a key in the map, the value of the most recently
715 inserted one is returned.
716
717 \sa key(), values(), contains(), operator[]()
718*/
719
720/*! \fn template <class Key, class T> T &QMap<Key, T>::operator[](const Key &key)
721
722 Returns the value associated with the key \a key as a modifiable
723 reference.
724
725 If the map contains no item with key \a key, the function inserts
726 a \l{default-constructed value} into the map with key \a key, and
727 returns a reference to it. If the map contains multiple items
728 with key \a key, this function returns a reference to the most
729 recently inserted value.
730
731 \sa insert(), value()
732*/
733
734/*! \fn template <class Key, class T> const T QMap<Key, T>::operator[](const Key &key) const
735
736 \overload
737
738 Same as value().
739*/
740
741/*! \fn template <class Key, class T> QList<Key> QMap<Key, T>::uniqueKeys() const
742 \since 4.2
743 \obsolete Use QMultiMap for storing multiple values with the same key.
744
745 Returns a list containing all the keys in the map in ascending
746 order. Keys that occur multiple times in the map (because items
747 were inserted with insertMulti(), or unite() was used) occur only
748 once in the returned list.
749
750 \sa QMultiMap::uniqueKeys()
751*/
752
753/*! \fn template <class Key, class T> QList<Key> QMap<Key, T>::keys() const
754
755 Returns a list containing all the keys in the map in ascending
756 order. Keys that occur multiple times in the map (because the
757 method is operating on a QMultiMap) also occur multiple times
758 in the list.
759
760 The order is guaranteed to be the same as that used by values().
761
762 \sa QMultiMap::uniqueKeys(), values(), key()
763*/
764
765/*! \fn template <class Key, class T> QList<Key> QMap<Key, T>::keys(const T &value) const
766
767 \overload
768
769 Returns a list containing all the keys associated with value \a
770 value in ascending order.
771
772 This function can be slow (\l{linear time}), because QMap's
773 internal data structure is optimized for fast lookup by key, not
774 by value.
775*/
776
777/*!
778 \fn template <class Key, class T> Key QMap<Key, T>::key(const T &value, const Key &defaultKey) const
779 \since 4.3
780 \overload
781
782 Returns the first key with value \a value, or \a defaultKey if
783 the map contains no item with value \a value. If no \a defaultKey
784 is provided the function returns a
785 \l{default-constructed value}{default-constructed key}.
786
787 This function can be slow (\l{linear time}), because QMap's
788 internal data structure is optimized for fast lookup by key, not
789 by value.
790
791 \sa value(), keys()
792*/
793
794/*! \fn template <class Key, class T> QList<T> QMap<Key, T>::values() const
795
796 Returns a list containing all the values in the map, in ascending
797 order of their keys. If a key is associated with multiple values,
798 all of its values will be in the list, and not just the most
799 recently inserted one.
800
801 \sa keys(), value()
802*/
803
804/*! \fn template <class Key, class T> QList<T> QMap<Key, T>::values(const Key &key) const
805 \overload
806 \obsolete Use QMultiMap for maps storing multiple values with the same key.
807
808 Returns a list containing all the values associated with key
809 \a key, from the most recently inserted to the least recently
810 inserted one.
811
812 \sa QMultiMap::values()
813*/
814
815/*! \fn template <class Key, class T> int QMap<Key, T>::count(const Key &key) const
816
817 Returns the number of items associated with key \a key.
818
819 \sa contains(), QMultiMap::count()
820*/
821
822/*! \fn template <class Key, class T> int QMap<Key, T>::count() const
823
824 \overload
825
826 Same as size().
827*/
828
829/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::begin()
830
831 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in
832 the map.
833
834 \sa constBegin(), end()
835*/
836
837/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::begin() const
838
839 \overload
840*/
841
842/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::cbegin() const
843 \since 5.0
844
845 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
846 in the map.
847
848 \sa begin(), cend()
849*/
850
851/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::constBegin() const
852
853 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
854 in the map.
855
856 \sa begin(), constEnd()
857*/
858
859/*! \fn template <class Key, class T> QMap<Key, T>::key_iterator QMap<Key, T>::keyBegin() const
860 \since 5.6
861
862 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first key
863 in the map.
864
865 \sa keyEnd(), firstKey()
866*/
867
868/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::end()
869
870 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item
871 after the last item in the map.
872
873 \sa begin(), constEnd()
874*/
875
876/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::end() const
877
878 \overload
879*/
880
881/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::cend() const
882 \since 5.0
883
884 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
885 item after the last item in the map.
886
887 \sa cbegin(), end()
888*/
889
890/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::constEnd() const
891
892 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
893 item after the last item in the map.
894
895 \sa constBegin(), end()
896*/
897
898/*! \fn template <class Key, class T> QMap<Key, T>::key_iterator QMap<Key, T>::keyEnd() const
899 \since 5.6
900
901 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
902 item after the last key in the map.
903
904 \sa keyBegin(), lastKey()
905*/
906
907
908/*! \fn template <class Key, class T> QMap<Key, T>::key_value_iterator QMap<Key, T>::keyValueBegin()
909 \since 5.10
910
911 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first entry
912 in the map.
913
914 \sa keyValueEnd()
915*/
916
917/*! \fn template <class Key, class T> QMap<Key, T>::key_value_iterator QMap<Key, T>::keyValueEnd()
918 \since 5.10
919
920 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
921 entry after the last entry in the map.
922
923 \sa keyValueBegin()
924*/
925
926/*! \fn template <class Key, class T> QMap<Key, T>::const_key_value_iterator QMap<Key, T>::keyValueBegin() const
927 \since 5.10
928
929 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
930 in the map.
931
932 \sa keyValueEnd()
933*/
934
935/*! \fn template <class Key, class T> QMap<Key, T>::const_key_value_iterator QMap<Key, T>::constKeyValueBegin() const
936 \since 5.10
937
938 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
939 in the map.
940
941 \sa keyValueBegin()
942*/
943
944/*! \fn template <class Key, class T> QMap<Key, T>::const_key_value_iterator QMap<Key, T>::keyValueEnd() const
945 \since 5.10
946
947 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
948 entry after the last entry in the map.
949
950 \sa keyValueBegin()
951*/
952
953/*! \fn template <class Key, class T> QMap<Key, T>::const_key_value_iterator QMap<Key, T>::constKeyValueEnd() const
954 \since 5.10
955
956 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
957 entry after the last entry in the map.
958
959 \sa constKeyValueBegin()
960*/
961
962/*! \fn template <class Key, class T> const Key &QMap<Key, T>::firstKey() const
963 \since 5.2
964
965 Returns a reference to the smallest key in the map.
966 This function assumes that the map is not empty.
967
968 This executes in \l{constant time}.
969
970 \sa lastKey(), first(), keyBegin(), isEmpty()
971*/
972
973/*! \fn template <class Key, class T> const Key &QMap<Key, T>::lastKey() const
974 \since 5.2
975
976 Returns a reference to the largest key in the map.
977 This function assumes that the map is not empty.
978
979 This executes in \l{logarithmic time}.
980
981 \sa firstKey(), last(), keyEnd(), isEmpty()
982*/
983
984/*! \fn template <class Key, class T> T &QMap<Key, T>::first()
985 \since 5.2
986
987 Returns a reference to the first value in the map, that is the value mapped
988 to the smallest key. This function assumes that the map is not empty.
989
990 When unshared (or const version is called), this executes in \l{constant time}.
991
992 \sa last(), firstKey(), isEmpty()
993*/
994
995/*! \fn template <class Key, class T> const T &QMap<Key, T>::first() const
996 \since 5.2
997
998 \overload
999*/
1000
1001/*! \fn template <class Key, class T> T &QMap<Key, T>::last()
1002 \since 5.2
1003
1004 Returns a reference to the last value in the map, that is the value mapped
1005 to the largest key. This function assumes that the map is not empty.
1006
1007 When unshared (or const version is called), this executes in \l{logarithmic time}.
1008
1009 \sa first(), lastKey(), isEmpty()
1010*/
1011
1012/*! \fn template <class Key, class T> const T &QMap<Key, T>::last() const
1013 \since 5.2
1014
1015 \overload
1016*/
1017
1018/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::erase(iterator pos)
1019
1020 Removes the (key, value) pair pointed to by the iterator \a pos
1021 from the map, and returns an iterator to the next item in the
1022 map.
1023
1024 \sa remove()
1025*/
1026
1027/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::find(const Key &key)
1028
1029 Returns an iterator pointing to the item with key \a key in the
1030 map.
1031
1032 If the map contains no item with key \a key, the function
1033 returns end().
1034
1035 If the map contains multiple items with key \a key, this
1036 function returns an iterator that points to the most recently
1037 inserted value. The other values are accessible by incrementing
1038 the iterator. For example, here's some code that iterates over all
1039 the items with the same key:
1040
1041 \snippet code/src_corelib_tools_qmap.cpp 14
1042
1043 \sa constFind(), value(), values(), lowerBound(), upperBound(), QMultiMap::find()
1044*/
1045
1046/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &key) const
1047
1048 \overload
1049*/
1050
1051/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::constFind(const Key &key) const
1052 \since 4.1
1053
1054 Returns an const iterator pointing to the item with key \a key in the
1055 map.
1056
1057 If the map contains no item with key \a key, the function
1058 returns constEnd().
1059
1060 \sa find(), QMultiMap::constFind()
1061*/
1062
1063/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::lowerBound(const Key &key)
1064
1065 Returns an iterator pointing to the first item with key \a key in
1066 the map. If the map contains no item with key \a key, the
1067 function returns an iterator to the nearest item with a greater
1068 key.
1069
1070 Example:
1071 \snippet code/src_corelib_tools_qmap.cpp 15
1072
1073 If the map contains multiple items with key \a key, this
1074 function returns an iterator that points to the most recently
1075 inserted value. The other values are accessible by incrementing
1076 the iterator. For example, here's some code that iterates over all
1077 the items with the same key:
1078
1079 \snippet code/src_corelib_tools_qmap.cpp 16
1080
1081 \sa upperBound(), find()
1082*/
1083
1084/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::lowerBound(const Key &key) const
1085
1086 \overload
1087*/
1088
1089/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::upperBound(const Key &key)
1090
1091 Returns an iterator pointing to the item that immediately follows
1092 the last item with key \a key in the map. If the map contains no
1093 item with key \a key, the function returns an iterator to the
1094 nearest item with a greater key.
1095
1096 Example:
1097 \snippet code/src_corelib_tools_qmap.cpp 17
1098
1099 \sa lowerBound(), find()
1100*/
1101
1102/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::upperBound(const Key &key) const
1103
1104 \overload
1105*/
1106
1107/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &key, const T &value)
1108
1109 Inserts a new item with the key \a key and a value of \a value.
1110
1111 If there is already an item with the key \a key, that item's value
1112 is replaced with \a value.
1113
1114 If there are multiple items with the key \a key, the most
1115 recently inserted item's value is replaced with \a value.
1116
1117 \sa QMultiMap::insert()
1118*/
1119
1120/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::insert(const_iterator pos, const Key &key, const T &value)
1121 \overload
1122 \since 5.1
1123 Inserts a new item with the key \a key and value \a value and with hint \a pos
1124 suggesting where to do the insert.
1125
1126 If constBegin() is used as hint it indicates that the \a key is less than any key in the map
1127 while constEnd() suggests that the \a key is (strictly) larger than any key in the map.
1128 Otherwise the hint should meet the condition (\a pos - 1).key() < \a key <= pos.key().
1129 If the hint \a pos is wrong it is ignored and a regular insert is done.
1130
1131 If there is already an item with the key \a key, that item's value
1132 is replaced with \a value.
1133
1134 If there are multiple items with the key \a key, then exactly one of them
1135 is replaced with \a value.
1136
1137 If the hint is correct and the map is unshared, the insert executes in amortized \l{constant time}.
1138
1139 When creating a map from sorted data inserting the largest key first with constBegin()
1140 is faster than inserting in sorted order with constEnd(), since constEnd() - 1 (which is needed
1141 to check if the hint is valid) needs \l{logarithmic time}.
1142
1143 \b {Note:} Be careful with the hint. Providing an iterator from an older shared instance might
1144 crash but there is also a risk that it will silently corrupt both the map and the \a pos map.
1145
1146 \sa QMultiMap::insert()
1147*/
1148
1149/*! \fn template <class Key, class T> void QMap<Key, T>::insert(const QMap<Key, T> &map)
1150 \since 5.15
1151
1152 Inserts all the items in \a map into this map.
1153
1154 If a key is common to both maps, its value will be replaced with
1155 the value stored in \a map.
1156
1157 \note If \a map contains multiple entries with the same key then the
1158 final value of the key is undefined.
1159
1160 \sa QMultiMap::insert()
1161*/
1162
1163/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &key, const T &value)
1164 \obsolete Use QMultiMap for storing multiple values with the same key.
1165
1166 Inserts a new item with the key \a key and a value of \a value.
1167
1168 If there is already an item with the same key in the map, this
1169 function will simply create a new one. (This behavior is
1170 different from insert(), which overwrites the value of an
1171 existing item.)
1172
1173 \sa QMultiMap::insert()
1174*/
1175
1176/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const_iterator pos, const Key &key, const T &value)
1177 \overload
1178 \since 5.1
1179 \obsolete Use QMultiMap for storing multiple values with the same key.
1180 Inserts a new item with the key \a key and value \a value and with hint \a pos
1181 suggesting where to do the insert.
1182
1183 If constBegin() is used as hint it indicates that the \a key is less than any key in the map
1184 while constEnd() suggests that the \a key is larger than any key in the map.
1185 Otherwise the hint should meet the condition (\a pos - 1).key() < \a key <= pos.key().
1186 If the hint \a pos is wrong it is ignored and a regular insertMulti is done.
1187
1188 If there is already an item with the same key in the map, this function will simply create a new one.
1189
1190 \b {Note:} Be careful with the hint. Providing an iterator from an older shared instance might
1191 crash but there is also a risk that it will silently corrupt both the map and the \a pos map.
1192
1193 \sa QMultiMap::insert()
1194*/
1195
1196
1197/*! \fn template <class Key, class T> QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other)
1198 \obsolete Use QMultiMap for storing multiple values with the same key.
1199
1200 Inserts all the items in the \a other map into this map. If a
1201 key is common to both maps, the resulting map will contain the
1202 key multiple times.
1203
1204 \sa QMultiMap::unite()
1205*/
1206
1207/*! \typedef QMap::Iterator
1208
1209 Qt-style synonym for QMap<Key, T>::iterator.
1210*/
1211
1212/*! \typedef QMap::ConstIterator
1213
1214 Qt-style synonym for QMap<Key, T>::const_iterator.
1215*/
1216
1217/*! \typedef QMap::difference_type
1218
1219 Typedef for ptrdiff_t. Provided for STL compatibility.
1220*/
1221
1222/*! \typedef QMap::key_type
1223
1224 Typedef for Key. Provided for STL compatibility.
1225*/
1226
1227/*! \typedef QMap::mapped_type
1228
1229 Typedef for T. Provided for STL compatibility.
1230*/
1231
1232/*! \typedef QMap::size_type
1233
1234 Typedef for int. Provided for STL compatibility.
1235*/
1236
1237/*!
1238 \fn template <class Key, class T> bool QMap<Key, T>::empty() const
1239
1240 This function is provided for STL compatibility. It is equivalent
1241 to isEmpty(), returning true if the map is empty; otherwise
1242 returning false.
1243*/
1244
1245/*!
1246 \fn template <class Key, class T> QPair<typename QMap<Key, T>::iterator, typename QMap<Key, T>::iterator> QMap<Key, T>::equal_range(const Key &key)
1247
1248 Returns a pair of iterators delimiting the range of values \c{[first, second)}, that
1249 are stored under \a key.
1250*/
1251
1252/*!
1253 \fn template <class Key, class T> QPair<typename QMap<Key, T>::const_iterator, typename QMap<Key, T>::const_iterator> QMap<Key, T>::equal_range(const Key &key) const
1254 \overload
1255 \since 5.6
1256*/
1257
1258
1259/*! \class QMap::iterator
1260 \inmodule QtCore
1261 \brief The QMap::iterator class provides an STL-style non-const iterator for QMap and QMultiMap.
1262
1263 QMap features both \l{STL-style iterators} and \l{Java-style
1264 iterators}. The STL-style iterators are more low-level and more
1265 cumbersome to use; on the other hand, they are slightly faster
1266 and, for developers who already know STL, have the advantage of
1267 familiarity.
1268
1269 QMap\<Key, T\>::iterator allows you to iterate over a QMap (or
1270 QMultiMap) and to modify the value (but not the key) stored under
1271 a particular key. If you want to iterate over a const QMap, you
1272 should use QMap::const_iterator. It is generally good practice to
1273 use QMap::const_iterator on a non-const QMap as well, unless you
1274 need to change the QMap through the iterator. Const iterators are
1275 slightly faster, and can improve code readability.
1276
1277 The default QMap::iterator constructor creates an uninitialized
1278 iterator. You must initialize it using a QMap function like
1279 QMap::begin(), QMap::end(), or QMap::find() before you can
1280 start iterating. Here's a typical loop that prints all the (key,
1281 value) pairs stored in a map:
1282
1283 \snippet code/src_corelib_tools_qmap.cpp 18
1284
1285 Unlike QHash, which stores its items in an arbitrary order, QMap
1286 stores its items ordered by key. Items that share the same key
1287 (because the map is a QMultiMap) will appear consecutively,
1288 from the most recently to the least recently inserted value.
1289
1290 Let's see a few examples of things we can do with a
1291 QMap::iterator that we cannot do with a QMap::const_iterator.
1292 Here's an example that increments every value stored in the QMap
1293 by 2:
1294
1295 \snippet code/src_corelib_tools_qmap.cpp 19
1296
1297 Here's an example that removes all the items whose key is a
1298 string that starts with an underscore character:
1299
1300 \snippet code/src_corelib_tools_qmap.cpp 20
1301
1302 The call to QMap::erase() removes the item pointed to by the
1303 iterator from the map, and returns an iterator to the next item.
1304 Here's another way of removing an item while iterating:
1305
1306 \snippet code/src_corelib_tools_qmap.cpp 21
1307
1308 It might be tempting to write code like this:
1309
1310 \snippet code/src_corelib_tools_qmap.cpp 22
1311
1312 However, this will potentially crash in \c{++i}, because \c i is
1313 a dangling iterator after the call to erase().
1314
1315 Multiple iterators can be used on the same map. If you add items
1316 to the map, existing iterators will remain valid. If you remove
1317 items from the map, iterators that point to the removed items
1318 will become dangling iterators.
1319
1320 \warning Iterators on implicitly shared containers do not work
1321 exactly like STL-iterators. You should avoid copying a container
1322 while iterators are active on that container. For more information,
1323 read \l{Implicit sharing iterator problem}.
1324
1325 \sa QMap::const_iterator, QMap::key_iterator, QMutableMapIterator
1326*/
1327
1328/*! \typedef QMap::iterator::difference_type
1329
1330 \internal
1331*/
1332
1333/*! \typedef QMap::iterator::iterator_category
1334
1335 A synonym for \e {std::bidirectional_iterator_tag} indicating
1336 this iterator is a bidirectional iterator.
1337*/
1338
1339/*! \typedef QMap::iterator::pointer
1340
1341 \internal
1342*/
1343
1344/*! \typedef QMap::iterator::reference
1345
1346 \internal
1347*/
1348
1349/*! \typedef QMap::iterator::value_type
1350
1351 \internal
1352*/
1353
1354/*! \fn template <class Key, class T> QMap<Key, T>::iterator::iterator()
1355
1356 Constructs an uninitialized iterator.
1357
1358 Functions like key(), value(), and operator++() must not be
1359 called on an uninitialized iterator. Use operator=() to assign a
1360 value to it before using it.
1361
1362 \sa QMap::begin(), QMap::end()
1363*/
1364
1365/*! \fn template <class Key, class T> QMap<Key, T>::iterator::iterator(Node *)
1366
1367 \internal
1368*/
1369
1370/*! \fn template <class Key, class T> const Key &QMap<Key, T>::iterator::key() const
1371
1372 Returns the current item's key as a const reference.
1373
1374 There is no direct way of changing an item's key through an
1375 iterator, although it can be done by calling QMap::erase()
1376 followed by QMap::insert() or QMap::insertMulti().
1377
1378 \sa value()
1379*/
1380
1381/*! \fn template <class Key, class T> T &QMap<Key, T>::iterator::value() const
1382
1383 Returns a modifiable reference to the current item's value.
1384
1385 You can change the value of an item by using value() on
1386 the left side of an assignment, for example:
1387
1388 \snippet code/src_corelib_tools_qmap.cpp 23
1389
1390 \sa key(), operator*()
1391*/
1392
1393/*! \fn template <class Key, class T> T &QMap<Key, T>::iterator::operator*() const
1394
1395 Returns a modifiable reference to the current item's value.
1396
1397 Same as value().
1398
1399 \sa key()
1400*/
1401
1402/*! \fn template <class Key, class T> T *QMap<Key, T>::iterator::operator->() const
1403
1404 Returns a pointer to the current item's value.
1405
1406 \sa value()
1407*/
1408
1409/*!
1410 \fn template <class Key, class T> bool QMap<Key, T>::iterator::operator==(const iterator &other) const
1411 \fn template <class Key, class T> bool QMap<Key, T>::iterator::operator==(const const_iterator &other) const
1412
1413 Returns \c true if \a other points to the same item as this
1414 iterator; otherwise returns \c false.
1415
1416 \sa operator!=()
1417*/
1418
1419/*!
1420 \fn template <class Key, class T> bool QMap<Key, T>::iterator::operator!=(const iterator &other) const
1421 \fn template <class Key, class T> bool QMap<Key, T>::iterator::operator!=(const const_iterator &other) const
1422
1423 Returns \c true if \a other points to a different item than this
1424 iterator; otherwise returns \c false.
1425
1426 \sa operator==()
1427*/
1428
1429/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator++()
1430
1431 The prefix ++ operator (\c{++i}) advances the iterator to the
1432 next item in the map and returns an iterator to the new current
1433 item.
1434
1435 Calling this function on QMap::end() leads to undefined results.
1436
1437 \sa operator--()
1438*/
1439
1440/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator++(int)
1441
1442 \overload
1443
1444 The postfix ++ operator (\c{i++}) advances the iterator to the
1445 next item in the map and returns an iterator to the previously
1446 current item.
1447*/
1448
1449/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator--()
1450
1451 The prefix -- operator (\c{--i}) makes the preceding item
1452 current and returns an iterator pointing to the new current item.
1453
1454 Calling this function on QMap::begin() leads to undefined
1455 results.
1456
1457 \sa operator++()
1458*/
1459
1460/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator--(int)
1461
1462 \overload
1463
1464 The postfix -- operator (\c{i--}) makes the preceding item
1465 current and returns an iterator pointing to the previously
1466 current item.
1467*/
1468
1469/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator+(int j) const
1470
1471 Returns an iterator to the item at \a j positions forward from
1472 this iterator. (If \a j is negative, the iterator goes backward.)
1473
1474 This operation can be slow for large \a j values.
1475
1476 \sa operator-()
1477
1478*/
1479
1480/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator-(int j) const
1481
1482 Returns an iterator to the item at \a j positions backward from
1483 this iterator. (If \a j is negative, the iterator goes forward.)
1484
1485 This operation can be slow for large \a j values.
1486
1487 \sa operator+()
1488*/
1489
1490/*! \fn template <class Key, class T> QMap<Key, T>::iterator &QMap<Key, T>::iterator::operator+=(int j)
1491
1492 Advances the iterator by \a j items. (If \a j is negative, the
1493 iterator goes backward.)
1494
1495 \sa operator-=(), operator+()
1496*/
1497
1498/*! \fn template <class Key, class T> QMap<Key, T>::iterator &QMap<Key, T>::iterator::operator-=(int j)
1499
1500 Makes the iterator go back by \a j items. (If \a j is negative,
1501 the iterator goes forward.)
1502
1503 \sa operator+=(), operator-()
1504*/
1505
1506/*! \class QMap::const_iterator
1507 \inmodule QtCore
1508 \brief The QMap::const_iterator class provides an STL-style const iterator for QMap and QMultiMap.
1509
1510 QMap features both \l{STL-style iterators} and \l{Java-style
1511 iterators}. The STL-style iterators are more low-level and more
1512 cumbersome to use; on the other hand, they are slightly faster
1513 and, for developers who already know STL, have the advantage of
1514 familiarity.
1515
1516 QMap\<Key, T\>::const_iterator allows you to iterate over a QMap
1517 (or a QMultiMap). If you want to modify the QMap as you iterate
1518 over it, you must use QMap::iterator instead. It is generally
1519 good practice to use QMap::const_iterator on a non-const QMap as
1520 well, unless you need to change the QMap through the iterator.
1521 Const iterators are slightly faster, and can improve code
1522 readability.
1523
1524 The default QMap::const_iterator constructor creates an
1525 uninitialized iterator. You must initialize it using a QMap
1526 function like QMap::constBegin(), QMap::constEnd(), or
1527 QMap::find() before you can start iterating. Here's a typical
1528 loop that prints all the (key, value) pairs stored in a map:
1529
1530 \snippet code/src_corelib_tools_qmap.cpp 24
1531
1532 Unlike QHash, which stores its items in an arbitrary order, QMap
1533 stores its items ordered by key. Items that share the same key
1534 (because the map is a QMultiMap) will appear consecutively,
1535 from the most recently to the least recently inserted value.
1536
1537 Multiple iterators can be used on the same map. If you add items
1538 to the map, existing iterators will remain valid. If you remove
1539 items from the map, iterators that point to the removed items
1540 will become dangling iterators.
1541
1542 \warning Iterators on implicitly shared containers do not work
1543 exactly like STL-iterators. You should avoid copying a container
1544 while iterators are active on that container. For more information,
1545 read \l{Implicit sharing iterator problem}.
1546
1547 \sa QMap::iterator, QMap::key_iterator, QMapIterator
1548*/
1549
1550/*! \typedef QMap::const_iterator::difference_type
1551
1552 \internal
1553*/
1554
1555/*! \typedef QMap::const_iterator::iterator_category
1556
1557 A synonym for \e {std::bidirectional_iterator_tag} indicating
1558 this iterator is a bidirectional iterator.
1559*/
1560
1561/*! \typedef QMap::const_iterator::pointer
1562
1563 \internal
1564*/
1565
1566/*! \typedef QMap::const_iterator::reference
1567
1568 \internal
1569*/
1570
1571/*! \typedef QMap::const_iterator::value_type
1572
1573 \internal
1574*/
1575
1576/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator::const_iterator()
1577
1578 Constructs an uninitialized iterator.
1579
1580 Functions like key(), value(), and operator++() must not be
1581 called on an uninitialized iterator. Use operator=() to assign a
1582 value to it before using it.
1583
1584 \sa QMap::constBegin(), QMap::constEnd()
1585*/
1586
1587/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator::const_iterator(const Node *)
1588
1589 \internal
1590*/
1591
1592/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator::const_iterator(const iterator &other)
1593
1594 Constructs a copy of \a other.
1595*/
1596
1597/*! \fn template <class Key, class T> const Key &QMap<Key, T>::const_iterator::key() const
1598
1599 Returns the current item's key.
1600
1601 \sa value()
1602*/
1603
1604/*! \fn template <class Key, class T> const T &QMap<Key, T>::const_iterator::value() const
1605
1606 Returns the current item's value.
1607
1608 \sa key(), operator*()
1609*/
1610
1611/*! \fn template <class Key, class T> const T &QMap<Key, T>::const_iterator::operator*() const
1612
1613 Returns the current item's value.
1614
1615 Same as value().
1616
1617 \sa key()
1618*/
1619
1620/*! \fn template <class Key, class T> const T *QMap<Key, T>::const_iterator::operator->() const
1621
1622 Returns a pointer to the current item's value.
1623
1624 \sa value()
1625*/
1626
1627/*! \fn template <class Key, class T> bool QMap<Key, T>::const_iterator::operator==(const const_iterator &other) const
1628
1629 Returns \c true if \a other points to the same item as this
1630 iterator; otherwise returns \c false.
1631
1632 \sa operator!=()
1633*/
1634
1635/*! \fn template <class Key, class T> bool QMap<Key, T>::const_iterator::operator!=(const const_iterator &other) const
1636
1637 Returns \c true if \a other points to a different item than this
1638 iterator; otherwise returns \c false.
1639
1640 \sa operator==()
1641*/
1642
1643/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::const_iterator::operator++()
1644
1645 The prefix ++ operator (\c{++i}) advances the iterator to the
1646 next item in the map and returns an iterator to the new current
1647 item.
1648
1649 Calling this function on QMap::end() leads to undefined results.
1650
1651 \sa operator--()
1652*/
1653
1654/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::const_iterator::operator++(int)
1655
1656 \overload
1657
1658 The postfix ++ operator (\c{i++}) advances the iterator to the
1659 next item in the map and returns an iterator to the previously
1660 current item.
1661*/
1662
1663/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator &QMap<Key, T>::const_iterator::operator--()
1664
1665 The prefix -- operator (\c{--i}) makes the preceding item
1666 current and returns an iterator pointing to the new current item.
1667
1668 Calling this function on QMap::begin() leads to undefined
1669 results.
1670
1671 \sa operator++()
1672*/
1673
1674/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::const_iterator::operator--(int)
1675
1676 \overload
1677
1678 The postfix -- operator (\c{i--}) makes the preceding item
1679 current and returns an iterator pointing to the previously
1680 current item.
1681*/
1682
1683/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::const_iterator::operator+(int j) const
1684
1685 Returns an iterator to the item at \a j positions forward from
1686 this iterator. (If \a j is negative, the iterator goes backward.)
1687
1688 This operation can be slow for large \a j values.
1689
1690 \sa operator-()
1691*/
1692
1693/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::const_iterator::operator-(int j) const
1694
1695 Returns an iterator to the item at \a j positions backward from
1696 this iterator. (If \a j is negative, the iterator goes forward.)
1697
1698 This operation can be slow for large \a j values.
1699
1700 \sa operator+()
1701*/
1702
1703/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator &QMap<Key, T>::const_iterator::operator+=(int j)
1704
1705 Advances the iterator by \a j items. (If \a j is negative, the
1706 iterator goes backward.)
1707
1708 This operation can be slow for large \a j values.
1709
1710 \sa operator-=(), operator+()
1711*/
1712
1713/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator &QMap<Key, T>::const_iterator::operator-=(int j)
1714
1715 Makes the iterator go back by \a j items. (If \a j is negative,
1716 the iterator goes forward.)
1717
1718 This operation can be slow for large \a j values.
1719
1720 \sa operator+=(), operator-()
1721*/
1722
1723/*! \class QMap::key_iterator
1724 \inmodule QtCore
1725 \since 5.6
1726 \brief The QMap::key_iterator class provides an STL-style const iterator for QMap and QMultiMap keys.
1727
1728 QMap::key_iterator is essentially the same as QMap::const_iterator
1729 with the difference that operator*() and operator->() return a key
1730 instead of a value.
1731
1732 For most uses QMap::iterator and QMap::const_iterator should be used,
1733 you can easily access the key by calling QMap::iterator::key():
1734
1735 \snippet code/src_corelib_tools_qmap.cpp keyiterator1
1736
1737 However, to have interoperability between QMap's keys and STL-style
1738 algorithms we need an iterator that dereferences to a key instead
1739 of a value. With QMap::key_iterator we can apply an algorithm to a
1740 range of keys without having to call QMap::keys(), which is inefficient
1741 as it costs one QMap iteration and memory allocation to create a temporary
1742 QList.
1743
1744 \snippet code/src_corelib_tools_qmap.cpp keyiterator2
1745
1746 QMap::key_iterator is const, it's not possible to modify the key.
1747
1748 The default QMap::key_iterator constructor creates an uninitialized
1749 iterator. You must initialize it using a QMap function like
1750 QMap::keyBegin() or QMap::keyEnd().
1751
1752 \warning Iterators on implicitly shared containers do not work
1753 exactly like STL-iterators. You should avoid copying a container
1754 while iterators are active on that container. For more information,
1755 read \l{Implicit sharing iterator problem}.
1756
1757 \sa QMap::const_iterator, QMap::iterator
1758*/
1759
1760/*! \typedef QMap::key_iterator::difference_type
1761 \internal
1762*/
1763
1764/*! \typedef QMap::key_iterator::iterator_category
1765 \internal
1766*/
1767
1768/*! \typedef QMap::key_iterator::pointer
1769 \internal
1770*/
1771
1772/*! \typedef QMap::key_iterator::reference
1773 \internal
1774*/
1775
1776/*! \typedef QMap::key_iterator::value_type
1777 \internal
1778*/
1779
1780/*! \fn template <class Key, class T> const T &QMap<Key, T>::key_iterator::operator*() const
1781
1782 Returns the current item's key.
1783*/
1784
1785/*! \fn template <class Key, class T> const T *QMap<Key, T>::key_iterator::operator->() const
1786
1787 Returns a pointer to the current item's key.
1788*/
1789
1790/*! \fn template <class Key, class T> bool QMap<Key, T>::key_iterator::operator==(key_iterator other) const
1791
1792 Returns \c true if \a other points to the same item as this
1793 iterator; otherwise returns \c false.
1794
1795 \sa operator!=()
1796*/
1797
1798/*! \fn template <class Key, class T> bool QMap<Key, T>::key_iterator::operator!=(key_iterator other) const
1799
1800 Returns \c true if \a other points to a different item than this
1801 iterator; otherwise returns \c false.
1802
1803 \sa operator==()
1804*/
1805
1806/*!
1807 \fn template <class Key, class T> QMap<Key, T>::key_iterator &QMap<Key, T>::key_iterator::operator++()
1808
1809 The prefix ++ operator (\c{++i}) advances the iterator to the
1810 next item in the hash and returns an iterator to the new current
1811 item.
1812
1813 Calling this function on QMap::keyEnd() leads to undefined results.
1814
1815 \sa operator--()
1816*/
1817
1818/*! \fn template <class Key, class T> QMap<Key, T>::key_iterator QMap<Key, T>::key_iterator::operator++(int)
1819
1820 \overload
1821
1822 The postfix ++ operator (\c{i++}) advances the iterator to the
1823 next item in the hash and returns an iterator to the previous
1824 item.
1825*/
1826
1827/*! \fn template <class Key, class T> QMap<Key, T>::key_iterator &QMap<Key, T>::key_iterator::operator--()
1828
1829 The prefix -- operator (\c{--i}) makes the preceding item
1830 current and returns an iterator pointing to the new current item.
1831
1832 Calling this function on QMap::keyBegin() leads to undefined
1833 results.
1834
1835 \sa operator++()
1836*/
1837
1838/*! \fn template <class Key, class T> QMap<Key, T>::key_iterator QMap<Key, T>::key_iterator::operator--(int)
1839
1840 \overload
1841
1842 The postfix -- operator (\c{i--}) makes the preceding item
1843 current and returns an iterator pointing to the previous
1844 item.
1845*/
1846
1847/*! \fn template <class Key, class T> const_iterator QMap<Key, T>::key_iterator::base() const
1848 Returns the underlying const_iterator this key_iterator is based on.
1849*/
1850
1851/*! \typedef QMap::const_key_value_iterator
1852 \inmodule QtCore
1853 \since 5.10
1854 \brief The QMap::const_key_value_iterator typedef provides an STL-style iterator for QMap and QMultiMap.
1855
1856 QMap::const_key_value_iterator is essentially the same as QMap::const_iterator
1857 with the difference that operator*() returns a key/value pair instead of a
1858 value.
1859
1860 \sa QKeyValueIterator
1861*/
1862
1863/*! \typedef QMap::key_value_iterator
1864 \inmodule QtCore
1865 \since 5.10
1866 \brief The QMap::key_value_iterator typedef provides an STL-style iterator for QMap and QMultiMap.
1867
1868 QMap::key_value_iterator is essentially the same as QMap::iterator
1869 with the difference that operator*() returns a key/value pair instead of a
1870 value.
1871
1872 \sa QKeyValueIterator
1873*/
1874
1875/*! \fn template <class Key, class T> QDataStream &operator<<(QDataStream &out, const QMap<Key, T> &map)
1876 \relates QMap
1877
1878 Writes the map \a map to stream \a out.
1879
1880 This function requires the key and value types to implement \c
1881 operator<<().
1882
1883 \sa{Serializing Qt Data Types}{Format of the QDataStream operators}
1884*/
1885
1886/*! \fn template <class Key, class T> QDataStream &operator>>(QDataStream &in, QMap<Key, T> &map)
1887 \relates QMap
1888
1889 Reads a map from stream \a in into \a map.
1890
1891 This function requires the key and value types to implement \c
1892 operator>>().
1893
1894 \sa{Serializing Qt Data Types}{Format of the QDataStream operators}
1895*/
1896
1897/*! \class QMultiMap
1898 \inmodule QtCore
1899 \brief The QMultiMap class is a convenience QMap subclass that provides multi-valued maps.
1900
1901 \ingroup tools
1902 \ingroup shared
1903
1904 \reentrant
1905
1906 QMultiMap\<Key, T\> is one of Qt's generic \l{container classes}.
1907 It inherits QMap and extends it with a few functions
1908 that make it able to store multi-valued maps. A multi-valued map
1909 is a map that allows multiple values with the same key; QMap
1910 doesn't allow that.
1911
1912 Because QMultiMap inherits QMap, all of QMap's functionality also
1913 applies to QMultiMap. For example, you can use isEmpty() to test
1914 whether the map is empty, and you can traverse a QMultiMap using
1915 QMap's iterator classes (for example, QMapIterator). But in
1916 addition, it provides an insert() function that inserts but does
1917 not overwrite any previous value if the key already exists,
1918 and a replace() function that corresponds which does overwite
1919 an existing value if they key is already in the map.
1920 It also provides convenient operator+() and operator+=().
1921
1922 Example:
1923 \snippet code/src_corelib_tools_qmap.cpp 25
1924
1925 Unlike QMap, QMultiMap provides no operator[]. Use value() or
1926 replace() if you want to access the most recently inserted item
1927 with a certain key.
1928
1929 If you want to retrieve all the values for a single key, you can
1930 use values(const Key &key), which returns a QList<T>:
1931
1932 \snippet code/src_corelib_tools_qmap.cpp 26
1933
1934 The items that share the same key are available from most
1935 recently to least recently inserted.
1936
1937 If you prefer the STL-style iterators, you can call find() to get
1938 the iterator for the first item with a key and iterate from
1939 there:
1940
1941 \snippet code/src_corelib_tools_qmap.cpp 27
1942
1943 QMultiMap's key and value data types must be \l{assignable data
1944 types}. This covers most data types you are likely to encounter,
1945 but the compiler won't let you, for example, store a QWidget as a
1946 value; instead, store a QWidget *. In addition, QMultiMap's key type
1947 must provide operator<(). See the QMap documentation for details.
1948
1949 \sa QMap, QMapIterator, QMutableMapIterator, QMultiHash
1950*/
1951
1952/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap()
1953
1954 Constructs an empty map.
1955*/
1956
1957/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(std::initializer_list<std::pair<Key,T> > list)
1958 \since 5.1
1959
1960 Constructs a multi-map with a copy of each of the elements in the
1961 initializer list \a list.
1962
1963 This function is only available if the program is being
1964 compiled in C++11 mode.
1965*/
1966
1967/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(const QMap<Key, T> &other)
1968
1969 Constructs a copy of \a other (which can be a QMap or a
1970 QMultiMap).
1971
1972 \sa operator=()
1973*/
1974
1975/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::replace(const Key &key, const T &value)
1976
1977 Inserts a new item with the key \a key and a value of \a value.
1978
1979 If there is already an item with the key \a key, that item's value
1980 is replaced with \a value.
1981
1982 If there are multiple items with the key \a key, the most
1983 recently inserted item's value is replaced with \a value.
1984
1985 \sa insert()
1986*/
1987
1988/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insert(const Key &key, const T &value)
1989
1990 Inserts a new item with the key \a key and a value of \a value.
1991
1992 If there is already an item with the same key in the map, this
1993 function will simply create a new one. (This behavior is
1994 different from replace(), which overwrites the value of an
1995 existing item.)
1996
1997 \sa replace()
1998*/
1999
2000/*! \fn [qmultimap-insert-pos] template <class Key, class T> typename QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insert(typename QMultiMap<Key, T>::const_iterator pos, const Key &key, const T &value)
2001
2002 \since 5.1
2003 Inserts a new item with the key \a key and value \a value and with hint \a pos
2004 suggesting where to do the insert.
2005
2006 If constBegin() is used as hint it indicates that the \a key is less than any key in the map
2007 while constEnd() suggests that the \a key is larger than any key in the map.
2008 Otherwise the hint should meet the condition (\a pos - 1).key() < \a key <= pos.key().
2009 If the hint \a pos is wrong it is ignored and a regular insert is done.
2010
2011 If there is already an item with the same key in the map, this function will simply create a new one.
2012
2013 \b {Note:} Be careful with the hint. Providing an iterator from an older shared instance might
2014 crash but there is also a risk that it will silently corrupt both the map and the \a pos map.
2015*/
2016
2017/*! \fn template <class Key, class T> QMultiMap &QMultiMap<Key, T>::operator+=(const QMultiMap &other)
2018
2019 Inserts all the items in the \a other map into this map and
2020 returns a reference to this map.
2021
2022 \sa insert(), operator+()
2023*/
2024
2025/*! \fn template <class Key, class T> QMultiMap QMultiMap<Key, T>::operator+(const QMultiMap &other) const
2026
2027 Returns a map that contains all the items in this map in
2028 addition to all the items in \a other. If a key is common to both
2029 maps, the resulting map will contain the key multiple times.
2030
2031 \sa operator+=()
2032*/
2033
2034/*!
2035 \fn template <class Key, class T> bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const
2036 \since 4.3
2037
2038 Returns \c true if the map contains an item with key \a key and
2039 value \a value; otherwise returns \c false.
2040
2041 \sa QMap::contains()
2042*/
2043
2044/*!
2045 \fn template <class Key, class T> int QMultiMap<Key, T>::remove(const Key &key, const T &value)
2046 \since 4.3
2047
2048 Removes all the items that have the key \a key and the value \a
2049 value from the map. Returns the number of items removed.
2050
2051 \sa QMap::remove()
2052*/
2053
2054/*!
2055 \fn template <class Key, class T> int QMultiMap<Key, T>::count(const Key &key, const T &value) const
2056 \since 4.3
2057
2058 Returns the number of items with key \a key and value \a value.
2059
2060 \sa QMap::count()
2061*/
2062
2063/*!
2064 \fn template <class Key, class T> typename QMap<Key, T>::iterator QMultiMap<Key, T>::find(const Key &key, const T &value)
2065 \since 4.3
2066
2067 Returns an iterator pointing to the item with key \a key and
2068 value \a value in the map.
2069
2070 If the map contains no such item, the function returns end().
2071
2072 If the map contains multiple items with key \a key, this
2073 function returns an iterator that points to the most recently
2074 inserted value.
2075
2076 \sa QMap::find()
2077*/
2078
2079/*!
2080 \fn template <class Key, class T> typename QMap<Key, T>::const_iterator QMultiMap<Key, T>::find(const Key &key, const T &value) const
2081 \since 4.3
2082 \overload
2083
2084 Returns a const iterator pointing to the item with the given \a key and
2085 \a value in the map.
2086
2087 If the map contains no such item, the function returns end().
2088
2089 If the map contains multiple items with the specified \a key, this
2090 function returns a const iterator that points to the most recently
2091 inserted value.
2092
2093 \sa QMap::find()
2094*/
2095
2096/*!
2097 \fn template <class Key, class T> typename QMap<Key, T>::const_iterator QMultiMap<Key, T>::constFind(const Key &key, const T &value) const
2098 \since 4.3
2099
2100 Returns an iterator pointing to the item with key \a key and the
2101 value \a value in the map.
2102
2103 If the map contains no such item, the function returns
2104 constEnd().
2105
2106 \sa QMap::constFind()
2107*/
2108
2109/*! \fn template <class Key, class T> QList<T> QMultiMap<Key, T>::values(const Key &key) const
2110
2111 Returns a list containing all the values associated with key
2112 \a key, from the most recently inserted to the least recently
2113 inserted one.
2114*/
2115
2116/*! \fn template <class Key, class T> QList<Key> QMultiMap<Key, T>::uniqueKeys() const
2117 \since 4.2
2118
2119 Returns a list containing all the keys in the map in ascending
2120 order. Keys that occur multiple times in the map occur only
2121 once in the returned list.
2122*/
2123
2124/*!
2125 \fn [qmultimap-unite] template <class Key, class T> QMultiMap<Key, T> &QMultiMap<Key, T>::unite(const QMultiMap<Key, T> &other)
2126
2127 Inserts all the items in the \a other map into this map. If a
2128 key is common to both maps, the resulting map will contain the
2129 key multiple times.
2130*/
2131
2132QT_END_NAMESPACE
2133

source code of qtbase/src/corelib/tools/qmap.cpp