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, 0, { 0, nullptr, nullptr }, 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->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->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_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(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_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_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(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_parent);
286 break;
287 }
288 }
289 }
290 if (x)
291 x->setColor(QMapNodeBase::Black);
292 }
293 free(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(alloc, alignment)
316 : ::malloc(alloc);
317}
318
319static inline void qMapDeallocate(QMapNodeBase *node, int alignment)
320{
321 if (alignment > qMapAlignmentThreshold())
322 qFreeAligned(node);
323 else
324 ::free(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(node, 0, 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(node);
345 }
346 return node;
347}
348
349void QMapDataBase::freeTree(QMapNodeBase *root, int alignment)
350{
351 if (root->left)
352 freeTree(root->left, alignment);
353 if (root->right)
354 freeTree(root->right, alignment);
355 qMapDeallocate(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 insertMulti() instead of insert() (or using the convenience
472 subclass QMultiMap). If you want to retrieve all the values for a
473 single key, you can use values(const Key &key), which returns a
474 QList<T>:
475
476 \snippet code/src_corelib_tools_qmap.cpp 10
477
478 The items that share the same key are available from most
479 recently to least recently inserted. Another approach is to call
480 find() to get the STL-style iterator for the first item with a
481 key and iterate from there:
482
483 \snippet code/src_corelib_tools_qmap.cpp 11
484
485 If you only need to extract the values from a map (not the keys),
486 you can also use \l{foreach}:
487
488 \snippet code/src_corelib_tools_qmap.cpp 12
489
490 Items can be removed from the map in several ways. One way is to
491 call remove(); this will remove any item with the given key.
492 Another way is to use QMutableMapIterator::remove(). In addition,
493 you can clear the entire map using clear().
494
495 QMap's key and value data types must be \l{assignable data
496 types}. This covers most data types you are likely to encounter,
497 but the compiler won't let you, for example, store a QWidget as a
498 value; instead, store a QWidget *. In addition, QMap's key type
499 must provide operator<(). QMap uses it to keep its items sorted,
500 and assumes that two keys \c x and \c y are equal if neither \c{x
501 < y} nor \c{y < x} is true.
502
503 Example:
504 \snippet code/src_corelib_tools_qmap.cpp 13
505
506 In the example, we start by comparing the employees' names. If
507 they're equal, we compare their dates of birth to break the tie.
508
509 \sa QMapIterator, QMutableMapIterator, QHash, QSet
510*/
511
512/*! \fn template <class Key, class T> QMap<Key, T>::QMap()
513
514 Constructs an empty map.
515
516 \sa clear()
517*/
518
519/*!
520 \fn template <class Key, class T> QMap<Key, T>::QMap(QMap<Key, T> &&other)
521
522 Move-constructs a QMap instance, making it point at the same
523 object that \a other was pointing to.
524
525 \since 5.2
526*/
527
528/*! \fn template <class Key, class T> QMap<Key, T>::QMap(const QMap<Key, T> &other)
529
530 Constructs a copy of \a other.
531
532 This operation occurs in \l{constant time}, because QMap is
533 \l{implicitly shared}. This makes returning a QMap from a
534 function very fast. If a shared instance is modified, it will be
535 copied (copy-on-write), and this takes \l{linear time}.
536
537 \sa operator=()
538*/
539
540/*! \fn template <class Key, class T> QMap<Key, T>::QMap(const typename std::map<Key, T> & other)
541
542 Constructs a copy of \a other.
543
544 \sa toStdMap()
545*/
546
547/*! \fn template <class Key, class T> QMap<Key, T>::QMap(std::initializer_list<std::pair<Key,T> > list)
548 \since 5.1
549
550 Constructs a map with a copy of each of the elements in the
551 initializer list \a list.
552
553 This function is only available if the program is being
554 compiled in C++11 mode.
555*/
556
557/*! \fn template <class Key, class T> std::map<Key, T> QMap<Key, T>::toStdMap() const
558
559 Returns an STL map equivalent to this QMap.
560*/
561
562/*! \fn template <class Key, class T> QMap<Key, T>::~QMap()
563
564 Destroys the map. References to the values in the map, and all
565 iterators over this map, become invalid.
566*/
567
568/*! \fn template <class Key, class T> QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other)
569
570 Assigns \a other to this map and returns a reference to this map.
571*/
572
573/*!
574 \fn template <class Key, class T> QMap<Key, T> &QMap<Key, T>::operator=(QMap<Key, T> &&other)
575
576 Move-assigns \a other to this QMap instance.
577
578 \since 5.2
579*/
580
581/*! \fn template <class Key, class T> void QMap<Key, T>::swap(QMap<Key, T> &other)
582 \since 4.8
583
584 Swaps map \a other with this map. This operation is very
585 fast and never fails.
586*/
587
588/*! \fn template <class Key, class T> void QMultiMap<Key, T>::swap(QMultiMap<Key, T> &other)
589 \since 4.8
590
591 Swaps map \a other with this map. This operation is very
592 fast and never fails.
593*/
594
595/*! \fn template <class Key, class T> bool QMap<Key, T>::operator==(const QMap<Key, T> &other) const
596
597 Returns \c true if \a other is equal to this map; otherwise returns
598 false.
599
600 Two maps are considered equal if they contain the same (key,
601 value) pairs.
602
603 This function requires the value type to implement \c
604 operator==().
605
606 \sa operator!=()
607*/
608
609/*! \fn template <class Key, class T> bool QMap<Key, T>::operator!=(const QMap<Key, T> &other) const
610
611 Returns \c true if \a other is not equal to this map; otherwise
612 returns \c false.
613
614 Two maps are considered equal if they contain the same (key,
615 value) pairs.
616
617 This function requires the value type to implement \c
618 operator==().
619
620 \sa operator==()
621*/
622
623/*! \fn template <class Key, class T> int QMap<Key, T>::size() const
624
625 Returns the number of (key, value) pairs in the map.
626
627 \sa isEmpty(), count()
628*/
629
630/*!
631 \fn template <class Key, class T> bool QMap<Key, T>::isEmpty() const
632
633 Returns \c true if the map contains no items; otherwise returns
634 false.
635
636 \sa size()
637*/
638
639/*! \fn template <class Key, class T> void QMap<Key, T>::detach()
640
641 \internal
642
643 Detaches this map from any other maps with which it may share
644 data.
645
646 \sa isDetached()
647*/
648
649/*! \fn template <class Key, class T> bool QMap<Key, T>::isDetached() const
650
651 \internal
652
653 Returns \c true if the map's internal data isn't shared with any
654 other map object; otherwise returns \c false.
655
656 \sa detach()
657*/
658
659/*! \fn template <class Key, class T> void QMap<Key, T>::setSharable(bool sharable)
660
661 \internal
662*/
663
664/*! \fn template <class Key, class T> bool QMap<Key, T>::isSharedWith(const QMap<Key, T> &other) const
665
666 \internal
667*/
668
669/*! \fn template <class Key, class T> void QMap<Key, T>::clear()
670
671 Removes all items from the map.
672
673 \sa remove()
674*/
675
676/*! \fn template <class Key, class T> int QMap<Key, T>::remove(const Key &key)
677
678 Removes all the items that have the key \a key from the map.
679 Returns the number of items removed which is usually 1 but will be
680 0 if the key isn't in the map, or \> 1 if insertMulti() has been
681 used with the \a key.
682
683 \sa clear(), take(), QMultiMap::remove()
684*/
685
686/*! \fn template <class Key, class T> T QMap<Key, T>::take(const Key &key)
687
688 Removes the item with the key \a key from the map and returns
689 the value associated with it.
690
691 If the item does not exist in the map, the function simply
692 returns a \l{default-constructed value}. If there are multiple
693 items for \a key in the map, only the most recently inserted one
694 is removed and returned.
695
696 If you don't use the return value, remove() is more efficient.
697
698 \sa remove()
699*/
700
701/*! \fn template <class Key, class T> bool QMap<Key, T>::contains(const Key &key) const
702
703 Returns \c true if the map contains an item with key \a key;
704 otherwise returns \c false.
705
706 \sa count(), QMultiMap::contains()
707*/
708
709/*! \fn template <class Key, class T> const T QMap<Key, T>::value(const Key &key, const T &defaultValue) const
710
711 Returns the value associated with the key \a key.
712
713 If the map contains no item with key \a key, the function returns
714 \a defaultValue. If no \a defaultValue is specified, the function
715 returns a \l{default-constructed value}. If there are multiple
716 items for \a key in the map, the value of the most recently
717 inserted one is returned.
718
719 \sa key(), values(), contains(), operator[]()
720*/
721
722/*! \fn template <class Key, class T> T &QMap<Key, T>::operator[](const Key &key)
723
724 Returns the value associated with the key \a key as a modifiable
725 reference.
726
727 If the map contains no item with key \a key, the function inserts
728 a \l{default-constructed value} into the map with key \a key, and
729 returns a reference to it. If the map contains multiple items
730 with key \a key, this function returns a reference to the most
731 recently inserted value.
732
733 \sa insert(), value()
734*/
735
736/*! \fn template <class Key, class T> const T QMap<Key, T>::operator[](const Key &key) const
737
738 \overload
739
740 Same as value().
741*/
742
743/*! \fn template <class Key, class T> QList<Key> QMap<Key, T>::uniqueKeys() const
744 \since 4.2
745
746 Returns a list containing all the keys in the map in ascending
747 order. Keys that occur multiple times in the map (because items
748 were inserted with insertMulti(), or unite() was used) occur only
749 once in the returned list.
750
751 \sa keys(), values()
752*/
753
754/*! \fn template <class Key, class T> QList<Key> QMap<Key, T>::keys() const
755
756 Returns a list containing all the keys in the map in ascending
757 order. Keys that occur multiple times in the map (because items
758 were inserted with insertMulti(), or unite() was used) also
759 occur multiple times in the list.
760
761 To obtain a list of unique keys, where each key from the map only
762 occurs once, use uniqueKeys().
763
764 The order is guaranteed to be the same as that used by values().
765
766 \sa uniqueKeys(), values(), key()
767*/
768
769/*! \fn template <class Key, class T> QList<Key> QMap<Key, T>::keys(const T &value) const
770
771 \overload
772
773 Returns a list containing all the keys associated with value \a
774 value in ascending order.
775
776 This function can be slow (\l{linear time}), because QMap's
777 internal data structure is optimized for fast lookup by key, not
778 by value.
779*/
780
781/*!
782 \fn template <class Key, class T> Key QMap<Key, T>::key(const T &value, const Key &defaultKey) const
783 \since 4.3
784 \overload
785
786 Returns the first key with value \a value, or \a defaultKey if
787 the map contains no item with value \a value. If no \a defaultKey
788 is provided the function returns a
789 \l{default-constructed value}{default-constructed key}.
790
791 This function can be slow (\l{linear time}), because QMap's
792 internal data structure is optimized for fast lookup by key, not
793 by value.
794
795 \sa value(), keys()
796*/
797
798/*! \fn template <class Key, class T> QList<T> QMap<Key, T>::values() const
799
800 Returns a list containing all the values in the map, in ascending
801 order of their keys. If a key is associated with multiple values,
802 all of its values will be in the list, and not just the most
803 recently inserted one.
804
805 \sa keys(), value()
806*/
807
808/*! \fn template <class Key, class T> QList<T> QMap<Key, T>::values(const Key &key) const
809
810 \overload
811
812 Returns a list containing all the values associated with key
813 \a key, from the most recently inserted to the least recently
814 inserted one.
815
816 \sa count(), insertMulti()
817*/
818
819/*! \fn template <class Key, class T> int QMap<Key, T>::count(const Key &key) const
820
821 Returns the number of items associated with key \a key.
822
823 \sa contains(), insertMulti(), QMultiMap::count()
824*/
825
826/*! \fn template <class Key, class T> int QMap<Key, T>::count() const
827
828 \overload
829
830 Same as size().
831*/
832
833/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::begin()
834
835 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in
836 the map.
837
838 \sa constBegin(), end()
839*/
840
841/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::begin() const
842
843 \overload
844*/
845
846/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::cbegin() const
847 \since 5.0
848
849 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
850 in the map.
851
852 \sa begin(), cend()
853*/
854
855/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::constBegin() const
856
857 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
858 in the map.
859
860 \sa begin(), constEnd()
861*/
862
863/*! \fn template <class Key, class T> QMap<Key, T>::key_iterator QMap<Key, T>::keyBegin() const
864 \since 5.6
865
866 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first key
867 in the map.
868
869 \sa keyEnd(), firstKey()
870*/
871
872/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::end()
873
874 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item
875 after the last item in the map.
876
877 \sa begin(), constEnd()
878*/
879
880/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::end() const
881
882 \overload
883*/
884
885/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::cend() const
886 \since 5.0
887
888 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
889 item after the last item in the map.
890
891 \sa cbegin(), end()
892*/
893
894/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::constEnd() const
895
896 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
897 item after the last item in the map.
898
899 \sa constBegin(), end()
900*/
901
902/*! \fn template <class Key, class T> QMap<Key, T>::key_iterator QMap<Key, T>::keyEnd() const
903 \since 5.6
904
905 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
906 item after the last key in the map.
907
908 \sa keyBegin(), lastKey()
909*/
910
911
912/*! \fn template <class Key, class T> QMap<Key, T>::key_value_iterator QMap<Key, T>::keyValueBegin()
913 \since 5.10
914
915 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first entry
916 in the map.
917
918 \sa keyValueEnd()
919*/
920
921/*! \fn template <class Key, class T> QMap<Key, T>::key_value_iterator QMap<Key, T>::keyValueEnd()
922 \since 5.10
923
924 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
925 entry after the last entry in the map.
926
927 \sa keyValueBegin()
928*/
929
930/*! \fn template <class Key, class T> QMap<Key, T>::const_key_value_iterator QMap<Key, T>::keyValueBegin() const
931 \since 5.10
932
933 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
934 in the map.
935
936 \sa keyValueEnd()
937*/
938
939/*! \fn template <class Key, class T> QMap<Key, T>::const_key_value_iterator QMap<Key, T>::constKeyValueBegin() const
940 \since 5.10
941
942 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
943 in the map.
944
945 \sa keyValueBegin()
946*/
947
948/*! \fn template <class Key, class T> QMap<Key, T>::const_key_value_iterator QMap<Key, T>::keyValueEnd() const
949 \since 5.10
950
951 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
952 entry after the last entry in the map.
953
954 \sa keyValueBegin()
955*/
956
957/*! \fn template <class Key, class T> QMap<Key, T>::const_key_value_iterator QMap<Key, T>::constKeyValueEnd() const
958 \since 5.10
959
960 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
961 entry after the last entry in the map.
962
963 \sa constKeyValueBegin()
964*/
965
966/*! \fn template <class Key, class T> const Key &QMap<Key, T>::firstKey() const
967 \since 5.2
968
969 Returns a reference to the smallest key in the map.
970 This function assumes that the map is not empty.
971
972 This executes in \l{constant time}.
973
974 \sa lastKey(), first(), keyBegin(), isEmpty()
975*/
976
977/*! \fn template <class Key, class T> const Key &QMap<Key, T>::lastKey() const
978 \since 5.2
979
980 Returns a reference to the largest key in the map.
981 This function assumes that the map is not empty.
982
983 This executes in \l{logarithmic time}.
984
985 \sa firstKey(), last(), keyEnd(), isEmpty()
986*/
987
988/*! \fn template <class Key, class T> T &QMap<Key, T>::first()
989 \since 5.2
990
991 Returns a reference to the first value in the map, that is the value mapped
992 to the smallest key. This function assumes that the map is not empty.
993
994 When unshared (or const version is called), this executes in \l{constant time}.
995
996 \sa last(), firstKey(), isEmpty()
997*/
998
999/*! \fn template <class Key, class T> const T &QMap<Key, T>::first() const
1000 \since 5.2
1001
1002 \overload
1003*/
1004
1005/*! \fn template <class Key, class T> T &QMap<Key, T>::last()
1006 \since 5.2
1007
1008 Returns a reference to the last value in the map, that is the value mapped
1009 to the largest key. This function assumes that the map is not empty.
1010
1011 When unshared (or const version is called), this executes in \l{logarithmic time}.
1012
1013 \sa first(), lastKey(), isEmpty()
1014*/
1015
1016/*! \fn template <class Key, class T> const T &QMap<Key, T>::last() const
1017 \since 5.2
1018
1019 \overload
1020*/
1021
1022/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::erase(iterator pos)
1023
1024 Removes the (key, value) pair pointed to by the iterator \a pos
1025 from the map, and returns an iterator to the next item in the
1026 map.
1027
1028 \sa remove()
1029*/
1030
1031/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::find(const Key &key)
1032
1033 Returns an iterator pointing to the item with key \a key in the
1034 map.
1035
1036 If the map contains no item with key \a key, the function
1037 returns end().
1038
1039 If the map contains multiple items with key \a key, this
1040 function returns an iterator that points to the most recently
1041 inserted value. The other values are accessible by incrementing
1042 the iterator. For example, here's some code that iterates over all
1043 the items with the same key:
1044
1045 \snippet code/src_corelib_tools_qmap.cpp 14
1046
1047 \sa constFind(), value(), values(), lowerBound(), upperBound(), QMultiMap::find()
1048*/
1049
1050/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &key) const
1051
1052 \overload
1053*/
1054
1055/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::constFind(const Key &key) const
1056 \since 4.1
1057
1058 Returns an const iterator pointing to the item with key \a key in the
1059 map.
1060
1061 If the map contains no item with key \a key, the function
1062 returns constEnd().
1063
1064 \sa find(), QMultiMap::constFind()
1065*/
1066
1067/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::lowerBound(const Key &key)
1068
1069 Returns an iterator pointing to the first item with key \a key in
1070 the map. If the map contains no item with key \a key, the
1071 function returns an iterator to the nearest item with a greater
1072 key.
1073
1074 Example:
1075 \snippet code/src_corelib_tools_qmap.cpp 15
1076
1077 If the map contains multiple items with key \a key, this
1078 function returns an iterator that points to the most recently
1079 inserted value. The other values are accessible by incrementing
1080 the iterator. For example, here's some code that iterates over all
1081 the items with the same key:
1082
1083 \snippet code/src_corelib_tools_qmap.cpp 16
1084
1085 \sa upperBound(), find()
1086*/
1087
1088/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::lowerBound(const Key &key) const
1089
1090 \overload
1091*/
1092
1093/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::upperBound(const Key &key)
1094
1095 Returns an iterator pointing to the item that immediately follows
1096 the last item with key \a key in the map. If the map contains no
1097 item with key \a key, the function returns an iterator to the
1098 nearest item with a greater key.
1099
1100 Example:
1101 \snippet code/src_corelib_tools_qmap.cpp 17
1102
1103 \sa lowerBound(), find()
1104*/
1105
1106/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::upperBound(const Key &key) const
1107
1108 \overload
1109*/
1110
1111/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &key, const T &value)
1112
1113 Inserts a new item with the key \a key and a value of \a value.
1114
1115 If there is already an item with the key \a key, that item's value
1116 is replaced with \a value.
1117
1118 If there are multiple items with the key \a key, the most
1119 recently inserted item's value is replaced with \a value.
1120
1121 \sa insertMulti()
1122*/
1123
1124/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::insert(const_iterator pos, const Key &key, const T &value)
1125 \overload
1126 \since 5.1
1127 Inserts a new item with the key \a key and value \a value and with hint \a pos
1128 suggesting where to do the insert.
1129
1130 If constBegin() is used as hint it indicates that the \a key is less than any key in the map
1131 while constEnd() suggests that the \a key is (strictly) larger than any key in the map.
1132 Otherwise the hint should meet the condition (\a pos - 1).key() < \a key <= pos.key().
1133 If the hint \a pos is wrong it is ignored and a regular insert is done.
1134
1135 If there is already an item with the key \a key, that item's value
1136 is replaced with \a value.
1137
1138 If there are multiple items with the key \a key, then exactly one of them
1139 is replaced with \a value.
1140
1141 If the hint is correct and the map is unshared, the insert executes in amortized \l{constant time}.
1142
1143 When creating a map from sorted data inserting the largest key first with constBegin()
1144 is faster than inserting in sorted order with constEnd(), since constEnd() - 1 (which is needed
1145 to check if the hint is valid) needs \l{logarithmic time}.
1146
1147 \b {Note:} Be careful with the hint. Providing an iterator from an older shared instance might
1148 crash but there is also a risk that it will silently corrupt both the map and the \a pos map.
1149
1150 \sa insertMulti()
1151*/
1152
1153/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &key, const T &value)
1154
1155 Inserts a new item with the key \a key and a value of \a value.
1156
1157 If there is already an item with the same key in the map, this
1158 function will simply create a new one. (This behavior is
1159 different from insert(), which overwrites the value of an
1160 existing item.)
1161
1162 \sa insert(), values()
1163*/
1164
1165/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const_iterator pos, const Key &key, const T &value)
1166 \overload
1167 \since 5.1
1168 Inserts a new item with the key \a key and value \a value and with hint \a pos
1169 suggesting where to do the insert.
1170
1171 If constBegin() is used as hint it indicates that the \a key is less than any key in the map
1172 while constEnd() suggests that the \a key is larger than any key in the map.
1173 Otherwise the hint should meet the condition (\a pos - 1).key() < \a key <= pos.key().
1174 If the hint \a pos is wrong it is ignored and a regular insertMulti is done.
1175
1176 If there is already an item with the same key in the map, this function will simply create a new one.
1177
1178 \b {Note:} Be careful with the hint. Providing an iterator from an older shared instance might
1179 crash but there is also a risk that it will silently corrupt both the map and the \a pos map.
1180
1181 \sa insert()
1182*/
1183
1184
1185/*! \fn template <class Key, class T> QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other)
1186
1187 Inserts all the items in the \a other map into this map. If a
1188 key is common to both maps, the resulting map will contain the
1189 key multiple times.
1190
1191 \sa insertMulti()
1192*/
1193
1194/*! \typedef QMap::Iterator
1195
1196 Qt-style synonym for QMap<Key, T>::iterator.
1197*/
1198
1199/*! \typedef QMap::ConstIterator
1200
1201 Qt-style synonym for QMap<Key, T>::const_iterator.
1202*/
1203
1204/*! \typedef QMap::difference_type
1205
1206 Typedef for ptrdiff_t. Provided for STL compatibility.
1207*/
1208
1209/*! \typedef QMap::key_type
1210
1211 Typedef for Key. Provided for STL compatibility.
1212*/
1213
1214/*! \typedef QMap::mapped_type
1215
1216 Typedef for T. Provided for STL compatibility.
1217*/
1218
1219/*! \typedef QMap::size_type
1220
1221 Typedef for int. Provided for STL compatibility.
1222*/
1223
1224/*!
1225 \fn template <class Key, class T> bool QMap<Key, T>::empty() const
1226
1227 This function is provided for STL compatibility. It is equivalent
1228 to isEmpty(), returning true if the map is empty; otherwise
1229 returning false.
1230*/
1231
1232/*!
1233 \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)
1234
1235 Returns a pair of iterators delimiting the range of values \c{[first, second)}, that
1236 are stored under \a key.
1237*/
1238
1239/*!
1240 \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
1241 \overload
1242 \since 5.6
1243*/
1244
1245
1246/*! \class QMap::iterator
1247 \inmodule QtCore
1248 \brief The QMap::iterator class provides an STL-style non-const iterator for QMap and QMultiMap.
1249
1250 QMap features both \l{STL-style iterators} and \l{Java-style
1251 iterators}. The STL-style iterators are more low-level and more
1252 cumbersome to use; on the other hand, they are slightly faster
1253 and, for developers who already know STL, have the advantage of
1254 familiarity.
1255
1256 QMap\<Key, T\>::iterator allows you to iterate over a QMap (or
1257 QMultiMap) and to modify the value (but not the key) stored under
1258 a particular key. If you want to iterate over a const QMap, you
1259 should use QMap::const_iterator. It is generally good practice to
1260 use QMap::const_iterator on a non-const QMap as well, unless you
1261 need to change the QMap through the iterator. Const iterators are
1262 slightly faster, and can improve code readability.
1263
1264 The default QMap::iterator constructor creates an uninitialized
1265 iterator. You must initialize it using a QMap function like
1266 QMap::begin(), QMap::end(), or QMap::find() before you can
1267 start iterating. Here's a typical loop that prints all the (key,
1268 value) pairs stored in a map:
1269
1270 \snippet code/src_corelib_tools_qmap.cpp 18
1271
1272 Unlike QHash, which stores its items in an arbitrary order, QMap
1273 stores its items ordered by key. Items that share the same key
1274 (because they were inserted using QMap::insertMulti(), or due to a
1275 unite()) will appear consecutively, from the most recently to the
1276 least recently inserted value.
1277
1278 Let's see a few examples of things we can do with a
1279 QMap::iterator that we cannot do with a QMap::const_iterator.
1280 Here's an example that increments every value stored in the QMap
1281 by 2:
1282
1283 \snippet code/src_corelib_tools_qmap.cpp 19
1284
1285 Here's an example that removes all the items whose key is a
1286 string that starts with an underscore character:
1287
1288 \snippet code/src_corelib_tools_qmap.cpp 20
1289
1290 The call to QMap::erase() removes the item pointed to by the
1291 iterator from the map, and returns an iterator to the next item.
1292 Here's another way of removing an item while iterating:
1293
1294 \snippet code/src_corelib_tools_qmap.cpp 21
1295
1296 It might be tempting to write code like this:
1297
1298 \snippet code/src_corelib_tools_qmap.cpp 22
1299
1300 However, this will potentially crash in \c{++i}, because \c i is
1301 a dangling iterator after the call to erase().
1302
1303 Multiple iterators can be used on the same map. If you add items
1304 to the map, existing iterators will remain valid. If you remove
1305 items from the map, iterators that point to the removed items
1306 will become dangling iterators.
1307
1308 \warning Iterators on implicitly shared containers do not work
1309 exactly like STL-iterators. You should avoid copying a container
1310 while iterators are active on that container. For more information,
1311 read \l{Implicit sharing iterator problem}.
1312
1313 \sa QMap::const_iterator, QMap::key_iterator, QMutableMapIterator
1314*/
1315
1316/*! \typedef QMap::iterator::difference_type
1317
1318 \internal
1319*/
1320
1321/*! \typedef QMap::iterator::iterator_category
1322
1323 A synonym for \e {std::bidirectional_iterator_tag} indicating
1324 this iterator is a bidirectional iterator.
1325*/
1326
1327/*! \typedef QMap::iterator::pointer
1328
1329 \internal
1330*/
1331
1332/*! \typedef QMap::iterator::reference
1333
1334 \internal
1335*/
1336
1337/*! \typedef QMap::iterator::value_type
1338
1339 \internal
1340*/
1341
1342/*! \fn template <class Key, class T> QMap<Key, T>::iterator::iterator()
1343
1344 Constructs an uninitialized iterator.
1345
1346 Functions like key(), value(), and operator++() must not be
1347 called on an uninitialized iterator. Use operator=() to assign a
1348 value to it before using it.
1349
1350 \sa QMap::begin(), QMap::end()
1351*/
1352
1353/*! \fn template <class Key, class T> QMap<Key, T>::iterator::iterator(Node *)
1354
1355 \internal
1356*/
1357
1358/*! \fn template <class Key, class T> const Key &QMap<Key, T>::iterator::key() const
1359
1360 Returns the current item's key as a const reference.
1361
1362 There is no direct way of changing an item's key through an
1363 iterator, although it can be done by calling QMap::erase()
1364 followed by QMap::insert() or QMap::insertMulti().
1365
1366 \sa value()
1367*/
1368
1369/*! \fn template <class Key, class T> T &QMap<Key, T>::iterator::value() const
1370
1371 Returns a modifiable reference to the current item's value.
1372
1373 You can change the value of an item by using value() on
1374 the left side of an assignment, for example:
1375
1376 \snippet code/src_corelib_tools_qmap.cpp 23
1377
1378 \sa key(), operator*()
1379*/
1380
1381/*! \fn template <class Key, class T> T &QMap<Key, T>::iterator::operator*() const
1382
1383 Returns a modifiable reference to the current item's value.
1384
1385 Same as value().
1386
1387 \sa key()
1388*/
1389
1390/*! \fn template <class Key, class T> T *QMap<Key, T>::iterator::operator->() const
1391
1392 Returns a pointer to the current item's value.
1393
1394 \sa value()
1395*/
1396
1397/*!
1398 \fn template <class Key, class T> bool QMap<Key, T>::iterator::operator==(const iterator &other) const
1399 \fn template <class Key, class T> bool QMap<Key, T>::iterator::operator==(const const_iterator &other) const
1400
1401 Returns \c true if \a other points to the same item as this
1402 iterator; otherwise returns \c false.
1403
1404 \sa operator!=()
1405*/
1406
1407/*!
1408 \fn template <class Key, class T> bool QMap<Key, T>::iterator::operator!=(const iterator &other) const
1409 \fn template <class Key, class T> bool QMap<Key, T>::iterator::operator!=(const const_iterator &other) const
1410
1411 Returns \c true if \a other points to a different item than this
1412 iterator; otherwise returns \c false.
1413
1414 \sa operator==()
1415*/
1416
1417/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator++()
1418
1419 The prefix ++ operator (\c{++i}) advances the iterator to the
1420 next item in the map and returns an iterator to the new current
1421 item.
1422
1423 Calling this function on QMap::end() leads to undefined results.
1424
1425 \sa operator--()
1426*/
1427
1428/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator++(int)
1429
1430 \overload
1431
1432 The postfix ++ operator (\c{i++}) advances the iterator to the
1433 next item in the map and returns an iterator to the previously
1434 current item.
1435*/
1436
1437/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator--()
1438
1439 The prefix -- operator (\c{--i}) makes the preceding item
1440 current and returns an iterator pointing to the new current item.
1441
1442 Calling this function on QMap::begin() leads to undefined
1443 results.
1444
1445 \sa operator++()
1446*/
1447
1448/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator--(int)
1449
1450 \overload
1451
1452 The postfix -- operator (\c{i--}) makes the preceding item
1453 current and returns an iterator pointing to the previously
1454 current item.
1455*/
1456
1457/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator+(int j) const
1458
1459 Returns an iterator to the item at \a j positions forward from
1460 this iterator. (If \a j is negative, the iterator goes backward.)
1461
1462 This operation can be slow for large \a j values.
1463
1464 \sa operator-()
1465
1466*/
1467
1468/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator-(int j) const
1469
1470 Returns an iterator to the item at \a j positions backward from
1471 this iterator. (If \a j is negative, the iterator goes forward.)
1472
1473 This operation can be slow for large \a j values.
1474
1475 \sa operator+()
1476*/
1477
1478/*! \fn template <class Key, class T> QMap<Key, T>::iterator &QMap<Key, T>::iterator::operator+=(int j)
1479
1480 Advances the iterator by \a j items. (If \a j is negative, the
1481 iterator goes backward.)
1482
1483 \sa operator-=(), operator+()
1484*/
1485
1486/*! \fn template <class Key, class T> QMap<Key, T>::iterator &QMap<Key, T>::iterator::operator-=(int j)
1487
1488 Makes the iterator go back by \a j items. (If \a j is negative,
1489 the iterator goes forward.)
1490
1491 \sa operator+=(), operator-()
1492*/
1493
1494/*! \class QMap::const_iterator
1495 \inmodule QtCore
1496 \brief The QMap::const_iterator class provides an STL-style const iterator for QMap and QMultiMap.
1497
1498 QMap features both \l{STL-style iterators} and \l{Java-style
1499 iterators}. The STL-style iterators are more low-level and more
1500 cumbersome to use; on the other hand, they are slightly faster
1501 and, for developers who already know STL, have the advantage of
1502 familiarity.
1503
1504 QMap\<Key, T\>::const_iterator allows you to iterate over a QMap
1505 (or a QMultiMap). If you want to modify the QMap as you iterate
1506 over it, you must use QMap::iterator instead. It is generally
1507 good practice to use QMap::const_iterator on a non-const QMap as
1508 well, unless you need to change the QMap through the iterator.
1509 Const iterators are slightly faster, and can improve code
1510 readability.
1511
1512 The default QMap::const_iterator constructor creates an
1513 uninitialized iterator. You must initialize it using a QMap
1514 function like QMap::constBegin(), QMap::constEnd(), or
1515 QMap::find() before you can start iterating. Here's a typical
1516 loop that prints all the (key, value) pairs stored in a map:
1517
1518 \snippet code/src_corelib_tools_qmap.cpp 24
1519
1520 Unlike QHash, which stores its items in an arbitrary order, QMap
1521 stores its items ordered by key. Items that share the same key
1522 (because they were inserted using QMap::insertMulti()) will
1523 appear consecutively, from the most recently to the least
1524 recently inserted value.
1525
1526 Multiple iterators can be used on the same map. If you add items
1527 to the map, existing iterators will remain valid. If you remove
1528 items from the map, iterators that point to the removed items
1529 will become dangling iterators.
1530
1531 \warning Iterators on implicitly shared containers do not work
1532 exactly like STL-iterators. You should avoid copying a container
1533 while iterators are active on that container. For more information,
1534 read \l{Implicit sharing iterator problem}.
1535
1536 \sa QMap::iterator, QMap::key_iterator, QMapIterator
1537*/
1538
1539/*! \typedef QMap::const_iterator::difference_type
1540
1541 \internal
1542*/
1543
1544/*! \typedef QMap::const_iterator::iterator_category
1545
1546 A synonym for \e {std::bidirectional_iterator_tag} indicating
1547 this iterator is a bidirectional iterator.
1548*/
1549
1550/*! \typedef QMap::const_iterator::pointer
1551
1552 \internal
1553*/
1554
1555/*! \typedef QMap::const_iterator::reference
1556
1557 \internal
1558*/
1559
1560/*! \typedef QMap::const_iterator::value_type
1561
1562 \internal
1563*/
1564
1565/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator::const_iterator()
1566
1567 Constructs an uninitialized iterator.
1568
1569 Functions like key(), value(), and operator++() must not be
1570 called on an uninitialized iterator. Use operator=() to assign a
1571 value to it before using it.
1572
1573 \sa QMap::constBegin(), QMap::constEnd()
1574*/
1575
1576/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator::const_iterator(const Node *)
1577
1578 \internal
1579*/
1580
1581/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator::const_iterator(const iterator &other)
1582
1583 Constructs a copy of \a other.
1584*/
1585
1586/*! \fn template <class Key, class T> const Key &QMap<Key, T>::const_iterator::key() const
1587
1588 Returns the current item's key.
1589
1590 \sa value()
1591*/
1592
1593/*! \fn template <class Key, class T> const T &QMap<Key, T>::const_iterator::value() const
1594
1595 Returns the current item's value.
1596
1597 \sa key(), operator*()
1598*/
1599
1600/*! \fn template <class Key, class T> const T &QMap<Key, T>::const_iterator::operator*() const
1601
1602 Returns the current item's value.
1603
1604 Same as value().
1605
1606 \sa key()
1607*/
1608
1609/*! \fn template <class Key, class T> const T *QMap<Key, T>::const_iterator::operator->() const
1610
1611 Returns a pointer to the current item's value.
1612
1613 \sa value()
1614*/
1615
1616/*! \fn template <class Key, class T> bool QMap<Key, T>::const_iterator::operator==(const const_iterator &other) const
1617
1618 Returns \c true if \a other points to the same item as this
1619 iterator; otherwise returns \c false.
1620
1621 \sa operator!=()
1622*/
1623
1624/*! \fn template <class Key, class T> bool QMap<Key, T>::const_iterator::operator!=(const const_iterator &other) const
1625
1626 Returns \c true if \a other points to a different item than this
1627 iterator; otherwise returns \c false.
1628
1629 \sa operator==()
1630*/
1631
1632/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::const_iterator::operator++()
1633
1634 The prefix ++ operator (\c{++i}) advances the iterator to the
1635 next item in the map and returns an iterator to the new current
1636 item.
1637
1638 Calling this function on QMap::end() leads to undefined results.
1639
1640 \sa operator--()
1641*/
1642
1643/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::const_iterator::operator++(int)
1644
1645 \overload
1646
1647 The postfix ++ operator (\c{i++}) advances the iterator to the
1648 next item in the map and returns an iterator to the previously
1649 current item.
1650*/
1651
1652/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator &QMap<Key, T>::const_iterator::operator--()
1653
1654 The prefix -- operator (\c{--i}) makes the preceding item
1655 current and returns an iterator pointing to the new current item.
1656
1657 Calling this function on QMap::begin() leads to undefined
1658 results.
1659
1660 \sa operator++()
1661*/
1662
1663/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::const_iterator::operator--(int)
1664
1665 \overload
1666
1667 The postfix -- operator (\c{i--}) makes the preceding item
1668 current and returns an iterator pointing to the previously
1669 current item.
1670*/
1671
1672/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::const_iterator::operator+(int j) const
1673
1674 Returns an iterator to the item at \a j positions forward from
1675 this iterator. (If \a j is negative, the iterator goes backward.)
1676
1677 This operation can be slow for large \a j values.
1678
1679 \sa operator-()
1680*/
1681
1682/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::const_iterator::operator-(int j) const
1683
1684 Returns an iterator to the item at \a j positions backward from
1685 this iterator. (If \a j is negative, the iterator goes forward.)
1686
1687 This operation can be slow for large \a j values.
1688
1689 \sa operator+()
1690*/
1691
1692/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator &QMap<Key, T>::const_iterator::operator+=(int j)
1693
1694 Advances the iterator by \a j items. (If \a j is negative, the
1695 iterator goes backward.)
1696
1697 This operation can be slow for large \a j values.
1698
1699 \sa operator-=(), operator+()
1700*/
1701
1702/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator &QMap<Key, T>::const_iterator::operator-=(int j)
1703
1704 Makes the iterator go back by \a j items. (If \a j is negative,
1705 the iterator goes forward.)
1706
1707 This operation can be slow for large \a j values.
1708
1709 \sa operator+=(), operator-()
1710*/
1711
1712/*! \class QMap::key_iterator
1713 \inmodule QtCore
1714 \since 5.6
1715 \brief The QMap::key_iterator class provides an STL-style const iterator for QMap and QMultiMap keys.
1716
1717 QMap::key_iterator is essentially the same as QMap::const_iterator
1718 with the difference that operator*() and operator->() return a key
1719 instead of a value.
1720
1721 For most uses QMap::iterator and QMap::const_iterator should be used,
1722 you can easily access the key by calling QMap::iterator::key():
1723
1724 \snippet code/src_corelib_tools_qmap.cpp keyiterator1
1725
1726 However, to have interoperability between QMap's keys and STL-style
1727 algorithms we need an iterator that dereferences to a key instead
1728 of a value. With QMap::key_iterator we can apply an algorithm to a
1729 range of keys without having to call QMap::keys(), which is inefficient
1730 as it costs one QMap iteration and memory allocation to create a temporary
1731 QList.
1732
1733 \snippet code/src_corelib_tools_qmap.cpp keyiterator2
1734
1735 QMap::key_iterator is const, it's not possible to modify the key.
1736
1737 The default QMap::key_iterator constructor creates an uninitialized
1738 iterator. You must initialize it using a QMap function like
1739 QMap::keyBegin() or QMap::keyEnd().
1740
1741 \warning Iterators on implicitly shared containers do not work
1742 exactly like STL-iterators. You should avoid copying a container
1743 while iterators are active on that container. For more information,
1744 read \l{Implicit sharing iterator problem}.
1745
1746 \sa QMap::const_iterator, QMap::iterator
1747*/
1748
1749/*! \typedef QMap::key_iterator::difference_type
1750 \internal
1751*/
1752
1753/*! \typedef QMap::key_iterator::iterator_category
1754 \internal
1755*/
1756
1757/*! \typedef QMap::key_iterator::pointer
1758 \internal
1759*/
1760
1761/*! \typedef QMap::key_iterator::reference
1762 \internal
1763*/
1764
1765/*! \typedef QMap::key_iterator::value_type
1766 \internal
1767*/
1768
1769/*! \fn template <class Key, class T> const T &QMap<Key, T>::key_iterator::operator*() const
1770
1771 Returns the current item's key.
1772*/
1773
1774/*! \fn template <class Key, class T> const T *QMap<Key, T>::key_iterator::operator->() const
1775
1776 Returns a pointer to the current item's key.
1777*/
1778
1779/*! \fn template <class Key, class T> bool QMap<Key, T>::key_iterator::operator==(key_iterator other) const
1780
1781 Returns \c true if \a other points to the same item as this
1782 iterator; otherwise returns \c false.
1783
1784 \sa operator!=()
1785*/
1786
1787/*! \fn template <class Key, class T> bool QMap<Key, T>::key_iterator::operator!=(key_iterator other) const
1788
1789 Returns \c true if \a other points to a different item than this
1790 iterator; otherwise returns \c false.
1791
1792 \sa operator==()
1793*/
1794
1795/*!
1796 \fn template <class Key, class T> QMap<Key, T>::key_iterator &QMap<Key, T>::key_iterator::operator++()
1797
1798 The prefix ++ operator (\c{++i}) advances the iterator to the
1799 next item in the hash and returns an iterator to the new current
1800 item.
1801
1802 Calling this function on QMap::keyEnd() leads to undefined results.
1803
1804 \sa operator--()
1805*/
1806
1807/*! \fn template <class Key, class T> QMap<Key, T>::key_iterator QMap<Key, T>::key_iterator::operator++(int)
1808
1809 \overload
1810
1811 The postfix ++ operator (\c{i++}) advances the iterator to the
1812 next item in the hash and returns an iterator to the previous
1813 item.
1814*/
1815
1816/*! \fn template <class Key, class T> QMap<Key, T>::key_iterator &QMap<Key, T>::key_iterator::operator--()
1817
1818 The prefix -- operator (\c{--i}) makes the preceding item
1819 current and returns an iterator pointing to the new current item.
1820
1821 Calling this function on QMap::keyBegin() leads to undefined
1822 results.
1823
1824 \sa operator++()
1825*/
1826
1827/*! \fn template <class Key, class T> QMap<Key, T>::key_iterator QMap<Key, T>::key_iterator::operator--(int)
1828
1829 \overload
1830
1831 The postfix -- operator (\c{i--}) makes the preceding item
1832 current and returns an iterator pointing to the previous
1833 item.
1834*/
1835
1836/*! \fn template <class Key, class T> const_iterator QMap<Key, T>::key_iterator::base() const
1837 Returns the underlying const_iterator this key_iterator is based on.
1838*/
1839
1840/*! \typedef QMap::const_key_value_iterator
1841 \inmodule QtCore
1842 \since 5.10
1843 \brief The QMap::const_key_value_iterator typedef provides an STL-style iterator for QMap and QMultiMap.
1844
1845 QMap::const_key_value_iterator is essentially the same as QMap::const_iterator
1846 with the difference that operator*() returns a key/value pair instead of a
1847 value.
1848
1849 \sa QKeyValueIterator
1850*/
1851
1852/*! \typedef QMap::key_value_iterator
1853 \inmodule QtCore
1854 \since 5.10
1855 \brief The QMap::key_value_iterator typedef provides an STL-style iterator for QMap and QMultiMap.
1856
1857 QMap::key_value_iterator is essentially the same as QMap::iterator
1858 with the difference that operator*() returns a key/value pair instead of a
1859 value.
1860
1861 \sa QKeyValueIterator
1862*/
1863
1864/*! \fn template <class Key, class T> QDataStream &operator<<(QDataStream &out, const QMap<Key, T> &map)
1865 \relates QMap
1866
1867 Writes the map \a map to stream \a out.
1868
1869 This function requires the key and value types to implement \c
1870 operator<<().
1871
1872 \sa{Serializing Qt Data Types}{Format of the QDataStream operators}
1873*/
1874
1875/*! \fn template <class Key, class T> QDataStream &operator>>(QDataStream &in, QMap<Key, T> &map)
1876 \relates QMap
1877
1878 Reads a map from stream \a in into \a map.
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/*! \class QMultiMap
1887 \inmodule QtCore
1888 \brief The QMultiMap class is a convenience QMap subclass that provides multi-valued maps.
1889
1890 \ingroup tools
1891 \ingroup shared
1892
1893 \reentrant
1894
1895 QMultiMap\<Key, T\> is one of Qt's generic \l{container classes}.
1896 It inherits QMap and extends it with a few convenience functions
1897 that make it more suitable than QMap for storing multi-valued
1898 maps. A multi-valued map is a map that allows multiple values
1899 with the same key; QMap normally doesn't allow that, unless you
1900 call QMap::insertMulti().
1901
1902 Because QMultiMap inherits QMap, all of QMap's functionality also
1903 applies to QMultiMap. For example, you can use isEmpty() to test
1904 whether the map is empty, and you can traverse a QMultiMap using
1905 QMap's iterator classes (for example, QMapIterator). But in
1906 addition, it provides an insert() function that corresponds to
1907 QMap::insertMulti(), and a replace() function that corresponds to
1908 QMap::insert(). It also provides convenient operator+() and
1909 operator+=().
1910
1911 Example:
1912 \snippet code/src_corelib_tools_qmap.cpp 25
1913
1914 Unlike QMap, QMultiMap provides no operator[]. Use value() or
1915 replace() if you want to access the most recently inserted item
1916 with a certain key.
1917
1918 If you want to retrieve all the values for a single key, you can
1919 use values(const Key &key), which returns a QList<T>:
1920
1921 \snippet code/src_corelib_tools_qmap.cpp 26
1922
1923 The items that share the same key are available from most
1924 recently to least recently inserted.
1925
1926 If you prefer the STL-style iterators, you can call find() to get
1927 the iterator for the first item with a key and iterate from
1928 there:
1929
1930 \snippet code/src_corelib_tools_qmap.cpp 27
1931
1932 QMultiMap's key and value data types must be \l{assignable data
1933 types}. This covers most data types you are likely to encounter,
1934 but the compiler won't let you, for example, store a QWidget as a
1935 value; instead, store a QWidget *. In addition, QMultiMap's key type
1936 must provide operator<(). See the QMap documentation for details.
1937
1938 \sa QMap, QMapIterator, QMutableMapIterator, QMultiHash
1939*/
1940
1941/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap()
1942
1943 Constructs an empty map.
1944*/
1945
1946/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(std::initializer_list<std::pair<Key,T> > list)
1947 \since 5.1
1948
1949 Constructs a multi-map with a copy of each of the elements in the
1950 initializer list \a list.
1951
1952 This function is only available if the program is being
1953 compiled in C++11 mode.
1954*/
1955
1956/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(const QMap<Key, T> &other)
1957
1958 Constructs a copy of \a other (which can be a QMap or a
1959 QMultiMap).
1960
1961 \sa operator=()
1962*/
1963
1964/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::replace(const Key &key, const T &value)
1965
1966 Inserts a new item with the key \a key and a value of \a value.
1967
1968 If there is already an item with the key \a key, that item's value
1969 is replaced with \a value.
1970
1971 If there are multiple items with the key \a key, the most
1972 recently inserted item's value is replaced with \a value.
1973
1974 \sa insert()
1975*/
1976
1977/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insert(const Key &key, const T &value)
1978
1979 Inserts a new item with the key \a key and a value of \a value.
1980
1981 If there is already an item with the same key in the map, this
1982 function will simply create a new one. (This behavior is
1983 different from replace(), which overwrites the value of an
1984 existing item.)
1985
1986 \sa replace()
1987*/
1988
1989/*! \fn template <class Key, class T> typename QMap<Key, T>::iterator QMultiMap<Key, T>::insert(typename QMap<Key, T>::const_iterator pos, const Key &key, const T &value)
1990
1991 \since 5.1
1992 Inserts a new item with the key \a key and value \a value and with hint \a pos
1993 suggesting where to do the insert.
1994
1995 If constBegin() is used as hint it indicates that the \a key is less than any key in the map
1996 while constEnd() suggests that the \a key is larger than any key in the map.
1997 Otherwise the hint should meet the condition (\a pos - 1).key() < \a key <= pos.key().
1998 If the hint \a pos is wrong it is ignored and a regular insert is done.
1999
2000 If there is already an item with the same key in the map, this function will simply create a new one.
2001
2002 \b {Note:} Be careful with the hint. Providing an iterator from an older shared instance might
2003 crash but there is also a risk that it will silently corrupt both the map and the \a pos map.
2004*/
2005
2006/*! \fn template <class Key, class T> QMultiMap &QMultiMap<Key, T>::operator+=(const QMultiMap &other)
2007
2008 Inserts all the items in the \a other map into this map and
2009 returns a reference to this map.
2010
2011 \sa insert(), operator+()
2012*/
2013
2014/*! \fn template <class Key, class T> QMultiMap QMultiMap<Key, T>::operator+(const QMultiMap &other) const
2015
2016 Returns a map that contains all the items in this map in
2017 addition to all the items in \a other. If a key is common to both
2018 maps, the resulting map will contain the key multiple times.
2019
2020 \sa operator+=()
2021*/
2022
2023/*!
2024 \fn template <class Key, class T> bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const
2025 \since 4.3
2026
2027 Returns \c true if the map contains an item with key \a key and
2028 value \a value; otherwise returns \c false.
2029
2030 \sa QMap::contains()
2031*/
2032
2033/*!
2034 \fn template <class Key, class T> int QMultiMap<Key, T>::remove(const Key &key, const T &value)
2035 \since 4.3
2036
2037 Removes all the items that have the key \a key and the value \a
2038 value from the map. Returns the number of items removed.
2039
2040 \sa QMap::remove()
2041*/
2042
2043/*!
2044 \fn template <class Key, class T> int QMultiMap<Key, T>::count(const Key &key, const T &value) const
2045 \since 4.3
2046
2047 Returns the number of items with key \a key and value \a value.
2048
2049 \sa QMap::count()
2050*/
2051
2052/*!
2053 \fn template <class Key, class T> typename QMap<Key, T>::iterator QMultiMap<Key, T>::find(const Key &key, const T &value)
2054 \since 4.3
2055
2056 Returns an iterator pointing to the item with key \a key and
2057 value \a value in the map.
2058
2059 If the map contains no such item, the function returns end().
2060
2061 If the map contains multiple items with key \a key, this
2062 function returns an iterator that points to the most recently
2063 inserted value.
2064
2065 \sa QMap::find()
2066*/
2067
2068/*!
2069 \fn template <class Key, class T> typename QMap<Key, T>::const_iterator QMultiMap<Key, T>::find(const Key &key, const T &value) const
2070 \since 4.3
2071 \overload
2072
2073 Returns a const iterator pointing to the item with the given \a key and
2074 \a value in the map.
2075
2076 If the map contains no such item, the function returns end().
2077
2078 If the map contains multiple items with the specified \a key, this
2079 function returns a const iterator that points to the most recently
2080 inserted value.
2081
2082 \sa QMap::find()
2083*/
2084
2085/*!
2086 \fn template <class Key, class T> typename QMap<Key, T>::const_iterator QMultiMap<Key, T>::constFind(const Key &key, const T &value) const
2087 \since 4.3
2088
2089 Returns an iterator pointing to the item with key \a key and the
2090 value \a value in the map.
2091
2092 If the map contains no such item, the function returns
2093 constEnd().
2094
2095 \sa QMap::constFind()
2096*/
2097
2098QT_END_NAMESPACE
2099