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