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#ifndef QMAP_H
41#define QMAP_H
42
43#include <QtCore/qiterator.h>
44#include <QtCore/qlist.h>
45#include <QtCore/qrefcount.h>
46#include <QtCore/qpair.h>
47
48#ifdef Q_MAP_DEBUG
49#include <QtCore/qdebug.h>
50#endif
51
52#include <functional>
53#include <initializer_list>
54#include <map>
55#include <new>
56
57QT_BEGIN_NAMESPACE
58
59/*
60 QMap uses qMapLessThanKey() to compare keys. The default
61 implementation uses operator<(). For pointer types,
62 qMapLessThanKey() uses std::less (because operator<() on
63 pointers can be used only between pointers in the same array).
64*/
65
66template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key2)
67{
68 return key1 < key2;
69}
70
71template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2)
72{
73 return std::less<const Ptr *>()(key1, key2);
74}
75
76struct QMapDataBase;
77template <class Key, class T> struct QMapData;
78
79struct Q_CORE_EXPORT QMapNodeBase
80{
81 quintptr p;
82 QMapNodeBase *left;
83 QMapNodeBase *right;
84
85 enum Color { Red = 0, Black = 1 };
86 enum { Mask = 3 }; // reserve the second bit as well
87
88 const QMapNodeBase *nextNode() const;
89 QMapNodeBase *nextNode() { return const_cast<QMapNodeBase *>(const_cast<const QMapNodeBase *>(this)->nextNode()); }
90 const QMapNodeBase *previousNode() const;
91 QMapNodeBase *previousNode() { return const_cast<QMapNodeBase *>(const_cast<const QMapNodeBase *>(this)->previousNode()); }
92
93 Color color() const { return Color(p & 1); }
94 void setColor(Color c) { if (c == Black) p |= Black; else p &= ~Black; }
95 QMapNodeBase *parent() const { return reinterpret_cast<QMapNodeBase *>(p & ~Mask); }
96 void setParent(QMapNodeBase *pp) { p = (p & Mask) | quintptr(pp); }
97
98 template <typename T>
99 static typename std::enable_if<QTypeInfo<T>::isComplex>::type
100 callDestructorIfNecessary(T &t) noexcept { Q_UNUSED(t); t.~T(); } // Q_UNUSED: silence MSVC unused 't' warning
101 template <typename T>
102 static typename std::enable_if<!QTypeInfo<T>::isComplex>::type
103 callDestructorIfNecessary(T &) noexcept {}
104};
105
106template <class Key, class T>
107struct QMapNode : public QMapNodeBase
108{
109 Key key;
110 T value;
111
112 inline QMapNode *leftNode() const { return static_cast<QMapNode *>(left); }
113 inline QMapNode *rightNode() const { return static_cast<QMapNode *>(right); }
114
115 inline const QMapNode *nextNode() const { return reinterpret_cast<const QMapNode *>(QMapNodeBase::nextNode()); }
116 inline const QMapNode *previousNode() const { return static_cast<const QMapNode *>(QMapNodeBase::previousNode()); }
117 inline QMapNode *nextNode() { return reinterpret_cast<QMapNode *>(QMapNodeBase::nextNode()); }
118 inline QMapNode *previousNode() { return static_cast<QMapNode *>(QMapNodeBase::previousNode()); }
119
120 QMapNode<Key, T> *copy(QMapData<Key, T> *d) const;
121
122 void destroySubTree()
123 {
124 callDestructorIfNecessary(key);
125 callDestructorIfNecessary(value);
126 doDestroySubTree(std::integral_constant<bool, QTypeInfo<T>::isComplex || QTypeInfo<Key>::isComplex>());
127 }
128
129 QMapNode<Key, T> *lowerBound(const Key &key);
130 QMapNode<Key, T> *upperBound(const Key &key);
131
132private:
133 void doDestroySubTree(std::false_type) {}
134 void doDestroySubTree(std::true_type)
135 {
136 if (left)
137 leftNode()->destroySubTree();
138 if (right)
139 rightNode()->destroySubTree();
140 }
141
142 QMapNode() = delete;
143 Q_DISABLE_COPY(QMapNode)
144};
145
146template <class Key, class T>
147inline QMapNode<Key, T> *QMapNode<Key, T>::lowerBound(const Key &akey)
148{
149 QMapNode<Key, T> *n = this;
150 QMapNode<Key, T> *lastNode = nullptr;
151 while (n) {
152 if (!qMapLessThanKey(n->key, akey)) {
153 lastNode = n;
154 n = n->leftNode();
155 } else {
156 n = n->rightNode();
157 }
158 }
159 return lastNode;
160}
161
162template <class Key, class T>
163inline QMapNode<Key, T> *QMapNode<Key, T>::upperBound(const Key &akey)
164{
165 QMapNode<Key, T> *n = this;
166 QMapNode<Key, T> *lastNode = nullptr;
167 while (n) {
168 if (qMapLessThanKey(akey, n->key)) {
169 lastNode = n;
170 n = n->leftNode();
171 } else {
172 n = n->rightNode();
173 }
174 }
175 return lastNode;
176}
177
178
179
180struct Q_CORE_EXPORT QMapDataBase
181{
182 QtPrivate::RefCount ref;
183 int size;
184 QMapNodeBase header;
185 QMapNodeBase *mostLeftNode;
186
187 void rotateLeft(QMapNodeBase *x);
188 void rotateRight(QMapNodeBase *x);
189 void rebalance(QMapNodeBase *x);
190 void freeNodeAndRebalance(QMapNodeBase *z);
191 void recalcMostLeftNode();
192
193 QMapNodeBase *createNode(int size, int alignment, QMapNodeBase *parent, bool left);
194 void freeTree(QMapNodeBase *root, int alignment);
195
196 static const QMapDataBase shared_null;
197
198 static QMapDataBase *createData();
199 static void freeData(QMapDataBase *d);
200};
201
202template <class Key, class T>
203struct QMapData : public QMapDataBase
204{
205 typedef QMapNode<Key, T> Node;
206
207 Node *root() const { return static_cast<Node *>(header.left); }
208
209 // using reinterpret_cast because QMapDataBase::header is not
210 // actually a QMapNode.
211 const Node *end() const { return reinterpret_cast<const Node *>(&header); }
212 Node *end() { return reinterpret_cast<Node *>(&header); }
213 const Node *begin() const { if (root()) return static_cast<const Node*>(mostLeftNode); return end(); }
214 Node *begin() { if (root()) return static_cast<Node*>(mostLeftNode); return end(); }
215
216 void deleteNode(Node *z);
217 Node *findNode(const Key &akey) const;
218 void nodeRange(const Key &akey, Node **firstNode, Node **lastNode);
219
220 Node *createNode(const Key &k, const T &v, Node *parent = nullptr, bool left = false)
221 {
222 Node *n = static_cast<Node *>(QMapDataBase::createNode(sizeof(Node), Q_ALIGNOF(Node),
223 parent, left));
224 QT_TRY {
225 new (&n->key) Key(k);
226 QT_TRY {
227 new (&n->value) T(v);
228 } QT_CATCH(...) {
229 n->key.~Key();
230 QT_RETHROW;
231 }
232 } QT_CATCH(...) {
233 QMapDataBase::freeNodeAndRebalance(n);
234 QT_RETHROW;
235 }
236 return n;
237 }
238
239 static QMapData *create() {
240 return static_cast<QMapData *>(createData());
241 }
242
243 void destroy() {
244 if (root()) {
245 root()->destroySubTree();
246 freeTree(header.left, Q_ALIGNOF(Node));
247 }
248 freeData(this);
249 }
250};
251
252template <class Key, class T>
253QMapNode<Key, T> *QMapNode<Key, T>::copy(QMapData<Key, T> *d) const
254{
255 QMapNode<Key, T> *n = d->createNode(key, value);
256 n->setColor(color());
257 if (left) {
258 n->left = leftNode()->copy(d);
259 n->left->setParent(n);
260 } else {
261 n->left = nullptr;
262 }
263 if (right) {
264 n->right = rightNode()->copy(d);
265 n->right->setParent(n);
266 } else {
267 n->right = nullptr;
268 }
269 return n;
270}
271
272template <class Key, class T>
273void QMapData<Key, T>::deleteNode(QMapNode<Key, T> *z)
274{
275 QMapNodeBase::callDestructorIfNecessary(z->key);
276 QMapNodeBase::callDestructorIfNecessary(z->value);
277 freeNodeAndRebalance(z);
278}
279
280template <class Key, class T>
281QMapNode<Key, T> *QMapData<Key, T>::findNode(const Key &akey) const
282{
283 if (Node *r = root()) {
284 Node *lb = r->lowerBound(akey);
285 if (lb && !qMapLessThanKey(akey, lb->key))
286 return lb;
287 }
288 return nullptr;
289}
290
291
292template <class Key, class T>
293void QMapData<Key, T>::nodeRange(const Key &akey, QMapNode<Key, T> **firstNode, QMapNode<Key, T> **lastNode)
294{
295 Node *n = root();
296 Node *l = end();
297 while (n) {
298 if (qMapLessThanKey(akey, n->key)) {
299 l = n;
300 n = n->leftNode();
301 } else if (qMapLessThanKey(n->key, akey)) {
302 n = n->rightNode();
303 } else {
304 *firstNode = n->leftNode() ? n->leftNode()->lowerBound(akey) : nullptr;
305 if (!*firstNode)
306 *firstNode = n;
307 *lastNode = n->rightNode() ? n->rightNode()->upperBound(akey) : nullptr;
308 if (!*lastNode)
309 *lastNode = l;
310 return;
311 }
312 }
313 *firstNode = *lastNode = l;
314}
315
316
317template <class Key, class T>
318class QMap
319{
320 typedef QMapNode<Key, T> Node;
321
322 QMapData<Key, T> *d;
323
324public:
325 inline QMap() noexcept : d(static_cast<QMapData<Key, T> *>(const_cast<QMapDataBase *>(&QMapDataBase::shared_null))) { }
326 inline QMap(std::initializer_list<std::pair<Key,T> > list)
327 : d(static_cast<QMapData<Key, T> *>(const_cast<QMapDataBase *>(&QMapDataBase::shared_null)))
328 {
329 for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it)
330 insert(it->first, it->second);
331 }
332 QMap(const QMap<Key, T> &other);
333
334 inline ~QMap() { if (!d->ref.deref()) d->destroy(); }
335
336 QMap<Key, T> &operator=(const QMap<Key, T> &other);
337 inline QMap(QMap<Key, T> &&other) noexcept
338 : d(other.d)
339 {
340 other.d = static_cast<QMapData<Key, T> *>(
341 const_cast<QMapDataBase *>(&QMapDataBase::shared_null));
342 }
343
344 inline QMap<Key, T> &operator=(QMap<Key, T> &&other) noexcept
345 { QMap moved(std::move(other)); swap(moved); return *this; }
346 inline void swap(QMap<Key, T> &other) noexcept { qSwap(d, other.d); }
347 explicit QMap(const typename std::map<Key, T> &other);
348 std::map<Key, T> toStdMap() const;
349
350 bool operator==(const QMap<Key, T> &other) const;
351 inline bool operator!=(const QMap<Key, T> &other) const { return !(*this == other); }
352
353 inline int size() const { return d->size; }
354
355 inline bool isEmpty() const { return d->size == 0; }
356
357 inline void detach() { if (d->ref.isShared()) detach_helper(); }
358 inline bool isDetached() const { return !d->ref.isShared(); }
359#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
360 inline void setSharable(bool sharable)
361 {
362 if (sharable == d->ref.isSharable())
363 return;
364 if (!sharable)
365 detach();
366 // Don't call on shared_null
367 d->ref.setSharable(sharable);
368 }
369#endif
370 inline bool isSharedWith(const QMap<Key, T> &other) const { return d == other.d; }
371
372 void clear();
373
374 int remove(const Key &key);
375 T take(const Key &key);
376
377 bool contains(const Key &key) const;
378 const Key key(const T &value, const Key &defaultKey = Key()) const;
379 const T value(const Key &key, const T &defaultValue = T()) const;
380 T &operator[](const Key &key);
381 const T operator[](const Key &key) const;
382
383 QList<Key> keys() const;
384 QList<Key> keys(const T &value) const;
385 QList<T> values() const;
386#if QT_DEPRECATED_SINCE(5, 15)
387 QT_DEPRECATED_VERSION_X_5_15("Use QMultiMap for maps storing multiple values with the same key.") QList<Key> uniqueKeys() const;
388 QT_DEPRECATED_VERSION_X_5_15("Use QMultiMap for maps storing multiple values with the same key.") QList<T> values(const Key &key) const;
389#endif
390 int count(const Key &key) const;
391
392
393 inline const Key &firstKey() const { Q_ASSERT(!isEmpty()); return constBegin().key(); }
394 inline const Key &lastKey() const { Q_ASSERT(!isEmpty()); return (constEnd() - 1).key(); }
395
396 inline T &first() { Q_ASSERT(!isEmpty()); return *begin(); }
397 inline const T &first() const { Q_ASSERT(!isEmpty()); return *constBegin(); }
398 inline T &last() { Q_ASSERT(!isEmpty()); return *(end() - 1); }
399 inline const T &last() const { Q_ASSERT(!isEmpty()); return *(constEnd() - 1); }
400
401 class const_iterator;
402
403 class iterator
404 {
405 friend class const_iterator;
406 Node *i;
407
408 public:
409 typedef std::bidirectional_iterator_tag iterator_category;
410 typedef qptrdiff difference_type;
411 typedef T value_type;
412 typedef T *pointer;
413 typedef T &reference;
414
415 inline iterator() : i(nullptr) { }
416 inline iterator(Node *node) : i(node) { }
417
418 inline const Key &key() const { return i->key; }
419 inline T &value() const { return i->value; }
420 inline T &operator*() const { return i->value; }
421 inline T *operator->() const { return &i->value; }
422 inline bool operator==(const iterator &o) const { return i == o.i; }
423 inline bool operator!=(const iterator &o) const { return i != o.i; }
424
425 inline iterator &operator++() {
426 i = i->nextNode();
427 return *this;
428 }
429 inline iterator operator++(int) {
430 iterator r = *this;
431 i = i->nextNode();
432 return r;
433 }
434 inline iterator &operator--() {
435 i = i->previousNode();
436 return *this;
437 }
438 inline iterator operator--(int) {
439 iterator r = *this;
440 i = i->previousNode();
441 return r;
442 }
443 inline iterator operator+(int j) const
444 { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
445 inline iterator operator-(int j) const { return operator+(-j); }
446 inline iterator &operator+=(int j) { return *this = *this + j; }
447 inline iterator &operator-=(int j) { return *this = *this - j; }
448 friend inline iterator operator+(int j, iterator k) { return k + j; }
449
450#ifndef QT_STRICT_ITERATORS
451 public:
452 inline bool operator==(const const_iterator &o) const
453 { return i == o.i; }
454 inline bool operator!=(const const_iterator &o) const
455 { return i != o.i; }
456#endif
457 friend class QMap<Key, T>;
458 friend class QMultiMap<Key, T>;
459 };
460 friend class iterator;
461
462 class const_iterator
463 {
464 friend class iterator;
465 const Node *i;
466
467 public:
468 typedef std::bidirectional_iterator_tag iterator_category;
469 typedef qptrdiff difference_type;
470 typedef T value_type;
471 typedef const T *pointer;
472 typedef const T &reference;
473
474 Q_DECL_CONSTEXPR inline const_iterator() : i(nullptr) { }
475 inline const_iterator(const Node *node) : i(node) { }
476#ifdef QT_STRICT_ITERATORS
477 explicit inline const_iterator(const iterator &o)
478#else
479 inline const_iterator(const iterator &o)
480#endif
481 { i = o.i; }
482
483 inline const Key &key() const { return i->key; }
484 inline const T &value() const { return i->value; }
485 inline const T &operator*() const { return i->value; }
486 inline const T *operator->() const { return &i->value; }
487 Q_DECL_CONSTEXPR inline bool operator==(const const_iterator &o) const { return i == o.i; }
488 Q_DECL_CONSTEXPR inline bool operator!=(const const_iterator &o) const { return i != o.i; }
489
490 inline const_iterator &operator++() {
491 i = i->nextNode();
492 return *this;
493 }
494 inline const_iterator operator++(int) {
495 const_iterator r = *this;
496 i = i->nextNode();
497 return r;
498 }
499 inline const_iterator &operator--() {
500 i = i->previousNode();
501 return *this;
502 }
503 inline const_iterator operator--(int) {
504 const_iterator r = *this;
505 i = i->previousNode();
506 return r;
507 }
508 inline const_iterator operator+(int j) const
509 { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
510 inline const_iterator operator-(int j) const { return operator+(-j); }
511 inline const_iterator &operator+=(int j) { return *this = *this + j; }
512 inline const_iterator &operator-=(int j) { return *this = *this - j; }
513 friend inline const_iterator operator+(int j, const_iterator k) { return k + j; }
514
515#ifdef QT_STRICT_ITERATORS
516 private:
517 inline bool operator==(const iterator &o) const { return operator==(const_iterator(o)); }
518 inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); }
519#endif
520 friend class QMap<Key, T>;
521 friend class QMultiMap<Key, T>;
522 };
523 friend class const_iterator;
524
525 class key_iterator
526 {
527 const_iterator i;
528
529 public:
530 typedef typename const_iterator::iterator_category iterator_category;
531 typedef typename const_iterator::difference_type difference_type;
532 typedef Key value_type;
533 typedef const Key *pointer;
534 typedef const Key &reference;
535
536 key_iterator() = default;
537 explicit key_iterator(const_iterator o) : i(o) { }
538
539 const Key &operator*() const { return i.key(); }
540 const Key *operator->() const { return &i.key(); }
541 bool operator==(key_iterator o) const { return i == o.i; }
542 bool operator!=(key_iterator o) const { return i != o.i; }
543
544 inline key_iterator &operator++() { ++i; return *this; }
545 inline key_iterator operator++(int) { return key_iterator(i++);}
546 inline key_iterator &operator--() { --i; return *this; }
547 inline key_iterator operator--(int) { return key_iterator(i--); }
548 const_iterator base() const { return i; }
549 };
550
551 typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator;
552 typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator;
553
554 // STL style
555 inline iterator begin() { detach(); return iterator(d->begin()); }
556 inline const_iterator begin() const { return const_iterator(d->begin()); }
557 inline const_iterator constBegin() const { return const_iterator(d->begin()); }
558 inline const_iterator cbegin() const { return const_iterator(d->begin()); }
559 inline iterator end() { detach(); return iterator(d->end()); }
560 inline const_iterator end() const { return const_iterator(d->end()); }
561 inline const_iterator constEnd() const { return const_iterator(d->end()); }
562 inline const_iterator cend() const { return const_iterator(d->end()); }
563 inline key_iterator keyBegin() const { return key_iterator(begin()); }
564 inline key_iterator keyEnd() const { return key_iterator(end()); }
565 inline key_value_iterator keyValueBegin() { return key_value_iterator(begin()); }
566 inline key_value_iterator keyValueEnd() { return key_value_iterator(end()); }
567 inline const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); }
568 inline const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); }
569 inline const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); }
570 inline const_key_value_iterator constKeyValueEnd() const { return const_key_value_iterator(end()); }
571 iterator erase(iterator it);
572
573 // more Qt
574 typedef iterator Iterator;
575 typedef const_iterator ConstIterator;
576 inline int count() const { return d->size; }
577 iterator find(const Key &key);
578 const_iterator find(const Key &key) const;
579 const_iterator constFind(const Key &key) const;
580 iterator lowerBound(const Key &key);
581 const_iterator lowerBound(const Key &key) const;
582 iterator upperBound(const Key &key);
583 const_iterator upperBound(const Key &key) const;
584 iterator insert(const Key &key, const T &value);
585 iterator insert(const_iterator pos, const Key &key, const T &value);
586 void insert(const QMap<Key, T> &map);
587#if QT_DEPRECATED_SINCE(5, 15)
588 QT_DEPRECATED_VERSION_X_5_15("Use QMultiMap for maps storing multiple values with the same key.") iterator insertMulti(const Key &key, const T &value);
589 QT_DEPRECATED_VERSION_X_5_15("Use QMultiMap for maps storing multiple values with the same key.") iterator insertMulti(const_iterator pos, const Key &akey, const T &avalue);
590 QT_DEPRECATED_VERSION_X_5_15("Use QMultiMap for maps storing multiple values with the same key.") QMap<Key, T> &unite(const QMap<Key, T> &other);
591#endif
592
593 // STL compatibility
594 typedef Key key_type;
595 typedef T mapped_type;
596 typedef qptrdiff difference_type;
597 typedef int size_type;
598 inline bool empty() const { return isEmpty(); }
599 QPair<iterator, iterator> equal_range(const Key &akey);
600 QPair<const_iterator, const_iterator> equal_range(const Key &akey) const;
601
602#ifdef Q_MAP_DEBUG
603 void dump() const;
604#endif
605
606private:
607 void detach_helper();
608 bool isValidIterator(const const_iterator &ci) const
609 {
610#if defined(QT_DEBUG) && !defined(Q_MAP_NO_ITERATOR_DEBUG)
611 const QMapNodeBase *n = ci.i;
612 while (n->parent())
613 n = n->parent();
614 return n->left == d->root();
615#else
616 Q_UNUSED(ci);
617 return true;
618#endif
619 }
620
621 friend class QMultiMap<Key, T>;
622};
623
624template <class Key, class T>
625inline QMap<Key, T>::QMap(const QMap<Key, T> &other)
626{
627 if (other.d->ref.ref()) {
628 d = other.d;
629 } else {
630 d = QMapData<Key, T>::create();
631 if (other.d->header.left) {
632 d->header.left = static_cast<Node *>(other.d->header.left)->copy(d);
633 d->header.left->setParent(&d->header);
634 d->recalcMostLeftNode();
635 }
636 }
637}
638
639template <class Key, class T>
640Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other)
641{
642 if (d != other.d) {
643 QMap<Key, T> tmp(other);
644 tmp.swap(*this);
645 }
646 return *this;
647}
648
649template <class Key, class T>
650Q_INLINE_TEMPLATE void QMap<Key, T>::clear()
651{
652 *this = QMap<Key, T>();
653}
654
655QT_WARNING_PUSH
656QT_WARNING_DISABLE_CLANG("-Wreturn-stack-address")
657
658template <class Key, class T>
659Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey, const T &adefaultValue) const
660{
661 Node *n = d->findNode(akey);
662 return n ? n->value : adefaultValue;
663}
664
665QT_WARNING_POP
666
667template <class Key, class T>
668Q_INLINE_TEMPLATE const T QMap<Key, T>::operator[](const Key &akey) const
669{
670 return value(akey);
671}
672
673template <class Key, class T>
674Q_INLINE_TEMPLATE T &QMap<Key, T>::operator[](const Key &akey)
675{
676 detach();
677 Node *n = d->findNode(akey);
678 if (!n)
679 return *insert(akey, T());
680 return n->value;
681}
682
683template <class Key, class T>
684Q_INLINE_TEMPLATE int QMap<Key, T>::count(const Key &akey) const
685{
686 Node *firstNode;
687 Node *lastNode;
688 d->nodeRange(akey, &firstNode, &lastNode);
689
690 const_iterator ci_first(firstNode);
691 const const_iterator ci_last(lastNode);
692 int cnt = 0;
693 while (ci_first != ci_last) {
694 ++cnt;
695 ++ci_first;
696 }
697 return cnt;
698}
699
700template <class Key, class T>
701Q_INLINE_TEMPLATE bool QMap<Key, T>::contains(const Key &akey) const
702{
703 return d->findNode(akey) != nullptr;
704}
705
706template <class Key, class T>
707Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey, const T &avalue)
708{
709 detach();
710 Node *n = d->root();
711 Node *y = d->end();
712 Node *lastNode = nullptr;
713 bool left = true;
714 while (n) {
715 y = n;
716 if (!qMapLessThanKey(n->key, akey)) {
717 lastNode = n;
718 left = true;
719 n = n->leftNode();
720 } else {
721 left = false;
722 n = n->rightNode();
723 }
724 }
725 if (lastNode && !qMapLessThanKey(akey, lastNode->key)) {
726 lastNode->value = avalue;
727 return iterator(lastNode);
728 }
729 Node *z = d->createNode(akey, avalue, y, left);
730 return iterator(z);
731}
732
733template <class Key, class T>
734typename QMap<Key, T>::iterator QMap<Key, T>::insert(const_iterator pos, const Key &akey, const T &avalue)
735{
736 if (d->ref.isShared())
737 return this->insert(akey, avalue);
738
739 Q_ASSERT_X(isValidIterator(pos), "QMap::insert", "The specified const_iterator argument 'it' is invalid");
740
741 if (pos == constEnd()) {
742 // Hint is that the Node is larger than (or equal to) the largest value.
743 Node *n = static_cast<Node *>(pos.i->left);
744 if (n) {
745 while (n->right)
746 n = static_cast<Node *>(n->right);
747
748 if (!qMapLessThanKey(n->key, akey))
749 return this->insert(akey, avalue); // ignore hint
750 // This can be optimized by checking equal too.
751 // we can overwrite if previous node key is strictly smaller
752 // (or there is no previous node)
753
754 Node *z = d->createNode(akey, avalue, n, false); // insert right most
755 return iterator(z);
756 }
757 return this->insert(akey, avalue);
758 } else {
759 // Hint indicates that the node should be less (or equal to) the hint given
760 // but larger than the previous value.
761 Node *next = const_cast<Node*>(pos.i);
762 if (qMapLessThanKey(next->key, akey))
763 return this->insert(akey, avalue); // ignore hint
764
765 if (pos == constBegin()) {
766 // There is no previous value
767 // Maybe overwrite left most value
768 if (!qMapLessThanKey(akey, next->key)) {
769 next->value = avalue; // overwrite current iterator
770 return iterator(next);
771 }
772 // insert left most.
773 Node *z = d->createNode(akey, avalue, begin().i, true);
774 return iterator(z);
775 } else {
776 Node *prev = const_cast<Node*>(pos.i->previousNode());
777 if (!qMapLessThanKey(prev->key, akey)) {
778 return this->insert(akey, avalue); // ignore hint
779 }
780 // Hint is ok
781 if (!qMapLessThanKey(akey, next->key)) {
782 next->value = avalue; // overwrite current iterator
783 return iterator(next);
784 }
785
786 // we need to insert (not overwrite)
787 if (prev->right == nullptr) {
788 Node *z = d->createNode(akey, avalue, prev, false);
789 return iterator(z);
790 }
791 if (next->left == nullptr) {
792 Node *z = d->createNode(akey, avalue, next, true);
793 return iterator(z);
794 }
795 Q_ASSERT(false); // We should have prev->right == nullptr or next->left == nullptr.
796 return this->insert(akey, avalue);
797 }
798 }
799}
800
801template <class Key, class T>
802Q_INLINE_TEMPLATE void QMap<Key, T>::insert(const QMap<Key, T> &map)
803{
804 if (d == map.d)
805 return;
806
807 detach();
808
809 Node *n = d->root();
810 auto it = map.cbegin();
811 const auto e = map.cend();
812 while (it != e) {
813 // Insertion here is based on insert(Key, T)
814 auto parent = d->end();
815 bool left = true;
816 Node *lastNode = nullptr;
817 while (n) {
818 parent = n;
819 if (!qMapLessThanKey(n->key, it.key())) {
820 lastNode = n;
821 n = n->leftNode();
822 left = true;
823 } else {
824 n = n->rightNode();
825 left = false;
826 }
827 }
828 if (lastNode && !qMapLessThanKey(it.key(), lastNode->key)) {
829 lastNode->value = it.value();
830 n = lastNode;
831 } else {
832 n = d->createNode(it.key(), it.value(), parent, left);
833 }
834 ++it;
835 if (it != e) {
836 // Move back up the tree until we find the next branch or node which is
837 // relevant for the next key.
838 while (n != d->root() && qMapLessThanKey(n->key, it.key()))
839 n = static_cast<Node *>(n->parent());
840 }
841 }
842}
843
844
845template <class Key, class T>
846Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::constFind(const Key &akey) const
847{
848 Node *n = d->findNode(akey);
849 return const_iterator(n ? n : d->end());
850}
851
852template <class Key, class T>
853Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &akey) const
854{
855 return constFind(akey);
856}
857
858template <class Key, class T>
859Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::find(const Key &akey)
860{
861 detach();
862 Node *n = d->findNode(akey);
863 return iterator(n ? n : d->end());
864}
865
866template <class Key, class T>
867QPair<typename QMap<Key, T>::iterator, typename QMap<Key, T>::iterator> QMap<Key, T>::equal_range(const Key &akey)
868{
869 detach();
870 Node *firstNode, *lastNode;
871 d->nodeRange(akey, &firstNode, &lastNode);
872 return QPair<iterator, iterator>(iterator(firstNode), iterator(lastNode));
873}
874
875template <class Key, class T>
876QPair<typename QMap<Key, T>::const_iterator, typename QMap<Key, T>::const_iterator>
877QMap<Key, T>::equal_range(const Key &akey) const
878{
879 Node *firstNode, *lastNode;
880 d->nodeRange(akey, &firstNode, &lastNode);
881 return qMakePair(const_iterator(firstNode), const_iterator(lastNode));
882}
883
884#ifdef Q_MAP_DEBUG
885template <class Key, class T>
886void QMap<Key, T>::dump() const
887{
888 const_iterator it = begin();
889 qDebug("map dump:");
890 while (it != end()) {
891 const QMapNodeBase *n = it.i;
892 int depth = 0;
893 while (n && n != d->root()) {
894 ++depth;
895 n = n->parent();
896 }
897 QByteArray space(4*depth, ' ');
898 qDebug() << space << (it.i->color() == Node::Red ? "Red " : "Black") << it.i << it.i->left << it.i->right
899 << it.key() << it.value();
900 ++it;
901 }
902 qDebug("---------");
903}
904#endif
905
906template <class Key, class T>
907Q_OUTOFLINE_TEMPLATE int QMap<Key, T>::remove(const Key &akey)
908{
909 detach();
910 int n = 0;
911 while (Node *node = d->findNode(akey)) {
912 d->deleteNode(node);
913 ++n;
914 }
915 return n;
916}
917
918template <class Key, class T>
919Q_OUTOFLINE_TEMPLATE T QMap<Key, T>::take(const Key &akey)
920{
921 detach();
922
923 Node *node = d->findNode(akey);
924 if (node) {
925 T t = std::move(node->value);
926 d->deleteNode(node);
927 return t;
928 }
929 return T();
930}
931
932template <class Key, class T>
933Q_OUTOFLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::erase(iterator it)
934{
935 if (it == iterator(d->end()))
936 return it;
937
938 Q_ASSERT_X(isValidIterator(const_iterator(it)), "QMap::erase", "The specified iterator argument 'it' is invalid");
939
940 if (d->ref.isShared()) {
941 const_iterator oldBegin = constBegin();
942 const_iterator old = const_iterator(it);
943 int backStepsWithSameKey = 0;
944
945 while (old != oldBegin) {
946 --old;
947 if (qMapLessThanKey(old.key(), it.key()))
948 break;
949 ++backStepsWithSameKey;
950 }
951
952 it = find(old.key()); // ensures detach
953 Q_ASSERT_X(it != iterator(d->end()), "QMap::erase", "Unable to locate same key in erase after detach.");
954
955 while (backStepsWithSameKey > 0) {
956 ++it;
957 --backStepsWithSameKey;
958 }
959 }
960
961 Node *n = it.i;
962 ++it;
963 d->deleteNode(n);
964 return it;
965}
966
967template <class Key, class T>
968Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::detach_helper()
969{
970 QMapData<Key, T> *x = QMapData<Key, T>::create();
971 if (d->header.left) {
972 x->header.left = static_cast<Node *>(d->header.left)->copy(x);
973 x->header.left->setParent(&x->header);
974 }
975 if (!d->ref.deref())
976 d->destroy();
977 d = x;
978 d->recalcMostLeftNode();
979}
980
981template <class Key, class T>
982Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys() const
983{
984 QList<Key> res;
985 res.reserve(size());
986 const_iterator i = begin();
987 while (i != end()) {
988 res.append(i.key());
989 ++i;
990 }
991 return res;
992}
993
994template <class Key, class T>
995Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys(const T &avalue) const
996{
997 QList<Key> res;
998 const_iterator i = begin();
999 while (i != end()) {
1000 if (i.value() == avalue)
1001 res.append(i.key());
1002 ++i;
1003 }
1004 return res;
1005}
1006
1007template <class Key, class T>
1008Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T &avalue, const Key &defaultKey) const
1009{
1010 const_iterator i = begin();
1011 while (i != end()) {
1012 if (i.value() == avalue)
1013 return i.key();
1014 ++i;
1015 }
1016
1017 return defaultKey;
1018}
1019
1020template <class Key, class T>
1021Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values() const
1022{
1023 QList<T> res;
1024 res.reserve(size());
1025 const_iterator i = begin();
1026 while (i != end()) {
1027 res.append(i.value());
1028 ++i;
1029 }
1030 return res;
1031}
1032
1033template <class Key, class T>
1034Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::lowerBound(const Key &akey) const
1035{
1036 Node *lb = d->root() ? d->root()->lowerBound(akey) : nullptr;
1037 if (!lb)
1038 lb = d->end();
1039 return const_iterator(lb);
1040}
1041
1042template <class Key, class T>
1043Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::lowerBound(const Key &akey)
1044{
1045 detach();
1046 Node *lb = d->root() ? d->root()->lowerBound(akey) : nullptr;
1047 if (!lb)
1048 lb = d->end();
1049 return iterator(lb);
1050}
1051
1052template <class Key, class T>
1053Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator
1054QMap<Key, T>::upperBound(const Key &akey) const
1055{
1056 Node *ub = d->root() ? d->root()->upperBound(akey) : nullptr;
1057 if (!ub)
1058 ub = d->end();
1059 return const_iterator(ub);
1060}
1061
1062template <class Key, class T>
1063Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::upperBound(const Key &akey)
1064{
1065 detach();
1066 Node *ub = d->root() ? d->root()->upperBound(akey) : nullptr;
1067 if (!ub)
1068 ub = d->end();
1069 return iterator(ub);
1070}
1071
1072template <class Key, class T>
1073Q_OUTOFLINE_TEMPLATE bool QMap<Key, T>::operator==(const QMap<Key, T> &other) const
1074{
1075 if (size() != other.size())
1076 return false;
1077 if (d == other.d)
1078 return true;
1079
1080 const_iterator it1 = begin();
1081 const_iterator it2 = other.begin();
1082
1083 while (it1 != end()) {
1084 if (!(it1.value() == it2.value()) || qMapLessThanKey(it1.key(), it2.key()) || qMapLessThanKey(it2.key(), it1.key()))
1085 return false;
1086 ++it2;
1087 ++it1;
1088 }
1089 return true;
1090}
1091
1092template <class Key, class T>
1093Q_OUTOFLINE_TEMPLATE QMap<Key, T>::QMap(const std::map<Key, T> &other)
1094{
1095 d = QMapData<Key, T>::create();
1096 typename std::map<Key,T>::const_iterator it = other.end();
1097 while (it != other.begin()) {
1098 --it;
1099 d->createNode((*it).first, (*it).second, d->begin(), true); // insert on most left node.
1100 }
1101}
1102
1103template <class Key, class T>
1104Q_OUTOFLINE_TEMPLATE std::map<Key, T> QMap<Key, T>::toStdMap() const
1105{
1106 std::map<Key, T> map;
1107 const_iterator it = end();
1108 while (it != begin()) {
1109 --it;
1110 map.insert(map.begin(), std::pair<Key, T>(it.key(), it.value()));
1111 }
1112 return map;
1113}
1114
1115template <class Key, class T>
1116class QMultiMap : public QMap<Key, T>
1117{
1118public:
1119 QMultiMap() noexcept {}
1120 inline QMultiMap(std::initializer_list<std::pair<Key,T> > list)
1121 {
1122 for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it)
1123 insert(it->first, it->second);
1124 }
1125 QMultiMap(const QMap<Key, T> &other) : QMap<Key, T>(other) {}
1126 QMultiMap(QMap<Key, T> &&other) noexcept : QMap<Key, T>(std::move(other)) {}
1127 void swap(QMultiMap<Key, T> &other) noexcept { QMap<Key, T>::swap(other); }
1128
1129 QList<Key> uniqueKeys() const;
1130 QList<T> values(const Key &key) const;
1131
1132 inline typename QMap<Key, T>::iterator replace(const Key &key, const T &value)
1133 { return QMap<Key, T>::insert(key, value); }
1134 typename QMap<Key, T>::iterator insert(const Key &key, const T &value);
1135 //! [qmultimap-insert-pos]
1136 typename QMap<Key, T>::iterator insert(typename QMap<Key, T>::const_iterator pos,
1137 const Key &key, const T &value);
1138
1139 //! [qmultimap-unite]
1140 QMultiMap &unite(const QMultiMap &other);
1141 inline QMultiMap &operator+=(const QMultiMap &other)
1142 { return unite(other); }
1143 inline QMultiMap operator+(const QMultiMap &other) const
1144 { QMultiMap result = *this; result += other; return result; }
1145
1146 using QMap<Key, T>::contains;
1147 using QMap<Key, T>::remove;
1148 using QMap<Key, T>::count;
1149 using QMap<Key, T>::find;
1150 using QMap<Key, T>::constFind;
1151 using QMap<Key, T>::values;
1152 using QMap<Key, T>::size;
1153 using QMap<Key, T>::detach;
1154 using QMap<Key, T>::erase;
1155 using QMap<Key, T>::isValidIterator;
1156 using typename QMap<Key, T>::Node;
1157
1158 bool contains(const Key &key, const T &value) const;
1159
1160 int remove(const Key &key, const T &value);
1161
1162 int count(const Key &key, const T &value) const;
1163
1164 typename QMap<Key, T>::iterator find(const Key &key, const T &value) {
1165 typename QMap<Key, T>::iterator i(find(key));
1166 typename QMap<Key, T>::iterator end(this->end());
1167 while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
1168 if (i.value() == value)
1169 return i;
1170 ++i;
1171 }
1172 return end;
1173 }
1174 typename QMap<Key, T>::const_iterator find(const Key &key, const T &value) const {
1175 typename QMap<Key, T>::const_iterator i(constFind(key));
1176 typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());
1177 while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
1178 if (i.value() == value)
1179 return i;
1180 ++i;
1181 }
1182 return end;
1183 }
1184 typename QMap<Key, T>::const_iterator constFind(const Key &key, const T &value) const
1185 { return find(key, value); }
1186private:
1187 T &operator[](const Key &key);
1188 const T operator[](const Key &key) const;
1189};
1190
1191template <class Key, class T>
1192Q_OUTOFLINE_TEMPLATE QList<Key> QMultiMap<Key, T>::uniqueKeys() const
1193{
1194 QList<Key> res;
1195 res.reserve(size()); // May be too much, but assume short lifetime
1196 typename QMap<Key, T>::const_iterator i = this->begin();
1197 if (i != this->end()) {
1198 for (;;) {
1199 const Key &aKey = i.key();
1200 res.append(aKey);
1201 do {
1202 if (++i == this->end())
1203 goto break_out_of_outer_loop;
1204 } while (!qMapLessThanKey(aKey, i.key())); // loop while (key == i.key())
1205 }
1206 }
1207break_out_of_outer_loop:
1208 return res;
1209}
1210
1211template <class Key, class T>
1212Q_OUTOFLINE_TEMPLATE QList<T> QMultiMap<Key, T>::values(const Key &akey) const
1213{
1214 QList<T> res;
1215 Node *n = this->d->findNode(akey);
1216 if (n) {
1217 typename QMap<Key, T>::const_iterator it(n);
1218 do {
1219 res.append(*it);
1220 ++it;
1221 } while (it != this->constEnd() && !qMapLessThanKey<Key>(akey, it.key()));
1222 }
1223 return res;
1224}
1225
1226template <class Key, class T>
1227Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMultiMap<Key, T>::insert(const Key &akey,
1228 const T &avalue)
1229{
1230 detach();
1231 Node* y = this->d->end();
1232 Node* x = static_cast<Node *>(this->d->root());
1233 bool left = true;
1234 while (x != nullptr) {
1235 left = !qMapLessThanKey(x->key, akey);
1236 y = x;
1237 x = left ? x->leftNode() : x->rightNode();
1238 }
1239 Node *z = this->d->createNode(akey, avalue, y, left);
1240 return typename QMap<Key, T>::iterator(z);
1241}
1242
1243#ifndef Q_CLANG_QDOC
1244template <class Key, class T>
1245typename QMap<Key, T>::iterator QMultiMap<Key, T>::insert(typename QMap<Key, T>::const_iterator pos,
1246 const Key &akey, const T &avalue)
1247{
1248 if (this->d->ref.isShared())
1249 return insert(akey, avalue);
1250
1251 Q_ASSERT_X(isValidIterator(pos), "QMap::insert", "The specified const_iterator argument 'pos' is invalid");
1252
1253 if (pos == this->constEnd()) {
1254 // Hint is that the Node is larger than (or equal to) the largest value.
1255 Node *n = static_cast<Node *>(pos.i->left);
1256 if (n) {
1257 while (n->right)
1258 n = static_cast<Node *>(n->right);
1259
1260 if (!qMapLessThanKey(n->key, akey))
1261 return insert(akey, avalue); // ignore hint
1262 Node *z = this->d->createNode(akey, avalue, n, false); // insert right most
1263 return typename QMap<Key, T>::iterator(z);
1264 }
1265 return insert(akey, avalue);
1266 } else {
1267 // Hint indicates that the node should be less (or equal to) the hint given
1268 // but larger than the previous value.
1269 Node *next = const_cast<Node*>(pos.i);
1270 if (qMapLessThanKey(next->key, akey))
1271 return insert(akey, avalue); // ignore hint
1272
1273 if (pos == this->constBegin()) {
1274 // There is no previous value (insert left most)
1275 Node *z = this->d->createNode(akey, avalue, this->begin().i, true);
1276 return typename QMap<Key, T>::iterator(z);
1277 } else {
1278 Node *prev = const_cast<Node*>(pos.i->previousNode());
1279 if (!qMapLessThanKey(prev->key, akey))
1280 return insert(akey, avalue); // ignore hint
1281
1282 // Hint is ok - do insert
1283 if (prev->right == nullptr) {
1284 Node *z = this->d->createNode(akey, avalue, prev, false);
1285 return typename QMap<Key, T>::iterator(z);
1286 }
1287 if (next->left == nullptr) {
1288 Node *z = this->d->createNode(akey, avalue, next, true);
1289 return typename QMap<Key, T>::iterator(z);
1290 }
1291 Q_ASSERT(false); // We should have prev->right == nullptr or next->left == nullptr.
1292 return insert(akey, avalue);
1293 }
1294 }
1295}
1296
1297template <class Key, class T>
1298Q_INLINE_TEMPLATE QMultiMap<Key, T> &QMultiMap<Key, T>::unite(const QMultiMap<Key, T> &other)
1299{
1300 QMultiMap<Key, T> copy(other);
1301 typename QMap<Key, T>::const_iterator it = copy.constEnd();
1302 const typename QMap<Key, T>::const_iterator b = copy.constBegin();
1303 while (it != b) {
1304 --it;
1305 insert(it.key(), it.value());
1306 }
1307 return *this;
1308}
1309#endif // Q_CLANG_QDOC
1310
1311template <class Key, class T>
1312Q_INLINE_TEMPLATE bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const
1313{
1314 return constFind(key, value) != QMap<Key, T>::constEnd();
1315}
1316
1317template <class Key, class T>
1318Q_INLINE_TEMPLATE int QMultiMap<Key, T>::remove(const Key &key, const T &value)
1319{
1320 int n = 0;
1321 typename QMap<Key, T>::iterator i(find(key));
1322 typename QMap<Key, T>::iterator end(QMap<Key, T>::end());
1323 while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
1324 if (i.value() == value) {
1325 i = erase(i);
1326 ++n;
1327 } else {
1328 ++i;
1329 }
1330 }
1331 return n;
1332}
1333
1334template <class Key, class T>
1335Q_INLINE_TEMPLATE int QMultiMap<Key, T>::count(const Key &key, const T &value) const
1336{
1337 int n = 0;
1338 typename QMap<Key, T>::const_iterator i(constFind(key));
1339 typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());
1340 while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
1341 if (i.value() == value)
1342 ++n;
1343 ++i;
1344 }
1345 return n;
1346}
1347
1348#if QT_DEPRECATED_SINCE(5, 15)
1349template<class Key, class T>
1350QList<Key> QMap<Key, T>::uniqueKeys() const
1351{
1352 return static_cast<const QMultiMap<Key, T> *>(this)->uniqueKeys();
1353}
1354
1355template<class Key, class T>
1356QList<T> QMap<Key, T>::values(const Key &key) const
1357{
1358 return static_cast<const QMultiMap<Key, T> *>(this)->values(key);
1359}
1360
1361template<class Key, class T>
1362typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &key, const T &value)
1363{
1364 return static_cast<QMultiMap<Key, T> *>(this)->insert(key, value);
1365}
1366
1367template<class Key, class T>
1368typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const_iterator pos, const Key &akey, const T &avalue)
1369{
1370 return static_cast<QMultiMap<Key, T> *>(this)->insert(pos, akey, avalue);
1371}
1372
1373template<class Key, class T>
1374QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other)
1375{
1376 return static_cast<QMultiMap<Key, T> *>(this)->unite(other);
1377}
1378#endif
1379
1380Q_DECLARE_ASSOCIATIVE_ITERATOR(Map)
1381Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map)
1382
1383QT_END_NAMESPACE
1384
1385#endif // QMAP_H
1386

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