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