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
57 QT_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
qMapLessThanKey(const Key & key1,const Key & key2)66 template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key2)
67 {
68 return key1 < key2;
69 }
70
qMapLessThanKey(const Ptr * key1,const Ptr * key2)71 template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2)
72 {
73 return std::less<const Ptr *>()(key1, key2);
74 }
75
76 struct QMapDataBase;
77 template <class Key, class T> struct QMapData;
78
79 struct 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;
nextNodeQMapNodeBase89 QMapNodeBase *nextNode() { return const_cast<QMapNodeBase *>(const_cast<const QMapNodeBase *>(this)->nextNode()); }
90 const QMapNodeBase *previousNode() const;
previousNodeQMapNodeBase91 QMapNodeBase *previousNode() { return const_cast<QMapNodeBase *>(const_cast<const QMapNodeBase *>(this)->previousNode()); }
92
colorQMapNodeBase93 Color color() const { return Color(p & 1); }
setColorQMapNodeBase94 void setColor(Color c) { if (c == Black) p |= Black; else p &= ~Black; }
parentQMapNodeBase95 QMapNodeBase *parent() const { return reinterpret_cast<QMapNodeBase *>(p & ~Mask); }
setParentQMapNodeBase96 void setParent(QMapNodeBase *pp) { p = (p & Mask) | quintptr(pp); }
97
98 template <typename T>
99 static typename std::enable_if<QTypeInfo<T>::isComplex>::type
callDestructorIfNecessaryQMapNodeBase100 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
callDestructorIfNecessaryQMapNodeBase103 callDestructorIfNecessary(T &) noexcept {}
104 };
105
106 template <class Key, class T>
107 struct QMapNode : public QMapNodeBase
108 {
109 Key key;
110 T value;
111
leftNodeQMapNode112 inline QMapNode *leftNode() const { return static_cast<QMapNode *>(left); }
rightNodeQMapNode113 inline QMapNode *rightNode() const { return static_cast<QMapNode *>(right); }
114
nextNodeQMapNode115 inline const QMapNode *nextNode() const { return reinterpret_cast<const QMapNode *>(QMapNodeBase::nextNode()); }
previousNodeQMapNode116 inline const QMapNode *previousNode() const { return static_cast<const QMapNode *>(QMapNodeBase::previousNode()); }
nextNodeQMapNode117 inline QMapNode *nextNode() { return reinterpret_cast<QMapNode *>(QMapNodeBase::nextNode()); }
previousNodeQMapNode118 inline QMapNode *previousNode() { return static_cast<QMapNode *>(QMapNodeBase::previousNode()); }
119
120 QMapNode<Key, T> *copy(QMapData<Key, T> *d) const;
121
destroySubTreeQMapNode122 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
132 private:
doDestroySubTreeQMapNode133 void doDestroySubTree(std::false_type) {}
doDestroySubTreeQMapNode134 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
147 template <class Key, class T>
lowerBound(const Key & akey)148 inline 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
163 template <class Key, class T>
upperBound(const Key & akey)164 inline 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
181 struct 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
203 template <class Key, class T>
204 struct QMapData : public QMapDataBase
205 {
206 typedef QMapNode<Key, T> Node;
207
rootQMapData208 Node *root() const { return static_cast<Node *>(header.left); }
209
210 // using reinterpret_cast because QMapDataBase::header is not
211 // actually a QMapNode.
212 QT_WARNING_PUSH
213 QT_WARNING_DISABLE_GCC("-Wstrict-aliasing")
endQMapData214 const Node *end() const { return reinterpret_cast<const Node *>(&header); }
endQMapData215 Node *end() { return reinterpret_cast<Node *>(&header); }
216 QT_WARNING_POP
beginQMapData217 const Node *begin() const { if (root()) return static_cast<const Node*>(mostLeftNode); return end(); }
beginQMapData218 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(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);
QT_CATCHQMapData232 } QT_CATCH(...) {
233 n->key.~Key();
234 QT_RETHROW;
235 }
QT_CATCHQMapData236 } QT_CATCH(...) {
237 QMapDataBase::freeNodeAndRebalance(n);
238 QT_RETHROW;
239 }
240 return n;
241 }
242
createQMapData243 static QMapData *create() {
244 return static_cast<QMapData *>(createData());
245 }
246
destroyQMapData247 void destroy() {
248 if (root()) {
249 root()->destroySubTree();
250 freeTree(header.left, Q_ALIGNOF(Node));
251 }
252 freeData(this);
253 }
254 };
255
256 template <class Key, class T>
copy(QMapData<Key,T> * d)257 QMapNode<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
276 template <class Key, class T>
deleteNode(QMapNode<Key,T> * z)277 void QMapData<Key, T>::deleteNode(QMapNode<Key, T> *z)
278 {
279 QMapNodeBase::callDestructorIfNecessary(z->key);
280 QMapNodeBase::callDestructorIfNecessary(z->value);
281 freeNodeAndRebalance(z);
282 }
283
284 template <class Key, class T>
findNode(const Key & akey)285 QMapNode<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
296 template <class Key, class T>
nodeRange(const Key & akey,QMapNode<Key,T> ** firstNode,QMapNode<Key,T> ** lastNode)297 void 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
321 template <class Key, class T>
322 class QMap
323 {
324 typedef QMapNode<Key, T> Node;
325
326 QMapData<Key, T> *d;
327
328 public:
QMap()329 inline QMap() noexcept : d(static_cast<QMapData<Key, T> *>(const_cast<QMapDataBase *>(&QMapDataBase::shared_null))) { }
QMap(std::initializer_list<std::pair<Key,T>> list)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
~QMap()338 inline ~QMap() { if (!d->ref.deref()) d->destroy(); }
339
340 QMap<Key, T> &operator=(const QMap<Key, T> &other);
QMap(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(moved); return *this; }
swap(QMap<Key,T> & other)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
size()357 inline int size() const { return d->size; }
358
isEmpty()359 inline bool isEmpty() const { return d->size == 0; }
360
detach()361 inline void detach() { if (d->ref.isShared()) detach_helper(); }
isDetached()362 inline bool isDetached() const { return !d->ref.isShared(); }
363 #if !defined(QT_NO_UNSHARABLE_CONTAINERS)
setSharable(bool sharable)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
isSharedWith(const QMap<Key,T> & other)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
firstKey()397 inline const Key &firstKey() const { Q_ASSERT(!isEmpty()); return constBegin().key(); }
lastKey()398 inline const Key &lastKey() const { Q_ASSERT(!isEmpty()); return (constEnd() - 1).key(); }
399
first()400 inline T &first() { Q_ASSERT(!isEmpty()); return *begin(); }
first()401 inline const T &first() const { Q_ASSERT(!isEmpty()); return *constBegin(); }
last()402 inline T &last() { Q_ASSERT(!isEmpty()); return *(end() - 1); }
last()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
iterator()419 inline iterator() : i(nullptr) { }
iterator(Node * node)420 inline iterator(Node *node) : i(node) { }
421
key()422 inline const Key &key() const { return i->key; }
value()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); }
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
const_iterator()478 Q_DECL_CONSTEXPR inline const_iterator() : i(nullptr) { }
const_iterator(const Node * node)479 inline const_iterator(const Node *node) : i(node) { }
480 #ifdef QT_STRICT_ITERATORS
const_iterator(const iterator & o)481 explicit inline const_iterator(const iterator &o)
482 #else
483 inline const_iterator(const iterator &o)
484 #endif
485 { i = o.i; }
486
key()487 inline const Key &key() const { return i->key; }
value()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); }
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;
key_iterator(const_iterator o)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--); }
base()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
begin()559 inline iterator begin() { detach(); return iterator(d->begin()); }
begin()560 inline const_iterator begin() const { return const_iterator(d->begin()); }
constBegin()561 inline const_iterator constBegin() const { return const_iterator(d->begin()); }
cbegin()562 inline const_iterator cbegin() const { return const_iterator(d->begin()); }
end()563 inline iterator end() { detach(); return iterator(d->end()); }
end()564 inline const_iterator end() const { return const_iterator(d->end()); }
constEnd()565 inline const_iterator constEnd() const { return const_iterator(d->end()); }
cend()566 inline const_iterator cend() const { return const_iterator(d->end()); }
keyBegin()567 inline key_iterator keyBegin() const { return key_iterator(begin()); }
keyEnd()568 inline key_iterator keyEnd() const { return key_iterator(end()); }
keyValueBegin()569 inline key_value_iterator keyValueBegin() { return key_value_iterator(begin()); }
keyValueEnd()570 inline key_value_iterator keyValueEnd() { return key_value_iterator(end()); }
keyValueBegin()571 inline const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); }
constKeyValueBegin()572 inline const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); }
keyValueEnd()573 inline const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); }
constKeyValueEnd()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;
count()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;
empty()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
610 private:
611 void detach_helper();
isValidIterator(const const_iterator & ci)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
628 template <class Key, class T>
QMap(const QMap<Key,T> & other)629 inline 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
643 template <class Key, class T>
644 Q_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
653 template <class Key, class T>
clear()654 Q_INLINE_TEMPLATE void QMap<Key, T>::clear()
655 {
656 *this = QMap<Key, T>();
657 }
658
659 QT_WARNING_PUSH
660 QT_WARNING_DISABLE_CLANG("-Wreturn-stack-address")
661
662 template <class Key, class T>
value(const Key & akey,const T & adefaultValue)663 Q_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
669 QT_WARNING_POP
670
671 template <class Key, class T>
672 Q_INLINE_TEMPLATE const T QMap<Key, T>::operator[](const Key &akey) const
673 {
674 return value(akey);
675 }
676
677 template <class Key, class T>
678 Q_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
687 template <class Key, class T>
count(const Key & akey)688 Q_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
704 template <class Key, class T>
contains(const Key & akey)705 Q_INLINE_TEMPLATE bool QMap<Key, T>::contains(const Key &akey) const
706 {
707 return d->findNode(akey) != nullptr;
708 }
709
710 template <class Key, class T>
insert(const Key & akey,const T & avalue)711 Q_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
737 template <class Key, class T>
insert(const_iterator pos,const Key & akey,const T & avalue)738 typename 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
805 template <class Key, class T>
insert(const QMap<Key,T> & map)806 Q_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
849 template <class Key, class T>
constFind(const Key & akey)850 Q_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
856 template <class Key, class T>
find(const Key & akey)857 Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &akey) const
858 {
859 return constFind(akey);
860 }
861
862 template <class Key, class T>
find(const Key & akey)863 Q_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
870 template <class Key, class T>
equal_range(const Key & akey)871 QPair<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
879 template <class Key, class T>
880 QPair<typename QMap<Key, T>::const_iterator, typename QMap<Key, T>::const_iterator>
equal_range(const Key & akey)881 QMap<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
889 template <class Key, class T>
dump()890 void 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
910 template <class Key, class T>
remove(const Key & akey)911 Q_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
922 template <class Key, class T>
take(const Key & akey)923 Q_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
936 template <class Key, class T>
erase(iterator it)937 Q_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
971 template <class Key, class T>
detach_helper()972 Q_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
985 template <class Key, class T>
keys()986 Q_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
998 template <class Key, class T>
keys(const T & avalue)999 Q_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
1011 template <class Key, class T>
key(const T & avalue,const Key & defaultKey)1012 Q_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
1024 template <class Key, class T>
values()1025 Q_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
1037 template <class Key, class T>
lowerBound(const Key & akey)1038 Q_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
1046 template <class Key, class T>
lowerBound(const Key & akey)1047 Q_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
1056 template <class Key, class T>
1057 Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator
upperBound(const Key & akey)1058 QMap<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
1066 template <class Key, class T>
upperBound(const Key & akey)1067 Q_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
1076 template <class Key, class T>
1077 Q_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
1096 template <class Key, class T>
QMap(const std::map<Key,T> & other)1097 Q_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
1107 template <class Key, class T>
toStdMap()1108 Q_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
1119 template <class Key, class T>
1120 class QMultiMap : public QMap<Key, T>
1121 {
1122 public:
QMultiMap()1123 QMultiMap() noexcept {}
QMultiMap(std::initializer_list<std::pair<Key,T>> list)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 }
QMultiMap(const QMap<Key,T> & other)1129 QMultiMap(const QMap<Key, T> &other) : QMap<Key, T>(other) {}
QMultiMap(QMap<Key,T> && other)1130 QMultiMap(QMap<Key, T> &&other) noexcept : QMap<Key, T>(std::move(other)) {}
swap(QMultiMap<Key,T> & 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
replace(const Key & key,const T & value)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
find(const Key & key,const T & value)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 }
find(const Key & key,const T & value)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 }
constFind(const Key & key,const T & value)1188 typename QMap<Key, T>::const_iterator constFind(const Key &key, const T &value) const
1189 { return find(key, value); }
1190 private:
1191 T &operator[](const Key &key);
1192 const T operator[](const Key &key) const;
1193 };
1194
1195 template <class Key, class T>
uniqueKeys()1196 Q_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 }
1211 break_out_of_outer_loop:
1212 return res;
1213 }
1214
1215 template <class Key, class T>
values(const Key & akey)1216 Q_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
1230 template <class Key, class T>
insert(const Key & akey,const T & avalue)1231 Q_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
1248 template <class Key, class T>
insert(typename QMap<Key,T>::const_iterator pos,const Key & akey,const T & avalue)1249 typename 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
1301 template <class Key, class T>
unite(const QMultiMap<Key,T> & other)1302 Q_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
1315 template <class Key, class T>
contains(const Key & key,const T & value)1316 Q_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
1321 template <class Key, class T>
remove(const Key & key,const T & value)1322 Q_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
1338 template <class Key, class T>
count(const Key & key,const T & value)1339 Q_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)
1353 template<class Key, class T>
uniqueKeys()1354 QList<Key> QMap<Key, T>::uniqueKeys() const
1355 {
1356 return static_cast<const QMultiMap<Key, T> *>(this)->uniqueKeys();
1357 }
1358
1359 template<class Key, class T>
values(const Key & key)1360 QList<T> QMap<Key, T>::values(const Key &key) const
1361 {
1362 return static_cast<const QMultiMap<Key, T> *>(this)->values(key);
1363 }
1364
1365 template<class Key, class T>
insertMulti(const Key & key,const T & value)1366 typename 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
1371 template<class Key, class T>
insertMulti(const_iterator pos,const Key & akey,const T & avalue)1372 typename 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
1377 template<class Key, class T>
unite(const QMap<Key,T> & other)1378 QMap<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
1384 Q_DECLARE_ASSOCIATIVE_ITERATOR(Map)
1385 Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map)
1386
1387 QT_END_NAMESPACE
1388
1389 #endif // QMAP_H
1390