1// Copyright (C) 2020 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
2// Copyright (C) 2021 The Qt Company Ltd.
3// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
4
5#ifndef QMAP_H
6#define QMAP_H
7
8#include <QtCore/qiterator.h>
9#include <QtCore/qlist.h>
10#include <QtCore/qrefcount.h>
11#include <QtCore/qpair.h>
12#include <QtCore/qshareddata.h>
13#include <QtCore/qshareddata_impl.h>
14
15#include <functional>
16#include <initializer_list>
17#include <map>
18#include <algorithm>
19
20QT_BEGIN_NAMESPACE
21
22// common code shared between QMap and QMultimap
23template <typename AMap>
24class QMapData : public QSharedData
25{
26public:
27 using Map = AMap;
28 using Key = typename Map::key_type;
29 using T = typename Map::mapped_type;
30 using value_type = typename Map::value_type;
31 using size_type = typename Map::size_type;
32 using iterator = typename Map::iterator;
33 using const_iterator = typename Map::const_iterator;
34
35 static_assert(std::is_nothrow_destructible_v<Key>, "Types with throwing destructors are not supported in Qt containers.");
36 static_assert(std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers.");
37
38 Map m;
39
40 QMapData() = default;
41 explicit QMapData(const Map &other)
42 : m(other)
43 {}
44
45 explicit QMapData(Map &&other)
46 : m(std::move(other))
47 {}
48
49 // used in remove(); copies from source all the values not matching key.
50 // returns how many were NOT copied (removed).
51 size_type copyIfNotEquivalentTo(const Map &source, const Key &key)
52 {
53 Q_ASSERT(m.empty());
54
55 size_type result = 0;
56 const auto &keyCompare = source.key_comp();
57 const auto filter = [&result, &key, &keyCompare](const auto &v)
58 {
59 if (!keyCompare(key, v.first) && !keyCompare(v.first, key)) {
60 // keys are equivalent (neither a<b nor b<a) => found it
61 ++result;
62 return true;
63 }
64 return false;
65 };
66
67 std::remove_copy_if(source.cbegin(), source.cend(),
68 std::inserter(m, m.end()),
69 filter);
70 return result;
71 }
72
73 // used in key(T), count(Key, T), find(key, T), etc; returns a
74 // comparator object suitable for algorithms with std::(multi)map
75 // iterators.
76 static auto valueIsEqualTo(const T &value)
77 {
78 return [&value](const auto &v) { return v.second == value; };
79 }
80
81 Key key(const T &value, const Key &defaultKey) const
82 {
83 auto i = std::find_if(m.cbegin(),
84 m.cend(),
85 valueIsEqualTo(value));
86 if (i != m.cend())
87 return i->first;
88
89 return defaultKey;
90 }
91
92 QList<Key> keys() const
93 {
94 QList<Key> result;
95 result.reserve(m.size());
96
97 const auto extractKey = [](const auto &v) { return v.first; };
98
99 std::transform(m.cbegin(),
100 m.cend(),
101 std::back_inserter(result),
102 extractKey);
103 return result;
104 }
105
106 QList<Key> keys(const T &value) const
107 {
108 QList<Key> result;
109 result.reserve(m.size());
110 // no std::transform_if...
111 for (const auto &v : m) {
112 if (v.second == value)
113 result.append(v.first);
114 }
115 result.shrink_to_fit();
116 return result;
117 }
118
119 QList<T> values() const
120 {
121 QList<T> result;
122 result.reserve(m.size());
123
124 const auto extractValue = [](const auto &v) { return v.second; };
125
126 std::transform(m.cbegin(),
127 m.cend(),
128 std::back_inserter(result),
129 extractValue);
130 return result;
131 }
132
133 size_type count(const Key &key) const
134 {
135 return m.count(key);
136 }
137
138 // Used in erase. Allocates a new QMapData and copies, from this->m,
139 // the elements not in the [first, last) range. The return contains
140 // the new QMapData and an iterator in its map pointing at the first
141 // element after the erase.
142 struct EraseResult {
143 QMapData *data;
144 iterator it;
145 };
146
147 EraseResult erase(const_iterator first, const_iterator last) const
148 {
149 EraseResult result;
150 result.data = new QMapData;
151 result.it = result.data->m.end();
152 const auto newDataEnd = result.it;
153
154 auto i = m.begin();
155 const auto e = m.end();
156
157 // copy over all the elements before first
158 while (i != first) {
159 result.it = result.data->m.insert(newDataEnd, *i);
160 ++i;
161 }
162
163 // skip until last
164 while (i != last)
165 ++i;
166
167 // copy from last to the end
168 while (i != e) {
169 result.data->m.insert(newDataEnd, *i);
170 ++i;
171 }
172
173 if (result.it != newDataEnd)
174 ++result.it;
175
176 return result;
177 }
178};
179
180//
181// QMap
182//
183
184template <class Key, class T>
185class QMap
186{
187 using Map = std::map<Key, T>;
188 using MapData = QMapData<Map>;
189 QtPrivate::QExplicitlySharedDataPointerV2<MapData> d;
190
191 friend class QMultiMap<Key, T>;
192
193public:
194 using key_type = Key;
195 using mapped_type = T;
196 using difference_type = qptrdiff;
197 using size_type = qsizetype;
198
199 QMap() = default;
200
201 // implicitly generated special member functions are OK!
202
203 void swap(QMap<Key, T> &other) noexcept
204 {
205 d.swap(other.d);
206 }
207
208 QMap(std::initializer_list<std::pair<Key, T>> list)
209 {
210 for (auto &p : list)
211 insert(p.first, p.second);
212 }
213
214 explicit QMap(const std::map<Key, T> &other)
215 : d(other.empty() ? nullptr : new MapData(other))
216 {
217 }
218
219 explicit QMap(std::map<Key, T> &&other)
220 : d(other.empty() ? nullptr : new MapData(std::move(other)))
221 {
222 }
223
224 std::map<Key, T> toStdMap() const &
225 {
226 if (d)
227 return d->m;
228 return {};
229 }
230
231 std::map<Key, T> toStdMap() &&
232 {
233 if (d) {
234 if (d.isShared())
235 return d->m;
236 else
237 return std::move(d->m);
238 }
239
240 return {};
241 }
242
243#ifndef Q_QDOC
244 template <typename AKey = Key, typename AT = T> friend
245 QTypeTraits::compare_eq_result_container<QMap, AKey, AT> operator==(const QMap &lhs, const QMap &rhs)
246 {
247 if (lhs.d == rhs.d)
248 return true;
249 if (!lhs.d)
250 return rhs == lhs;
251 Q_ASSERT(lhs.d);
252 return rhs.d ? (lhs.d->m == rhs.d->m) : lhs.d->m.empty();
253 }
254
255 template <typename AKey = Key, typename AT = T> friend
256 QTypeTraits::compare_eq_result_container<QMap, AKey, AT> operator!=(const QMap &lhs, const QMap &rhs)
257 {
258 return !(lhs == rhs);
259 }
260 // TODO: add the other comparison operators; std::map has them.
261#else
262 friend bool operator==(const QMap &lhs, const QMap &rhs);
263 friend bool operator!=(const QMap &lhs, const QMap &rhs);
264#endif // Q_QDOC
265
266 size_type size() const { return d ? size_type(d->m.size()) : size_type(0); }
267
268 bool isEmpty() const { return d ? d->m.empty() : true; }
269
270 void detach()
271 {
272 if (d)
273 d.detach();
274 else
275 d.reset(new MapData);
276 }
277
278 bool isDetached() const noexcept
279 {
280 return d ? !d.isShared() : false; // false makes little sense, but that's shared_null's behavior...
281 }
282
283 bool isSharedWith(const QMap<Key, T> &other) const noexcept
284 {
285 return d == other.d; // also this makes little sense?
286 }
287
288 void clear()
289 {
290 if (!d)
291 return;
292
293 if (!d.isShared())
294 d->m.clear();
295 else
296 d.reset();
297 }
298
299 size_type remove(const Key &key)
300 {
301 if (!d)
302 return 0;
303
304 if (!d.isShared())
305 return size_type(d->m.erase(key));
306
307 MapData *newData = new MapData;
308 size_type result = newData->copyIfNotEquivalentTo(d->m, key);
309
310 d.reset(newData);
311
312 return result;
313 }
314
315 template <typename Predicate>
316 size_type removeIf(Predicate pred)
317 {
318 return QtPrivate::associative_erase_if(*this, pred);
319 }
320
321 T take(const Key &key)
322 {
323 if (!d)
324 return T();
325
326 const auto copy = d.isShared() ? *this : QMap(); // keep `key` alive across the detach
327 // TODO: improve. There is no need of copying all the
328 // elements (the one to be removed can be skipped).
329 detach();
330
331 auto i = d->m.find(key);
332 if (i != d->m.end()) {
333 T result(std::move(i->second));
334 d->m.erase(i);
335 return result;
336 }
337 return T();
338 }
339
340 bool contains(const Key &key) const
341 {
342 if (!d)
343 return false;
344 auto i = d->m.find(key);
345 return i != d->m.end();
346 }
347
348 Key key(const T &value, const Key &defaultKey = Key()) const
349 {
350 if (!d)
351 return defaultKey;
352
353 return d->key(value, defaultKey);
354 }
355
356 T value(const Key &key, const T &defaultValue = T()) const
357 {
358 if (!d)
359 return defaultValue;
360 const auto i = d->m.find(key);
361 if (i != d->m.cend())
362 return i->second;
363 return defaultValue;
364 }
365
366 T &operator[](const Key &key)
367 {
368 const auto copy = d.isShared() ? *this : QMap(); // keep `key` alive across the detach
369 detach();
370 auto i = d->m.find(key);
371 if (i == d->m.end())
372 i = d->m.insert({key, T()}).first;
373 return i->second;
374 }
375
376 // CHANGE: return T, not const T!
377 T operator[](const Key &key) const
378 {
379 return value(key);
380 }
381
382 QList<Key> keys() const
383 {
384 if (!d)
385 return {};
386 return d->keys();
387 }
388
389 QList<Key> keys(const T &value) const
390 {
391 if (!d)
392 return {};
393 return d->keys(value);
394 }
395
396 QList<T> values() const
397 {
398 if (!d)
399 return {};
400 return d->values();
401 }
402
403 size_type count(const Key &key) const
404 {
405 if (!d)
406 return 0;
407 return d->count(key);
408 }
409
410 size_type count() const
411 {
412 return size();
413 }
414
415 inline const Key &firstKey() const { Q_ASSERT(!isEmpty()); return constBegin().key(); }
416 inline const Key &lastKey() const { Q_ASSERT(!isEmpty()); return (--constEnd()).key(); }
417
418 inline T &first() { Q_ASSERT(!isEmpty()); return *begin(); }
419 inline const T &first() const { Q_ASSERT(!isEmpty()); return *constBegin(); }
420 inline T &last() { Q_ASSERT(!isEmpty()); return *(--end()); }
421 inline const T &last() const { Q_ASSERT(!isEmpty()); return *(--constEnd()); }
422
423 class const_iterator;
424
425 class iterator
426 {
427 friend class QMap<Key, T>;
428 friend class const_iterator;
429
430 typename Map::iterator i;
431 explicit iterator(typename Map::iterator it) : i(it) {}
432 public:
433 using iterator_category = std::bidirectional_iterator_tag;
434 using difference_type = qptrdiff;
435 using value_type = T;
436 using pointer = T *;
437 using reference = T &;
438
439 iterator() = default;
440
441 const Key &key() const { return i->first; }
442 T &value() const { return i->second; }
443 T &operator*() const { return i->second; }
444 T *operator->() const { return &i->second; }
445 friend bool operator==(const iterator &lhs, const iterator &rhs) { return lhs.i == rhs.i; }
446 friend bool operator!=(const iterator &lhs, const iterator &rhs) { return lhs.i != rhs.i; }
447
448 iterator &operator++()
449 {
450 ++i;
451 return *this;
452 }
453 iterator operator++(int)
454 {
455 iterator r = *this;
456 ++i;
457 return r;
458 }
459 iterator &operator--()
460 {
461 --i;
462 return *this;
463 }
464 iterator operator--(int)
465 {
466 iterator r = *this;
467 --i;
468 return r;
469 }
470
471#if QT_DEPRECATED_SINCE(6, 0)
472 QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMap iterators are not random access")
473 //! [qmap-op-it-plus-step]
474 friend iterator operator+(iterator it, difference_type j) { return std::next(it, j); }
475
476 QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMap iterators are not random access")
477 //! [qmap-op-it-minus-step]
478 friend iterator operator-(iterator it, difference_type j) { return std::prev(it, j); }
479
480 QT_DEPRECATED_VERSION_X_6_0("Use std::next or std::advance; QMap iterators are not random access")
481 iterator &operator+=(difference_type j) { std::advance(*this, j); return *this; }
482
483 QT_DEPRECATED_VERSION_X_6_0("Use std::prev or std::advance; QMap iterators are not random access")
484 iterator &operator-=(difference_type j) { std::advance(*this, -j); return *this; }
485
486 QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMap iterators are not random access")
487 //! [qmap-op-step-plus-it]
488 friend iterator operator+(difference_type j, iterator it) { return std::next(it, j); }
489
490 QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMap iterators are not random access")
491 //! [qmap-op-step-minus-it]
492 friend iterator operator-(difference_type j, iterator it) { return std::prev(it, j); }
493#endif
494 };
495
496 class const_iterator
497 {
498 friend class QMap<Key, T>;
499 typename Map::const_iterator i;
500 explicit const_iterator(typename Map::const_iterator it) : i(it) {}
501
502 public:
503 using iterator_category = std::bidirectional_iterator_tag;
504 using difference_type = qptrdiff;
505 using value_type = T;
506 using pointer = const T *;
507 using reference = const T &;
508
509 const_iterator() = default;
510 Q_IMPLICIT const_iterator(const iterator &o) : i(o.i) {}
511
512 const Key &key() const { return i->first; }
513 const T &value() const { return i->second; }
514 const T &operator*() const { return i->second; }
515 const T *operator->() const { return &i->second; }
516 friend bool operator==(const const_iterator &lhs, const const_iterator &rhs) { return lhs.i == rhs.i; }
517 friend bool operator!=(const const_iterator &lhs, const const_iterator &rhs) { return lhs.i != rhs.i; }
518
519 const_iterator &operator++()
520 {
521 ++i;
522 return *this;
523 }
524 const_iterator operator++(int)
525 {
526 const_iterator r = *this;
527 ++i;
528 return r;
529 }
530 const_iterator &operator--()
531 {
532 --i;
533 return *this;
534 }
535 const_iterator operator--(int)
536 {
537 const_iterator r = *this;
538 --i;
539 return r;
540 }
541
542#if QT_DEPRECATED_SINCE(6, 0)
543 QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMap iterators are not random access")
544 //! [qmap-op-it-plus-step-const]
545 friend const_iterator operator+(const_iterator it, difference_type j) { return std::next(it, j); }
546
547 QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMap iterators are not random access")
548 //! [qmap-op-it-minus-step-const]
549 friend const_iterator operator-(const_iterator it, difference_type j) { return std::prev(it, j); }
550
551 QT_DEPRECATED_VERSION_X_6_0("Use std::next or std::advance; QMap iterators are not random access")
552 const_iterator &operator+=(difference_type j) { std::advance(*this, j); return *this; }
553
554 QT_DEPRECATED_VERSION_X_6_0("Use std::prev or std::advance; QMap iterators are not random access")
555 const_iterator &operator-=(difference_type j) { std::advance(*this, -j); return *this; }
556
557 QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMap iterators are not random access")
558 //! [qmap-op-step-plus-it-const]
559 friend const_iterator operator+(difference_type j, const_iterator it) { return std::next(it, j); }
560
561 QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMap iterators are not random access")
562 //! [qmap-op-step-minus-it-const]
563 friend const_iterator operator-(difference_type j, const_iterator it) { return std::prev(it, j); }
564#endif
565 };
566
567 class key_iterator
568 {
569 const_iterator i;
570
571 public:
572 typedef typename const_iterator::iterator_category iterator_category;
573 typedef typename const_iterator::difference_type difference_type;
574 typedef Key value_type;
575 typedef const Key *pointer;
576 typedef const Key &reference;
577
578 key_iterator() = default;
579 explicit key_iterator(const_iterator o) : i(o) { }
580
581 const Key &operator*() const { return i.key(); }
582 const Key *operator->() const { return &i.key(); }
583 bool operator==(key_iterator o) const { return i == o.i; }
584 bool operator!=(key_iterator o) const { return i != o.i; }
585
586 inline key_iterator &operator++() { ++i; return *this; }
587 inline key_iterator operator++(int) { return key_iterator(i++);}
588 inline key_iterator &operator--() { --i; return *this; }
589 inline key_iterator operator--(int) { return key_iterator(i--); }
590 const_iterator base() const { return i; }
591 };
592
593 typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator;
594 typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator;
595
596 // STL style
597 iterator begin() { detach(); return iterator(d->m.begin()); }
598 const_iterator begin() const { if (!d) return const_iterator(); return const_iterator(d->m.cbegin()); }
599 const_iterator constBegin() const { return begin(); }
600 const_iterator cbegin() const { return begin(); }
601 iterator end() { detach(); return iterator(d->m.end()); }
602 const_iterator end() const { if (!d) return const_iterator(); return const_iterator(d->m.end()); }
603 const_iterator constEnd() const { return end(); }
604 const_iterator cend() const { return end(); }
605 key_iterator keyBegin() const { return key_iterator(begin()); }
606 key_iterator keyEnd() const { return key_iterator(end()); }
607 key_value_iterator keyValueBegin() { return key_value_iterator(begin()); }
608 key_value_iterator keyValueEnd() { return key_value_iterator(end()); }
609 const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); }
610 const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); }
611 const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); }
612 const_key_value_iterator constKeyValueEnd() const { return const_key_value_iterator(end()); }
613 auto asKeyValueRange() & { return QtPrivate::QKeyValueRange(*this); }
614 auto asKeyValueRange() const & { return QtPrivate::QKeyValueRange(*this); }
615 auto asKeyValueRange() && { return QtPrivate::QKeyValueRange(std::move(*this)); }
616 auto asKeyValueRange() const && { return QtPrivate::QKeyValueRange(std::move(*this)); }
617
618 iterator erase(const_iterator it)
619 {
620 return erase(it, std::next(it));
621 }
622
623 iterator erase(const_iterator afirst, const_iterator alast)
624 {
625 if (!d)
626 return iterator();
627
628 if (!d.isShared())
629 return iterator(d->m.erase(afirst.i, alast.i));
630
631 auto result = d->erase(afirst.i, alast.i);
632 d.reset(result.data);
633 return iterator(result.it);
634 }
635
636 // more Qt
637 typedef iterator Iterator;
638 typedef const_iterator ConstIterator;
639
640 iterator find(const Key &key)
641 {
642 const auto copy = d.isShared() ? *this : QMap(); // keep `key` alive across the detach
643 detach();
644 return iterator(d->m.find(key));
645 }
646
647 const_iterator find(const Key &key) const
648 {
649 if (!d)
650 return const_iterator();
651 return const_iterator(d->m.find(key));
652 }
653
654 const_iterator constFind(const Key &key) const
655 {
656 return find(key);
657 }
658
659 iterator lowerBound(const Key &key)
660 {
661 const auto copy = d.isShared() ? *this : QMap(); // keep `key` alive across the detach
662 detach();
663 return iterator(d->m.lower_bound(key));
664 }
665
666 const_iterator lowerBound(const Key &key) const
667 {
668 if (!d)
669 return const_iterator();
670 return const_iterator(d->m.lower_bound(key));
671 }
672
673 iterator upperBound(const Key &key)
674 {
675 const auto copy = d.isShared() ? *this : QMap(); // keep `key` alive across the detach
676 detach();
677 return iterator(d->m.upper_bound(key));
678 }
679
680 const_iterator upperBound(const Key &key) const
681 {
682 if (!d)
683 return const_iterator();
684 return const_iterator(d->m.upper_bound(key));
685 }
686
687 iterator insert(const Key &key, const T &value)
688 {
689 const auto copy = d.isShared() ? *this : QMap(); // keep `key` alive across the detach
690 // TODO: improve. In case of assignment, why copying first?
691 detach();
692 return iterator(d->m.insert_or_assign(key, value).first);
693 }
694
695 iterator insert(const_iterator pos, const Key &key, const T &value)
696 {
697 // TODO: improve. In case of assignment, why copying first?
698 typename Map::const_iterator dpos;
699 const auto copy = d.isShared() ? *this : QMap(); // keep `key`/`value` alive across the detach
700 if (!d || d.isShared()) {
701 auto posDistance = d ? std::distance(d->m.cbegin(), pos.i) : 0;
702 detach();
703 dpos = std::next(d->m.cbegin(), posDistance);
704 } else {
705 dpos = pos.i;
706 }
707 return iterator(d->m.insert_or_assign(dpos, key, value));
708 }
709
710 void insert(const QMap<Key, T> &map)
711 {
712 // TODO: improve. In case of assignment, why copying first?
713 if (map.isEmpty())
714 return;
715
716 detach();
717
718#ifdef __cpp_lib_node_extract
719 auto copy = map.d->m;
720 copy.merge(std::move(d->m));
721 d->m = std::move(copy);
722#else
723 // this is a std::copy, but we can't use std::inserter (need insert_or_assign...).
724 // copy in reverse order, trying to make effective use of insertionHint.
725 auto insertionHint = d->m.end();
726 auto mapIt = map.d->m.crbegin();
727 auto end = map.d->m.crend();
728 for (; mapIt != end; ++mapIt)
729 insertionHint = d->m.insert_or_assign(insertionHint, mapIt->first, mapIt->second);
730#endif
731 }
732
733 void insert(QMap<Key, T> &&map)
734 {
735 if (!map.d || map.d->m.empty())
736 return;
737
738 if (map.d.isShared()) {
739 // fall back to a regular copy
740 insert(map);
741 return;
742 }
743
744 detach();
745
746#ifdef __cpp_lib_node_extract
747 map.d->m.merge(std::move(d->m));
748 *this = std::move(map);
749#else
750 // same as above
751 auto insertionHint = d->m.end();
752 auto mapIt = map.d->m.crbegin();
753 auto end = map.d->m.crend();
754 for (; mapIt != end; ++mapIt)
755 insertionHint = d->m.insert_or_assign(insertionHint, std::move(mapIt->first), std::move(mapIt->second));
756#endif
757 }
758
759 // STL compatibility
760 inline bool empty() const
761 {
762 return isEmpty();
763 }
764
765 QPair<iterator, iterator> equal_range(const Key &akey)
766 {
767 const auto copy = d.isShared() ? *this : QMap(); // keep `key` alive across the detach
768 detach();
769 auto result = d->m.equal_range(akey);
770 return {iterator(result.first), iterator(result.second)};
771 }
772
773 QPair<const_iterator, const_iterator> equal_range(const Key &akey) const
774 {
775 if (!d)
776 return {};
777 auto result = d->m.equal_range(akey);
778 return {const_iterator(result.first), const_iterator(result.second)};
779 }
780};
781
782Q_DECLARE_ASSOCIATIVE_ITERATOR(Map)
783Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map)
784
785template <typename Key, typename T, typename Predicate>
786qsizetype erase_if(QMap<Key, T> &map, Predicate pred)
787{
788 return QtPrivate::associative_erase_if(map, pred);
789}
790
791//
792// QMultiMap
793//
794
795template <class Key, class T>
796class QMultiMap
797{
798 using Map = std::multimap<Key, T>;
799 using MapData = QMapData<Map>;
800 QtPrivate::QExplicitlySharedDataPointerV2<MapData> d;
801
802public:
803 using key_type = Key;
804 using mapped_type = T;
805 using difference_type = qptrdiff;
806 using size_type = qsizetype;
807
808 QMultiMap() = default;
809
810 // implicitly generated special member functions are OK!
811
812 QMultiMap(std::initializer_list<std::pair<Key,T>> list)
813 {
814 for (auto &p : list)
815 insert(p.first, p.second);
816 }
817
818 void swap(QMultiMap<Key, T> &other) noexcept
819 {
820 d.swap(other.d);
821 }
822
823 explicit QMultiMap(const QMap<Key, T> &other)
824 : d(other.isEmpty() ? nullptr : new MapData)
825 {
826 if (d) {
827 Q_ASSERT(other.d);
828 d->m.insert(other.d->m.begin(),
829 other.d->m.end());
830 }
831 }
832
833 explicit QMultiMap(QMap<Key, T> &&other)
834 : d(other.isEmpty() ? nullptr : new MapData)
835 {
836 if (d) {
837 Q_ASSERT(other.d);
838 if (other.d.isShared()) {
839 d->m.insert(other.d->m.begin(),
840 other.d->m.end());
841 } else {
842#ifdef __cpp_lib_node_extract
843 d->m.merge(std::move(other.d->m));
844#else
845 d->m.insert(std::make_move_iterator(other.d->m.begin()),
846 std::make_move_iterator(other.d->m.end()));
847#endif
848 }
849 }
850 }
851
852 explicit QMultiMap(const std::multimap<Key, T> &other)
853 : d(other.empty() ? nullptr : new MapData(other))
854 {
855 }
856
857 explicit QMultiMap(std::multimap<Key, T> &&other)
858 : d(other.empty() ? nullptr : new MapData(std::move(other)))
859 {
860 }
861
862 // CHANGE: return type
863 Q_DECL_DEPRECATED_X("Use toStdMultiMap instead")
864 std::multimap<Key, T> toStdMap() const
865 {
866 return toStdMultiMap();
867 }
868
869 std::multimap<Key, T> toStdMultiMap() const &
870 {
871 if (d)
872 return d->m;
873 return {};
874 }
875
876 std::multimap<Key, T> toStdMultiMap() &&
877 {
878 if (d) {
879 if (d.isShared())
880 return d->m;
881 else
882 return std::move(d->m);
883 }
884
885 return {};
886 }
887
888#ifndef Q_QDOC
889 template <typename AKey = Key, typename AT = T> friend
890 QTypeTraits::compare_eq_result_container<QMultiMap, AKey, AT> operator==(const QMultiMap &lhs, const QMultiMap &rhs)
891 {
892 if (lhs.d == rhs.d)
893 return true;
894 if (!lhs.d)
895 return rhs == lhs;
896 Q_ASSERT(lhs.d);
897 return rhs.d ? (lhs.d->m == rhs.d->m) : lhs.d->m.empty();
898 }
899
900 template <typename AKey = Key, typename AT = T> friend
901 QTypeTraits::compare_eq_result_container<QMultiMap, AKey, AT> operator!=(const QMultiMap &lhs, const QMultiMap &rhs)
902 {
903 return !(lhs == rhs);
904 }
905 // TODO: add the other comparison operators; std::multimap has them.
906#else
907 friend bool operator==(const QMultiMap &lhs, const QMultiMap &rhs);
908 friend bool operator!=(const QMultiMap &lhs, const QMultiMap &rhs);
909#endif // Q_QDOC
910
911 size_type size() const { return d ? size_type(d->m.size()) : size_type(0); }
912
913 bool isEmpty() const { return d ? d->m.empty() : true; }
914
915 void detach()
916 {
917 if (d)
918 d.detach();
919 else
920 d.reset(new MapData);
921 }
922
923 bool isDetached() const noexcept
924 {
925 return d ? !d.isShared() : false; // false makes little sense, but that's shared_null's behavior...
926 }
927
928 bool isSharedWith(const QMultiMap<Key, T> &other) const noexcept
929 {
930 return d == other.d; // also this makes little sense?
931 }
932
933 void clear()
934 {
935 if (!d)
936 return;
937
938 if (!d.isShared())
939 d->m.clear();
940 else
941 d.reset();
942 }
943
944 size_type remove(const Key &key)
945 {
946 if (!d)
947 return 0;
948
949 if (!d.isShared())
950 return size_type(d->m.erase(key));
951
952 MapData *newData = new MapData;
953 size_type result = newData->copyIfNotEquivalentTo(d->m, key);
954
955 d.reset(newData);
956
957 return result;
958 }
959
960 size_type remove(const Key &key, const T &value)
961 {
962 if (!d)
963 return 0;
964
965 // key and value may belong to this map. As such, we need to copy
966 // them to ensure they stay valid throughout the iteration below
967 // (which may destroy them)
968 const Key keyCopy = key;
969 const T valueCopy = value;
970
971 // TODO: improve. Copy over only the elements not to be removed.
972 detach();
973
974 size_type result = 0;
975 const auto &keyCompare = d->m.key_comp();
976
977 auto i = d->m.find(keyCopy);
978 const auto e = d->m.end();
979
980 while (i != e && !keyCompare(keyCopy, i->first)) {
981 if (i->second == valueCopy) {
982 i = d->m.erase(i);
983 ++result;
984 } else {
985 ++i;
986 }
987 }
988
989 return result;
990 }
991
992 template <typename Predicate>
993 size_type removeIf(Predicate pred)
994 {
995 return QtPrivate::associative_erase_if(*this, pred);
996 }
997
998 T take(const Key &key)
999 {
1000 if (!d)
1001 return T();
1002
1003 const auto copy = d.isShared() ? *this : QMultiMap(); // keep `key` alive across the detach
1004
1005 // TODO: improve. There is no need of copying all the
1006 // elements (the one to be removed can be skipped).
1007 detach();
1008
1009 auto i = d->m.find(key);
1010 if (i != d->m.end()) {
1011 T result(std::move(i->second));
1012 d->m.erase(i);
1013 return result;
1014 }
1015 return T();
1016 }
1017
1018 bool contains(const Key &key) const
1019 {
1020 if (!d)
1021 return false;
1022 auto i = d->m.find(key);
1023 return i != d->m.end();
1024 }
1025
1026 bool contains(const Key &key, const T &value) const
1027 {
1028 return find(key, value) != end();
1029 }
1030
1031 Key key(const T &value, const Key &defaultKey = Key()) const
1032 {
1033 if (!d)
1034 return defaultKey;
1035
1036 return d->key(value, defaultKey);
1037 }
1038
1039 T value(const Key &key, const T &defaultValue = T()) const
1040 {
1041 if (!d)
1042 return defaultValue;
1043 const auto i = d->m.find(key);
1044 if (i != d->m.cend())
1045 return i->second;
1046 return defaultValue;
1047 }
1048
1049 QList<Key> keys() const
1050 {
1051 if (!d)
1052 return {};
1053 return d->keys();
1054 }
1055
1056 QList<Key> keys(const T &value) const
1057 {
1058 if (!d)
1059 return {};
1060 return d->keys(value);
1061 }
1062
1063 QList<Key> uniqueKeys() const
1064 {
1065 QList<Key> result;
1066 if (!d)
1067 return result;
1068
1069 result.reserve(size());
1070
1071 std::unique_copy(keyBegin(), keyEnd(),
1072 std::back_inserter(result));
1073
1074 result.shrink_to_fit();
1075 return result;
1076 }
1077
1078 QList<T> values() const
1079 {
1080 if (!d)
1081 return {};
1082 return d->values();
1083 }
1084
1085 QList<T> values(const Key &key) const
1086 {
1087 QList<T> result;
1088 const auto range = equal_range(key);
1089 result.reserve(std::distance(range.first, range.second));
1090 std::copy(range.first, range.second, std::back_inserter(result));
1091 return result;
1092 }
1093
1094 size_type count(const Key &key) const
1095 {
1096 if (!d)
1097 return 0;
1098 return d->count(key);
1099 }
1100
1101 size_type count(const Key &key, const T &value) const
1102 {
1103 if (!d)
1104 return 0;
1105
1106 // TODO: improve; no need of scanning the equal_range twice.
1107 auto range = d->m.equal_range(key);
1108
1109 return size_type(std::count_if(range.first,
1110 range.second,
1111 MapData::valueIsEqualTo(value)));
1112 }
1113
1114 inline const Key &firstKey() const { Q_ASSERT(!isEmpty()); return constBegin().key(); }
1115 inline const Key &lastKey() const { Q_ASSERT(!isEmpty()); return std::next(constEnd(), -1).key(); }
1116
1117 inline T &first() { Q_ASSERT(!isEmpty()); return *begin(); }
1118 inline const T &first() const { Q_ASSERT(!isEmpty()); return *constBegin(); }
1119 inline T &last() { Q_ASSERT(!isEmpty()); return *std::next(end(), -1); }
1120 inline const T &last() const { Q_ASSERT(!isEmpty()); return *std::next(constEnd(), -1); }
1121
1122 class const_iterator;
1123
1124 class iterator
1125 {
1126 friend class QMultiMap<Key, T>;
1127 friend class const_iterator;
1128
1129 typename Map::iterator i;
1130 explicit iterator(typename Map::iterator it) : i(it) {}
1131 public:
1132 using iterator_category = std::bidirectional_iterator_tag;
1133 using difference_type = qptrdiff;
1134 using value_type = T;
1135 using pointer = T *;
1136 using reference = T &;
1137
1138 iterator() = default;
1139
1140 const Key &key() const { return i->first; }
1141 T &value() const { return i->second; }
1142 T &operator*() const { return i->second; }
1143 T *operator->() const { return &i->second; }
1144 friend bool operator==(const iterator &lhs, const iterator &rhs) { return lhs.i == rhs.i; }
1145 friend bool operator!=(const iterator &lhs, const iterator &rhs) { return lhs.i != rhs.i; }
1146
1147 iterator &operator++()
1148 {
1149 ++i;
1150 return *this;
1151 }
1152 iterator operator++(int)
1153 {
1154 iterator r = *this;
1155 ++i;
1156 return r;
1157 }
1158 iterator &operator--()
1159 {
1160 --i;
1161 return *this;
1162 }
1163 iterator operator--(int)
1164 {
1165 iterator r = *this;
1166 --i;
1167 return r;
1168 }
1169
1170#if QT_DEPRECATED_SINCE(6, 0)
1171 QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMultiMap iterators are not random access")
1172 //! [qmultimap-op-it-plus-step]
1173 friend iterator operator+(iterator it, difference_type j) { return std::next(it, j); }
1174
1175 QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMultiMap iterators are not random access")
1176 //! [qmultimap-op-it-minus-step]
1177 friend iterator operator-(iterator it, difference_type j) { return std::prev(it, j); }
1178
1179 QT_DEPRECATED_VERSION_X_6_0("Use std::next or std::advance; QMultiMap iterators are not random access")
1180 iterator &operator+=(difference_type j) { std::advance(*this, j); return *this; }
1181
1182 QT_DEPRECATED_VERSION_X_6_0("Use std::prev or std::advance; QMultiMap iterators are not random access")
1183 iterator &operator-=(difference_type j) { std::advance(*this, -j); return *this; }
1184
1185 QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMultiMap iterators are not random access")
1186 //! [qmultimap-op-step-plus-it]
1187 friend iterator operator+(difference_type j, iterator it) { return std::next(it, j); }
1188
1189 QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMultiMap iterators are not random access")
1190 //! [qmultimap-op-step-minus-it]
1191 friend iterator operator-(difference_type j, iterator it) { return std::prev(it, j); }
1192#endif
1193 };
1194
1195 class const_iterator
1196 {
1197 friend class QMultiMap<Key, T>;
1198 typename Map::const_iterator i;
1199 explicit const_iterator(typename Map::const_iterator it) : i(it) {}
1200
1201 public:
1202 using iterator_category = std::bidirectional_iterator_tag;
1203 using difference_type = qptrdiff;
1204 using value_type = T;
1205 using pointer = const T *;
1206 using reference = const T &;
1207
1208 const_iterator() = default;
1209 Q_IMPLICIT const_iterator(const iterator &o) : i(o.i) {}
1210
1211 const Key &key() const { return i->first; }
1212 const T &value() const { return i->second; }
1213 const T &operator*() const { return i->second; }
1214 const T *operator->() const { return &i->second; }
1215 friend bool operator==(const const_iterator &lhs, const const_iterator &rhs) { return lhs.i == rhs.i; }
1216 friend bool operator!=(const const_iterator &lhs, const const_iterator &rhs) { return lhs.i != rhs.i; }
1217
1218 const_iterator &operator++()
1219 {
1220 ++i;
1221 return *this;
1222 }
1223 const_iterator operator++(int)
1224 {
1225 const_iterator r = *this;
1226 ++i;
1227 return r;
1228 }
1229 const_iterator &operator--()
1230 {
1231 --i;
1232 return *this;
1233 }
1234 const_iterator operator--(int)
1235 {
1236 const_iterator r = *this;
1237 --i;
1238 return r;
1239 }
1240
1241#if QT_DEPRECATED_SINCE(6, 0)
1242 QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMultiMap iterators are not random access")
1243 //! [qmultimap-op-it-plus-step-const]
1244 friend const_iterator operator+(const_iterator it, difference_type j) { return std::next(it, j); }
1245
1246 QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMultiMap iterators are not random access")
1247 //! [qmultimap-op-it-minus-step-const]
1248 friend const_iterator operator-(const_iterator it, difference_type j) { return std::prev(it, j); }
1249
1250 QT_DEPRECATED_VERSION_X_6_0("Use std::next or std::advance; QMultiMap iterators are not random access")
1251 const_iterator &operator+=(difference_type j) { std::advance(*this, j); return *this; }
1252
1253 QT_DEPRECATED_VERSION_X_6_0("Use std::prev or std::advance; QMultiMap iterators are not random access")
1254 const_iterator &operator-=(difference_type j) { std::advance(*this, -j); return *this; }
1255
1256 QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMultiMap iterators are not random access")
1257 //! [qmultimap-op-step-plus-it-const]
1258 friend const_iterator operator+(difference_type j, const_iterator it) { return std::next(it, j); }
1259
1260 QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMultiMap iterators are not random access")
1261 //! [qmultimap-op-step-minus-it-const]
1262 friend const_iterator operator-(difference_type j, const_iterator it) { return std::prev(it, j); }
1263#endif
1264 };
1265
1266 class key_iterator
1267 {
1268 const_iterator i;
1269
1270 public:
1271 typedef typename const_iterator::iterator_category iterator_category;
1272 typedef typename const_iterator::difference_type difference_type;
1273 typedef Key value_type;
1274 typedef const Key *pointer;
1275 typedef const Key &reference;
1276
1277 key_iterator() = default;
1278 explicit key_iterator(const_iterator o) : i(o) { }
1279
1280 const Key &operator*() const { return i.key(); }
1281 const Key *operator->() const { return &i.key(); }
1282 bool operator==(key_iterator o) const { return i == o.i; }
1283 bool operator!=(key_iterator o) const { return i != o.i; }
1284
1285 inline key_iterator &operator++() { ++i; return *this; }
1286 inline key_iterator operator++(int) { return key_iterator(i++);}
1287 inline key_iterator &operator--() { --i; return *this; }
1288 inline key_iterator operator--(int) { return key_iterator(i--); }
1289 const_iterator base() const { return i; }
1290 };
1291
1292 typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator;
1293 typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator;
1294
1295 // STL style
1296 iterator begin() { detach(); return iterator(d->m.begin()); }
1297 const_iterator begin() const { if (!d) return const_iterator(); return const_iterator(d->m.cbegin()); }
1298 const_iterator constBegin() const { return begin(); }
1299 const_iterator cbegin() const { return begin(); }
1300 iterator end() { detach(); return iterator(d->m.end()); }
1301 const_iterator end() const { if (!d) return const_iterator(); return const_iterator(d->m.end()); }
1302 const_iterator constEnd() const { return end(); }
1303 const_iterator cend() const { return end(); }
1304 key_iterator keyBegin() const { return key_iterator(begin()); }
1305 key_iterator keyEnd() const { return key_iterator(end()); }
1306 key_value_iterator keyValueBegin() { return key_value_iterator(begin()); }
1307 key_value_iterator keyValueEnd() { return key_value_iterator(end()); }
1308 const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); }
1309 const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); }
1310 const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); }
1311 const_key_value_iterator constKeyValueEnd() const { return const_key_value_iterator(end()); }
1312 auto asKeyValueRange() & { return QtPrivate::QKeyValueRange(*this); }
1313 auto asKeyValueRange() const & { return QtPrivate::QKeyValueRange(*this); }
1314 auto asKeyValueRange() && { return QtPrivate::QKeyValueRange(std::move(*this)); }
1315 auto asKeyValueRange() const && { return QtPrivate::QKeyValueRange(std::move(*this)); }
1316
1317 iterator erase(const_iterator it)
1318 {
1319 return erase(it, std::next(it));
1320 }
1321
1322 iterator erase(const_iterator afirst, const_iterator alast)
1323 {
1324 if (!d)
1325 return iterator();
1326
1327 if (!d.isShared())
1328 return iterator(d->m.erase(afirst.i, alast.i));
1329
1330 auto result = d->erase(afirst.i, alast.i);
1331 d.reset(result.data);
1332 return iterator(result.it);
1333 }
1334
1335 // more Qt
1336 typedef iterator Iterator;
1337 typedef const_iterator ConstIterator;
1338
1339 size_type count() const
1340 {
1341 return size();
1342 }
1343
1344 iterator find(const Key &key)
1345 {
1346 const auto copy = d.isShared() ? *this : QMultiMap(); // keep `key` alive across the detach
1347 detach();
1348 return iterator(d->m.find(key));
1349 }
1350
1351 const_iterator find(const Key &key) const
1352 {
1353 if (!d)
1354 return const_iterator();
1355 return const_iterator(d->m.find(key));
1356 }
1357
1358 const_iterator constFind(const Key &key) const
1359 {
1360 return find(key);
1361 }
1362
1363 iterator find(const Key &key, const T &value)
1364 {
1365 const auto copy = d.isShared() ? *this : QMultiMap(); // keep `key`/`value` alive across the detach
1366
1367 detach();
1368
1369 auto range = d->m.equal_range(key);
1370 auto i = std::find_if(range.first, range.second,
1371 MapData::valueIsEqualTo(value));
1372
1373 if (i != range.second)
1374 return iterator(i);
1375 return iterator(d->m.end());
1376 }
1377
1378 const_iterator find(const Key &key, const T &value) const
1379 {
1380 if (!d)
1381 return const_iterator();
1382
1383 auto range = d->m.equal_range(key);
1384 auto i = std::find_if(range.first, range.second,
1385 MapData::valueIsEqualTo(value));
1386
1387 if (i != range.second)
1388 return const_iterator(i);
1389 return const_iterator(d->m.end());
1390 }
1391
1392 const_iterator constFind(const Key &key, const T &value) const
1393 {
1394 return find(key, value);
1395 }
1396
1397 iterator lowerBound(const Key &key)
1398 {
1399 const auto copy = d.isShared() ? *this : QMultiMap(); // keep `key` alive across the detach
1400 detach();
1401 return iterator(d->m.lower_bound(key));
1402 }
1403
1404 const_iterator lowerBound(const Key &key) const
1405 {
1406 if (!d)
1407 return const_iterator();
1408 return const_iterator(d->m.lower_bound(key));
1409 }
1410
1411 iterator upperBound(const Key &key)
1412 {
1413 const auto copy = d.isShared() ? *this : QMultiMap(); // keep `key` alive across the detach
1414 detach();
1415 return iterator(d->m.upper_bound(key));
1416 }
1417
1418 const_iterator upperBound(const Key &key) const
1419 {
1420 if (!d)
1421 return const_iterator();
1422 return const_iterator(d->m.upper_bound(key));
1423 }
1424
1425 iterator insert(const Key &key, const T &value)
1426 {
1427 const auto copy = d.isShared() ? *this : QMultiMap(); // keep `key`/`value` alive across the detach
1428 detach();
1429 // note that std::multimap inserts at the end of an equal_range for a key,
1430 // QMultiMap at the beginning.
1431 auto i = d->m.lower_bound(key);
1432 return iterator(d->m.insert(i, {key, value}));
1433 }
1434
1435 iterator insert(const_iterator pos, const Key &key, const T &value)
1436 {
1437 const auto copy = d.isShared() ? *this : QMultiMap(); // keep `key`/`value` alive across the detach
1438 typename Map::const_iterator dpos;
1439 if (!d || d.isShared()) {
1440 auto posDistance = d ? std::distance(d->m.cbegin(), pos.i) : 0;
1441 detach();
1442 dpos = std::next(d->m.cbegin(), posDistance);
1443 } else {
1444 dpos = pos.i;
1445 }
1446 return iterator(d->m.insert(dpos, {key, value}));
1447 }
1448
1449#if QT_DEPRECATED_SINCE(6, 0)
1450 QT_DEPRECATED_VERSION_X_6_0("Use insert() instead")
1451 iterator insertMulti(const Key &key, const T &value)
1452 {
1453 return insert(key, value);
1454 }
1455 QT_DEPRECATED_VERSION_X_6_0("Use insert() instead")
1456 iterator insertMulti(const_iterator pos, const Key &key, const T &value)
1457 {
1458 return insert(pos, key, value);
1459 }
1460
1461 QT_DEPRECATED_VERSION_X_6_0("Use unite() instead")
1462 void insert(const QMultiMap<Key, T> &map)
1463 {
1464 unite(map);
1465 }
1466
1467 QT_DEPRECATED_VERSION_X_6_0("Use unite() instead")
1468 void insert(QMultiMap<Key, T> &&map)
1469 {
1470 unite(std::move(map));
1471 }
1472#endif
1473
1474 iterator replace(const Key &key, const T &value)
1475 {
1476 const auto copy = d.isShared() ? *this : QMultiMap(); // keep `key`/`value` alive across the detach
1477
1478 // TODO: improve. No need of copying and then overwriting.
1479 detach();
1480
1481 // Similarly, improve here (e.g. lower_bound and hinted insert);
1482 // there's no insert_or_assign on multimaps
1483 auto i = d->m.find(key);
1484 if (i != d->m.end())
1485 i->second = value;
1486 else
1487 i = d->m.insert({key, value});
1488
1489 return iterator(i);
1490 }
1491
1492 // STL compatibility
1493 inline bool empty() const { return isEmpty(); }
1494
1495 QPair<iterator, iterator> equal_range(const Key &akey)
1496 {
1497 const auto copy = d.isShared() ? *this : QMultiMap(); // keep `key` alive across the detach
1498 detach();
1499 auto result = d->m.equal_range(akey);
1500 return {iterator(result.first), iterator(result.second)};
1501 }
1502
1503 QPair<const_iterator, const_iterator> equal_range(const Key &akey) const
1504 {
1505 if (!d)
1506 return {};
1507 auto result = d->m.equal_range(akey);
1508 return {const_iterator(result.first), const_iterator(result.second)};
1509 }
1510
1511 QMultiMap &unite(const QMultiMap &other)
1512 {
1513 if (other.isEmpty())
1514 return *this;
1515
1516 detach();
1517
1518 auto copy = other.d->m;
1519#ifdef __cpp_lib_node_extract
1520 copy.merge(std::move(d->m));
1521#else
1522 copy.insert(std::make_move_iterator(d->m.begin()),
1523 std::make_move_iterator(d->m.end()));
1524#endif
1525 d->m = std::move(copy);
1526 return *this;
1527 }
1528
1529 QMultiMap &unite(QMultiMap<Key, T> &&other)
1530 {
1531 if (!other.d || other.d->m.empty())
1532 return *this;
1533
1534 if (other.d.isShared()) {
1535 // fall back to a regular copy
1536 unite(other);
1537 return *this;
1538 }
1539
1540 detach();
1541
1542#ifdef __cpp_lib_node_extract
1543 other.d->m.merge(std::move(d->m));
1544#else
1545 other.d->m.insert(std::make_move_iterator(d->m.begin()),
1546 std::make_move_iterator(d->m.end()));
1547#endif
1548 *this = std::move(other);
1549 return *this;
1550 }
1551};
1552
1553Q_DECLARE_ASSOCIATIVE_ITERATOR(MultiMap)
1554Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(MultiMap)
1555
1556template <typename Key, typename T>
1557QMultiMap<Key, T> operator+(const QMultiMap<Key, T> &lhs, const QMultiMap<Key, T> &rhs)
1558{
1559 auto result = lhs;
1560 result += rhs;
1561 return result;
1562}
1563
1564template <typename Key, typename T>
1565QMultiMap<Key, T> operator+=(QMultiMap<Key, T> &lhs, const QMultiMap<Key, T> &rhs)
1566{
1567 return lhs.unite(rhs);
1568}
1569
1570template <typename Key, typename T, typename Predicate>
1571qsizetype erase_if(QMultiMap<Key, T> &map, Predicate pred)
1572{
1573 return QtPrivate::associative_erase_if(map, pred);
1574}
1575
1576QT_END_NAMESPACE
1577
1578#endif // QMAP_H
1579

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