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

Provided by KDAB

Privacy Policy
Learn Advanced QML with KDAB
Find out more

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