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

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