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