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

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