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