qt/qtbase/src/corelib/tools/qmap.h

Revision control

++ // Copyright (C) 2020 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
++ // Copyright (C) 2021 The Qt Company Ltd.
++ // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
++ // Qt-Security score:significant reason:default
++
++ #ifndef QMAP_H
++ #define QMAP_H
++
++ #include <QtCore/qcompare.h>
++ #include <QtCore/qhashfunctions.h>
++ #include <QtCore/qiterator.h>
++ #include <QtCore/qlist.h>
++ #include <QtCore/qrefcount.h>
++ #include <QtCore/qpair.h>
++ #include <QtCore/qscopeguard.h>
++ #include <QtCore/qshareddata.h>
++ #include <QtCore/qshareddata_impl.h>
++ #include <QtCore/qttypetraits.h>
++
++ #include <functional>
++ #include <initializer_list>
++ #include <map>
++ #include <algorithm>
++
++ QT_BEGIN_NAMESPACE
++
++ // common code shared between QMap and QMultimap
++ template <typename AMap>
++ class QMapData : public QSharedData
++ {
++ public:
++ using Map = AMap;
++ using Key = typename Map::key_type;
++ using T = typename Map::mapped_type;
++ using value_type = typename Map::value_type;
++ using size_type = typename Map::size_type;
++ using iterator = typename Map::iterator;
++ using const_iterator = typename Map::const_iterator;
++
++ static_assert(std::is_nothrow_destructible_v<Key>, "Types with throwing destructors are not supported in Qt containers.");
++ static_assert(std::is_nothrow_destructible_v<T>, "Types with throwing destructors are not supported in Qt containers.");
++
++ Map m;
++
++ QMapData() = default;
++ explicit QMapData(const Map &other)
++ : m(other)
++ {}
++
++ explicit QMapData(Map &&other)
++ : m(std::move(other))
++ {}
++
++ // copies from source all the values not matching key.
++ // returns how many were NOT copied (removed), and first removed iterator
++ auto copyIfNotEquivalentTo(const Map &source, const Key &key)
++ {
++ Q_ASSERT(m.empty());
++
++ size_type result = 0;
++ auto foundIt = source.end();
++
++ const auto markFound = [&](auto it) {
++ if (result == 0)
++ foundIt = it;
++ ++result;
++ };
++ const auto keep = [this](auto it) { m.insert(m.cend(), *it); };
++
++ auto it = source.cbegin();
++ const auto end = source.cend();
++ const auto &cmp = m.key_comp();
++ // Keep all before:
++ for (; it != end && cmp(it->first, key); ++it)
++ keep(it);
++ // Count and skip matches:
++ for (; it != end && !cmp(key, it->first); ++it)
++ markFound(it);
++ // Keep all after:
++ for (; it != end; ++it)
++ keep(it);
++
++ struct resultType { size_type count; decltype(source.begin()) iterator; };
++ return resultType{result, foundIt};
++ }
++
++ void copyExceptFor(const Map &source, const iterator &skipit)
++ {
++ Q_ASSERT(m.empty());
++
++ auto it = source.cend();
++ const auto end = source.cbegin();
++ auto hint = m.end();
++ if (it == end)
++ return;
++ do {
++ --it;
++ if (it == skipit)
++ continue;
++ hint = m.emplace_hint(hint, it->first, it->second);
++ } while (it != end);
++ }
++
++ // Merges the two sources into this one, giving preference to source2
++ void fillWithMergeOf(const Map &source1, const Map &source2)
++ {
++ Q_ASSERT(m.empty());
++
++ auto insertionHint = m.end();
++ auto src1It = source1.crbegin();
++ const auto src1End = source1.crend();
++ auto src2It = source2.crbegin();
++ const auto src2End = source2.crend();
++ const auto &keyCompare = m.key_comp();
++ while (src1It != src1End && src2It != src2End) {
++ if (keyCompare(src2It->first, src1It->first)) {
++ insertionHint = m.emplace_hint(insertionHint, src1It->first, src1It->second);
++ ++src1It;
++ } else if (keyCompare(src1It->first, src2It->first)) {
++ insertionHint = m.emplace_hint(insertionHint, src2It->first, src2It->second);
++ ++src2It;
++ } else {
++ // Equivalence, insert source2, forget source1
++ insertionHint = m.emplace_hint(insertionHint, src2It->first, src2It->second);
++ ++src1It;
++ ++src2It;
++ }
++ }
++ for (; src1It != src1End; ++src1It)
++ insertionHint = m.emplace_hint(insertionHint, src1It->first, src1It->second);
++ for (; src2It != src2End; ++src2It)
++ insertionHint = m.emplace_hint(insertionHint, src2It->first, src2It->second);
++ }
++
++ // Merge source into this one without changing source as std::map::merge would
++ void insertMap(const Map &source)
++ {
++ Q_ASSERT(!m.empty());
++ // copy in reverse order, trying to make effective use of insertionHint.
++ auto insertionHint = m.end();
++ auto it = source.crbegin();
++ const auto end = source.crend();
++ for (; it != end; ++it)
++ insertionHint = m.emplace_hint(insertionHint, it->first, it->second);
++ }
++
++ // used in key(T), count(Key, T), find(key, T), etc; returns a
++ // comparator object suitable for algorithms with std::(multi)map
++ // iterators.
++ static auto valueIsEqualTo(const T &value)
++ {
++ return [&value](const auto &v) { return v.second == value; };
++ }
++
++ Key key(const T &value, const Key &defaultKey) const
++ {
++ auto i = std::find_if(m.cbegin(),
++ m.cend(),
++ valueIsEqualTo(value));
++ if (i != m.cend())
++ return i->first;
++
++ return defaultKey;
++ }
++
++ QList<Key> keys() const
++ {
++ QList<Key> result;
++ result.reserve(m.size());
++
++ const auto extractKey = [](const auto &v) { return v.first; };
++
++ std::transform(m.cbegin(),
++ m.cend(),
++ std::back_inserter(result),
++ extractKey);
++ return result;
++ }
++
++ QList<Key> keys(const T &value) const
++ {
++ QList<Key> result;
++ result.reserve(m.size());
++ // no std::transform_if...
++ for (const auto &v : m) {
++ if (v.second == value)
++ result.append(v.first);
++ }
++ result.shrink_to_fit();
++ return result;
++ }
++
++ QList<T> values() const
++ {
++ QList<T> result;
++ result.reserve(m.size());
++
++ const auto extractValue = [](const auto &v) { return v.second; };
++
++ std::transform(m.cbegin(),
++ m.cend(),
++ std::back_inserter(result),
++ extractValue);
++ return result;
++ }
++
++ size_type count(const Key &key) const
++ {
++ return m.count(key);
++ }
++
++ // Used in erase. Allocates a new QMapData and copies, from this->m,
++ // the elements not in the [first, last) range. The return contains
++ // the new QMapData and an iterator in its map pointing at the first
++ // element after the erase.
++ struct EraseResult {
++ QMapData *data;
++ iterator it;
++ };
++
++ EraseResult erase(const_iterator first, const_iterator last) const
++ {
++ EraseResult result;
++ result.data = new QMapData;
++ result.it = result.data->m.end();
++ const auto newDataEnd = result.it;
++
++ auto i = m.begin();
++ const auto e = m.end();
++
++ // copy over all the elements before first
++ while (i != first) {
++ result.it = result.data->m.insert(newDataEnd, *i);
++ ++i;
++ }
++
++ // skip until last
++ while (i != last)
++ ++i;
++
++ // copy from last to the end
++ while (i != e) {
++ result.data->m.insert(newDataEnd, *i);
++ ++i;
++ }
++
++ if (result.it != newDataEnd)
++ ++result.it;
++
++ return result;
++ }
++ };
++
++ // common type traits
++ namespace QtPrivate {
++
++ template <typename Container, typename ...Ts>
++ using map_has_operator_less_than =
++ std::conjunction<QTypeTraits::has_operator_less_than_container<Container, Ts>...>;
++
++ // The is_base_of<Container, T> check is required for recursive containers.
++ // Without it MSVC produces errors like:
++ //
++ // error C2968:
++ // 'if_map_has_relational_operators<QMap<NoCmpParamRecursiveMapK, Empty>,
++ // NoCmpParamRecursiveMapK, Empty>':
++ // recursive alias declaration
++ //
++ // The solution is similar to QTypeTraits::*_container checks.
++ template <typename Container, typename T>
++ using map_has_qt_compare_three_way_container =
++ std::disjunction<std::is_base_of<Container, T>, Qt::has_qt_compare_three_way<T>>;
++
++ template <typename Container, typename ...Ts>
++ using map_has_qt_compare_three_way =
++ std::conjunction<map_has_qt_compare_three_way_container<Container, Ts>...>;
++
++ template <typename Container, typename ...Ts>
++ using if_map_has_relational_operators =
++ std::enable_if_t<
++ std::disjunction_v<
++ map_has_operator_less_than<Container, Ts...>,
++ map_has_qt_compare_three_way<Container, Ts...>
++ >,
++ bool>;
++
++ } // namespace QtPrivate
++
++ //
++ // QMap
++ //
++
++ template <class Key, class T>
++ class QMap
++ {
++ using Map = std::map<Key, T>;
++ using MapData = QMapData<Map>;
++ QtPrivate::QExplicitlySharedDataPointerV2<MapData> d;
++
++ friend class QMultiMap<Key, T>;
++
++ public:
++ using key_type = Key;
++ using mapped_type = T;
++ using difference_type = qptrdiff;
++ using size_type = qsizetype;
++
++ QMap() = default;
++
++ // implicitly generated special member functions are OK!
++
++ void swap(QMap<Key, T> &other) noexcept
++ {
++ d.swap(other.d);
++ }
++
++ QMap(std::initializer_list<std::pair<Key, T>> list)
++ {
++ for (auto &p : list)
++ insert(p.first, p.second);
++ }
++
++ explicit QMap(const std::map<Key, T> &other)
++ : d(other.empty() ? nullptr : new MapData(other))
++ {
++ }
++
++ explicit QMap(std::map<Key, T> &&other)
++ : d(other.empty() ? nullptr : new MapData(std::move(other)))
++ {
++ }
++
++ std::map<Key, T> toStdMap() const &
++ {
++ if (d)
++ return d->m;
++ return {};
++ }
++
++ std::map<Key, T> toStdMap() &&
++ {
++ if (d) {
++ if (d.isShared())
++ return d->m;
++ else
++ return std::move(d->m);
++ }
++
++ return {};
++ }
++
++ #ifndef Q_QDOC
++ private:
++ template <typename AKey = Key, typename AT = T,
++ QTypeTraits::compare_eq_result_container<QMap, AKey, AT> = true>
++ friend bool comparesEqual(const QMap &lhs, const QMap &rhs)
++ {
++ if (lhs.d == rhs.d)
++ return true;
++ if (!lhs.d)
++ return rhs == lhs;
++ Q_ASSERT(lhs.d);
++ return rhs.d ? (lhs.d->m == rhs.d->m) : lhs.d->m.empty();
++ }
++ QT_DECLARE_EQUALITY_OPERATORS_HELPER(QMap, QMap, /* non-constexpr */, noexcept(false),
++ template <typename AKey = Key, typename AT = T,
++ QTypeTraits::compare_eq_result_container<QMap, AKey, AT> = true>)
++
++ template <typename AKey = Key, typename AT = T,
++ QtPrivate::if_map_has_relational_operators<QMap, AKey, AT> = true>
++ friend auto compareThreeWay(const QMap &lhs, const QMap &rhs)
++ {
++ return QtOrderingPrivate::lexicographicalCompareThreeWay(lhs.constKeyValueBegin(),
++ lhs.constKeyValueEnd(),
++ rhs.constKeyValueBegin(),
++ rhs.constKeyValueEnd());
++ }
++ QT_DECLARE_ORDERING_HELPER_AUTO(QMap, QMap, /* non-constexpr */, noexcept(false),
++ template <typename AKey = Key, typename AT = T,
++ QtPrivate::if_map_has_relational_operators<QMap, AKey, AT> = true>)
++
++ public:
++ #else
++ friend bool operator==(const QMap &lhs, const QMap &rhs);
++ friend bool operator!=(const QMap &lhs, const QMap &rhs);
++ friend bool operator<(const QMap &lhs, const QMap &rhs);
++ friend bool operator>(const QMap &lhs, const QMap &rhs);
++ friend bool operator<=(const QMap &lhs, const QMap &rhs);
++ friend bool operator>=(const QMap &lhs, const QMap &rhs);
++ friend auto operator<=>(const QMap &lhs, const QMap &rhs);
++ #endif // Q_QDOC
++
++ size_type size() const { return d ? size_type(d->m.size()) : size_type(0); }
++
++ [[nodiscard]]
++ bool isEmpty() const { return d ? d->m.empty() : true; }
++
++ void detach()
++ {
++ if (d)
++ d.detach();
++ else
++ d.reset(new MapData);
++ }
++
++ // A detach for holding an already shared copy, until calling function
++ // is done using references to keys or values that might reference it.
++ [[nodiscard]]
++ QMap referenceHoldingDetach()
++ {
++ if (!d) {
++ d.reset(new MapData);
++ } else if (d.isShared()) {
++ auto hold = *this;
++ d.detach();
++ return hold;
++ }
++ return {};
++ }
++
++ // Specialized version of referenceHoldingDetach(), which will not copy key, if copying
++ [[nodiscard]]
++ QMap referenceHoldingDetachExcept(const Key &key)
++ {
++ if (!d) {
++ d.reset(new MapData);
++ } else if (d.isShared()) {
++ auto hold = *this;
++ QtPrivate::QExplicitlySharedDataPointerV2<MapData> newData(new MapData);
++ newData->copyIfNotEquivalentTo(d->m, key);
++ d.swap(newData);
++ return hold;
++ }
++ return {};
++ }
++
++ bool isDetached() const noexcept
++ {
++ return d ? !d.isShared() : false; // false makes little sense, but that's shared_null's behavior...
++ }
++
++ bool isSharedWith(const QMap<Key, T> &other) const noexcept
++ {
++ return d == other.d; // also this makes little sense?
++ }
++
++ void clear()
++ {
++ if (!d)
++ return;
++
++ if (!d.isShared())
++ d->m.clear();
++ else
++ d.reset();
++ }
++
++ size_type remove(const Key &key)
++ {
++ if (!d)
++ return 0;
++
++ if (!d.isShared())
++ return size_type(d->m.erase(key));
++
++ MapData *newData = new MapData;
++ size_type result = newData->copyIfNotEquivalentTo(d->m, key).count;
++
++ d.reset(newData);
++
++ return result;
++ }
++
++ template <typename Predicate>
++ size_type removeIf(Predicate pred)
++ {
++ return QtPrivate::associative_erase_if(*this, pred);
++ }
++
++ T take(const Key &key)
++ {
++ if (!d)
++ return T();
++
++ if (d.isShared()) {
++ MapData *m = new MapData;
++ // For historic reasons, we always un-share (was: detach()) when
++ // this function is called, even if `key` isn't found
++ const auto commit = qScopeGuard([&] { d.reset(m); });
++
++ auto result = m->copyIfNotEquivalentTo(d->m, key);
++ if (result.count)
++ return result.iterator->second;
++ // if we reach here, `key` wasn't found:
++ return T();
++ }
++
++ #ifdef __cpp_lib_node_extract
++ if (const auto node = d->m.extract(key))
++ return std::move(node.mapped());
++ #else
++ auto i = d->m.find(key);
++ if (i != d->m.end()) {
++ // ### breaks RVO on most compilers (but only on old-fashioned ones, so who cares?)
++ T result(std::move(i->second));
++ d->m.erase(i);
++ return result;
++ }
++ #endif
++ return T();
++ }
++
++ bool contains(const Key &key) const
++ {
++ if (!d)
++ return false;
++ auto i = d->m.find(key);
++ return i != d->m.end();
++ }
++
++ Key key(const T &value, const Key &defaultKey = Key()) const
++ {
++ if (!d)
++ return defaultKey;
++
++ return d->key(value, defaultKey);
++ }
++
++ T value(const Key &key, const T &defaultValue = T()) const
++ {
++ if (!d)
++ return defaultValue;
++ const auto i = d->m.find(key);
++ if (i != d->m.cend())
++ return i->second;
++ return defaultValue;
++ }
++
++ T &operator[](const Key &key)
++ {
++ const auto hold = referenceHoldingDetach();
++ auto i = d->m.find(key);
++ if (i == d->m.end())
++ i = d->m.insert({key, T()}).first;
++ return i->second;
++ }
++
++ // CHANGE: return T, not const T!
++ T operator[](const Key &key) const
++ {
++ return value(key);
++ }
++
++ QList<Key> keys() const
++ {
++ if (!d)
++ return {};
++ return d->keys();
++ }
++
++ QList<Key> keys(const T &value) const
++ {
++ if (!d)
++ return {};
++ return d->keys(value);
++ }
++
++ QList<T> values() const
++ {
++ if (!d)
++ return {};
++ return d->values();
++ }
++
++ size_type count(const Key &key) const
++ {
++ if (!d)
++ return 0;
++ return d->count(key);
++ }
++
++ size_type count() const
++ {
++ return size();
++ }
++
++ inline const Key &firstKey() const { Q_ASSERT(!isEmpty()); return constBegin().key(); }
++ inline const Key &lastKey() const { Q_ASSERT(!isEmpty()); return (--constEnd()).key(); }
++
++ inline T &first() { Q_ASSERT(!isEmpty()); return *begin(); }
++ inline const T &first() const { Q_ASSERT(!isEmpty()); return *constBegin(); }
++ inline T &last() { Q_ASSERT(!isEmpty()); return *(--end()); }
++ inline const T &last() const { Q_ASSERT(!isEmpty()); return *(--constEnd()); }
++
++ class const_iterator;
++
++ class iterator
++ {
++ friend class QMap<Key, T>;
++ friend class const_iterator;
++
++ typename Map::iterator i;
++ explicit iterator(typename Map::iterator it) : i(it) {}
++ public:
++ using iterator_category = std::bidirectional_iterator_tag;
++ using difference_type = qptrdiff;
++ using value_type = T;
++ using pointer = T *;
++ using reference = T &;
++
++ iterator() = default;
++
++ const Key &key() const { return i->first; }
++ T &value() const { return i->second; }
++ T &operator*() const { return i->second; }
++ T *operator->() const { return &i->second; }
++ friend bool operator==(const iterator &lhs, const iterator &rhs) { return lhs.i == rhs.i; }
++ friend bool operator!=(const iterator &lhs, const iterator &rhs) { return lhs.i != rhs.i; }
++
++ iterator &operator++()
++ {
++ ++i;
++ return *this;
++ }
++ iterator operator++(int)
++ {
++ iterator r = *this;
++ ++i;
++ return r;
++ }
++ iterator &operator--()
++ {
++ --i;
++ return *this;
++ }
++ iterator operator--(int)
++ {
++ iterator r = *this;
++ --i;
++ return r;
++ }
++
++ #if QT_DEPRECATED_SINCE(6, 0)
++ QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMap iterators are not random access")
++ //! [qmap-op-it-plus-step]
++ friend iterator operator+(iterator it, difference_type j) { return std::next(it, j); }
++
++ QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMap iterators are not random access")
++ //! [qmap-op-it-minus-step]
++ friend iterator operator-(iterator it, difference_type j) { return std::prev(it, j); }
++
++ QT_DEPRECATED_VERSION_X_6_0("Use std::next or std::advance; QMap iterators are not random access")
++ iterator &operator+=(difference_type j) { std::advance(*this, j); return *this; }
++
++ QT_DEPRECATED_VERSION_X_6_0("Use std::prev or std::advance; QMap iterators are not random access")
++ iterator &operator-=(difference_type j) { std::advance(*this, -j); return *this; }
++
++ QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMap iterators are not random access")
++ //! [qmap-op-step-plus-it]
++ friend iterator operator+(difference_type j, iterator it) { return std::next(it, j); }
++
++ QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMap iterators are not random access")
++ //! [qmap-op-step-minus-it]
++ friend iterator operator-(difference_type j, iterator it) { return std::prev(it, j); }
++ #endif
++ };
++
++ class const_iterator
++ {
++ friend class QMap<Key, T>;
++ typename Map::const_iterator i;
++ explicit const_iterator(typename Map::const_iterator it) : i(it) {}
++
++ public:
++ using iterator_category = std::bidirectional_iterator_tag;
++ using difference_type = qptrdiff;
++ using value_type = T;
++ using pointer = const T *;
++ using reference = const T &;
++
++ const_iterator() = default;
++ Q_IMPLICIT const_iterator(const iterator &o) : i(o.i) {}
++
++ const Key &key() const { return i->first; }
++ const T &value() const { return i->second; }
++ const T &operator*() const { return i->second; }
++ const T *operator->() const { return &i->second; }
++ friend bool operator==(const const_iterator &lhs, const const_iterator &rhs) { return lhs.i == rhs.i; }
++ friend bool operator!=(const const_iterator &lhs, const const_iterator &rhs) { return lhs.i != rhs.i; }
++
++ const_iterator &operator++()
++ {
++ ++i;
++ return *this;
++ }
++ const_iterator operator++(int)
++ {
++ const_iterator r = *this;
++ ++i;
++ return r;
++ }
++ const_iterator &operator--()
++ {
++ --i;
++ return *this;
++ }
++ const_iterator operator--(int)
++ {
++ const_iterator r = *this;
++ --i;
++ return r;
++ }
++
++ #if QT_DEPRECATED_SINCE(6, 0)
++ QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMap iterators are not random access")
++ //! [qmap-op-it-plus-step-const]
++ friend const_iterator operator+(const_iterator it, difference_type j) { return std::next(it, j); }
++
++ QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMap iterators are not random access")
++ //! [qmap-op-it-minus-step-const]
++ friend const_iterator operator-(const_iterator it, difference_type j) { return std::prev(it, j); }
++
++ QT_DEPRECATED_VERSION_X_6_0("Use std::next or std::advance; QMap iterators are not random access")
++ const_iterator &operator+=(difference_type j) { std::advance(*this, j); return *this; }
++
++ QT_DEPRECATED_VERSION_X_6_0("Use std::prev or std::advance; QMap iterators are not random access")
++ const_iterator &operator-=(difference_type j) { std::advance(*this, -j); return *this; }
++
++ QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMap iterators are not random access")
++ //! [qmap-op-step-plus-it-const]
++ friend const_iterator operator+(difference_type j, const_iterator it) { return std::next(it, j); }
++
++ QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMap iterators are not random access")
++ //! [qmap-op-step-minus-it-const]
++ friend const_iterator operator-(difference_type j, const_iterator it) { return std::prev(it, j); }
++ #endif
++ };
++
++ class key_iterator
++ {
++ const_iterator i;
++
++ public:
++ typedef typename const_iterator::iterator_category iterator_category;
++ typedef typename const_iterator::difference_type difference_type;
++ typedef Key value_type;
++ typedef const Key *pointer;
++ typedef const Key &reference;
++
++ key_iterator() = default;
++ explicit key_iterator(const_iterator o) : i(o) { }
++
++ const Key &operator*() const { return i.key(); }
++ const Key *operator->() const { return &i.key(); }
++ bool operator==(key_iterator o) const { return i == o.i; }
++ bool operator!=(key_iterator o) const { return i != o.i; }
++
++ inline key_iterator &operator++() { ++i; return *this; }
++ inline key_iterator operator++(int) { return key_iterator(i++);}
++ inline key_iterator &operator--() { --i; return *this; }
++ inline key_iterator operator--(int) { return key_iterator(i--); }
++ const_iterator base() const { return i; }
++ };
++
++ typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator;
++ typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator;
++
++ // STL style
++ iterator begin() { detach(); return iterator(d->m.begin()); }
++ const_iterator begin() const { if (!d) return const_iterator(); return const_iterator(d->m.cbegin()); }
++ const_iterator constBegin() const { return begin(); }
++ const_iterator cbegin() const { return begin(); }
++ iterator end() { detach(); return iterator(d->m.end()); }
++ const_iterator end() const { if (!d) return const_iterator(); return const_iterator(d->m.end()); }
++ const_iterator constEnd() const { return end(); }
++ const_iterator cend() const { return end(); }
++ key_iterator keyBegin() const { return key_iterator(begin()); }
++ key_iterator keyEnd() const { return key_iterator(end()); }
++ key_value_iterator keyValueBegin() { return key_value_iterator(begin()); }
++ key_value_iterator keyValueEnd() { return key_value_iterator(end()); }
++ const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); }
++ const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); }
++ const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); }
++ const_key_value_iterator constKeyValueEnd() const { return const_key_value_iterator(end()); }
++ auto asKeyValueRange() & { return QtPrivate::QKeyValueRange<QMap &>(*this); }
++ auto asKeyValueRange() const & { return QtPrivate::QKeyValueRange<const QMap &>(*this); }
++ auto asKeyValueRange() && { return QtPrivate::QKeyValueRange<QMap>(std::move(*this)); }
++ auto asKeyValueRange() const && { return QtPrivate::QKeyValueRange<QMap>(std::move(*this)); }
++
++ iterator erase(const_iterator it)
++ {
++ return erase(it, std::next(it));
++ }
++
++ iterator erase(const_iterator afirst, const_iterator alast)
++ {
++ if (!d)
++ return iterator();
++
++ if (!d.isShared())
++ return iterator(d->m.erase(afirst.i, alast.i));
++
++ auto result = d->erase(afirst.i, alast.i);
++ d.reset(result.data);
++ return iterator(result.it);
++ }
++
++ // more Qt
++ typedef iterator Iterator;
++ typedef const_iterator ConstIterator;
++
++ iterator find(const Key &key)
++ {
++ const auto hold = referenceHoldingDetach();
++ return iterator(d->m.find(key));
++ }
++
++ const_iterator find(const Key &key) const
++ {
++ if (!d)
++ return const_iterator();
++ return const_iterator(d->m.find(key));
++ }
++
++ const_iterator constFind(const Key &key) const
++ {
++ return find(key);
++ }
++
++ iterator lowerBound(const Key &key)
++ {
++ const auto hold = referenceHoldingDetach();
++ return iterator(d->m.lower_bound(key));
++ }
++
++ const_iterator lowerBound(const Key &key) const
++ {
++ if (!d)
++ return const_iterator();
++ return const_iterator(d->m.lower_bound(key));
++ }
++
++ iterator upperBound(const Key &key)
++ {
++ const auto hold = referenceHoldingDetach();
++ return iterator(d->m.upper_bound(key));
++ }
++
++ const_iterator upperBound(const Key &key) const
++ {
++ if (!d)
++ return const_iterator();
++ return const_iterator(d->m.upper_bound(key));
++ }
++
++ iterator insert(const Key &key, const T &value)
++ {
++ const auto hold = referenceHoldingDetachExcept(key);
++ return iterator(d->m.insert_or_assign(key, value).first);
++ }
++
++ iterator insert(const_iterator pos, const Key &key, const T &value)
++ {
++ if (!d) {
++ detach();
++ return iterator(d->m.emplace(key, value).first);
++ } else if (d.isShared()) {
++ auto posDistance = std::distance(d->m.cbegin(), pos.i);
++ const auto hold = referenceHoldingDetachExcept(key);
++ auto dpos = std::next(d->m.cbegin(), posDistance);
++ return iterator(d->m.insert_or_assign(dpos, key, value));
++ }
++ return iterator(d->m.insert_or_assign(pos.i, key, value));
++ }
++
++ void insert(const QMap<Key, T> &map)
++ {
++ if (map.isEmpty())
++ return;
++
++ if (isEmpty()) {
++ *this = map;
++ return;
++ }
++
++ if (d.isShared()) {
++ QtPrivate::QExplicitlySharedDataPointerV2<MapData> newD(new MapData);
++ const auto commit = qScopeGuard([&] { newD.swap(d); });
++ newD->fillWithMergeOf(d->m, map.d->m);
++ return;
++ }
++
++ #ifdef __cpp_lib_node_extract
++ // Since std::map::merge is destructive only use it when not shared
++ auto copy = map.d->m;
++ copy.merge(d->m);
++ d->m = std::move(copy);
++ #else
++ QtPrivate::QExplicitlySharedDataPointerV2<MapData> newD(new MapData);
++ const auto commit = qScopeGuard([&] { newD.swap(d); });
++ newD->fillWithMergeOf(d->m, map.d->m);
++
++ #endif
++ }
++
++ void insert(QMap<Key, T> &&map)
++ {
++ if (map.isEmpty() || map.d.isShared()) {
++ // fall back to a regular copy
++ insert(map);
++ return;
++ }
++
++ // Otherwise insert into map, and do a swap on return
++ const auto commit = qScopeGuard([&] { map.swap(*this); });
++ if (isEmpty())
++ return;
++
++ if (d.isShared()) {
++ map.d->insertMap(d->m);
++ return;
++ }
++
++ #ifdef __cpp_lib_node_extract
++ map.d->m.merge(std::move(d->m));
++ #else
++ // same as above
++ map.d->insertMap(d->m);
++ #endif
++ }
++
++ // STL compatibility
++ [[nodiscard]]
++ inline bool empty() const
++ {
++ return isEmpty();
++ }
++
++ std::pair<iterator, iterator> equal_range(const Key &akey)
++ {
++ const auto hold = referenceHoldingDetach();
++ auto result = d->m.equal_range(akey);
++ return {iterator(result.first), iterator(result.second)};
++ }
++
++ std::pair<const_iterator, const_iterator> equal_range(const Key &akey) const
++ {
++ if (!d)
++ return {};
++ auto result = d->m.equal_range(akey);
++ return {const_iterator(result.first), const_iterator(result.second)};
++ }
++
++ private:
++ #ifdef Q_QDOC
++ friend size_t qHash(const QMap &key, size_t seed = 0);
++ #else
++ # if defined(Q_CC_GHS) || defined (Q_CC_MSVC)
++ // GHS and MSVC tries to intantiate qHash() for the noexcept running into a
++ // non-SFINAE'ed hard error... Create an artificial SFINAE context as a
++ // work-around:
++ template <typename M, std::enable_if_t<std::is_same_v<M, QMap>, bool> = true>
++ friend QtPrivate::QHashMultiReturnType<typename M::key_type, typename M::mapped_type>
++ # else
++ using M = QMap;
++ friend size_t
++ # endif
++ qHash(const M &key, size_t seed = 0)
++ noexcept(QHashPrivate::noexceptPairHash<typename M::key_type, typename M::mapped_type>())
++ {
++ if (!key.d)
++ return seed;
++ // don't use qHashRange to avoid its compile-time overhead:
++ return std::accumulate(key.d->m.begin(), key.d->m.end(), seed,
++ QtPrivate::QHashCombine{seed});
++ }
++ #endif // !Q_QDOC
++ };
++
++ Q_DECLARE_ASSOCIATIVE_ITERATOR(Map)
++ Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map)
++
++ template <typename Key, typename T, typename Predicate>
++ qsizetype erase_if(QMap<Key, T> &map, Predicate pred)
++ {
++ return QtPrivate::associative_erase_if(map, pred);
++ }
++
++
++ //
++ // QMultiMap
++ //
++
++ template <class Key, class T>
++ class QMultiMap
++ {
++ using Map = std::multimap<Key, T>;
++ using MapData = QMapData<Map>;
++ QtPrivate::QExplicitlySharedDataPointerV2<MapData> d;
++
++ // Note: methods that look up a single element by key use lower_bound() rather
++ // than find(). The C++ standard permits std::multimap::find() to return any
++ // element with the matching key; libc++ 22 changed which one it returns.
++ // lower_bound() is where insert() places new elements, so it consistently
++ // identifies the most-recently-inserted one.
++
++ auto findIteratorByKey(const Key &key) const
++ {
++ auto i = d->m.lower_bound(key);
++ const auto &cmp = d->m.key_comp();
++ if (i != d->m.end() && !cmp(key, i->first))
++ return i;
++ return d->m.end();
++ }
++ auto findIteratorByKey(const Key &key)
++ {
++ auto i = d->m.lower_bound(key);
++ const auto &cmp = d->m.key_comp();
++ if (i != d->m.end() && !cmp(key, i->first))
++ return i;
++ return d->m.end();
++ }
++
++ public:
++ using key_type = Key;
++ using mapped_type = T;
++ using difference_type = qptrdiff;
++ using size_type = qsizetype;
++
++ QMultiMap() = default;
++
++ // implicitly generated special member functions are OK!
++
++ QMultiMap(std::initializer_list<std::pair<Key,T>> list)
++ {
++ for (auto &p : list)
++ insert(p.first, p.second);
++ }
++
++ void swap(QMultiMap<Key, T> &other) noexcept
++ {
++ d.swap(other.d);
++ }
++
++ explicit QMultiMap(const QMap<Key, T> &other)
++ : d(other.isEmpty() ? nullptr : new MapData)
++ {
++ if (d) {
++ Q_ASSERT(other.d);
++ d->m.insert(other.d->m.begin(),
++ other.d->m.end());
++ }
++ }
++
++ explicit QMultiMap(QMap<Key, T> &&other)
++ : d(other.isEmpty() ? nullptr : new MapData)
++ {
++ if (d) {
++ Q_ASSERT(other.d);
++ if (other.d.isShared()) {
++ d->m.insert(other.d->m.begin(),
++ other.d->m.end());
++ } else {
++ #ifdef __cpp_lib_node_extract
++ d->m.merge(std::move(other.d->m));
++ #else
++ d->m.insert(std::make_move_iterator(other.d->m.begin()),
++ std::make_move_iterator(other.d->m.end()));
++ #endif
++ }
++ }
++ }
++
++ explicit QMultiMap(const std::multimap<Key, T> &other)
++ : d(other.empty() ? nullptr : new MapData(other))
++ {
++ }
++
++ explicit QMultiMap(std::multimap<Key, T> &&other)
++ : d(other.empty() ? nullptr : new MapData(std::move(other)))
++ {
++ }
++
++ // CHANGE: return type
++ Q_DECL_DEPRECATED_X("Use toStdMultiMap instead")
++ std::multimap<Key, T> toStdMap() const
++ {
++ return toStdMultiMap();
++ }
++
++ std::multimap<Key, T> toStdMultiMap() const &
++ {
++ if (d)
++ return d->m;
++ return {};
++ }
++
++ std::multimap<Key, T> toStdMultiMap() &&
++ {
++ if (d) {
++ if (d.isShared())
++ return d->m;
++ else
++ return std::move(d->m);
++ }
++
++ return {};
++ }
++
++ #ifndef Q_QDOC
++ private:
++ template <typename AKey = Key, typename AT = T,
++ QTypeTraits::compare_eq_result_container<QMultiMap, AKey, AT> = true>
++ friend bool comparesEqual(const QMultiMap &lhs, const QMultiMap &rhs)
++ {
++ if (lhs.d == rhs.d)
++ return true;
++ if (!lhs.d)
++ return rhs == lhs;
++ Q_ASSERT(lhs.d);
++ return rhs.d ? (lhs.d->m == rhs.d->m) : lhs.d->m.empty();
++ }
++ QT_DECLARE_EQUALITY_OPERATORS_HELPER(QMultiMap, QMultiMap, /* non-constexpr */, noexcept(false),
++ template <typename AKey = Key, typename AT = T,
++ QTypeTraits::compare_eq_result_container<QMultiMap, AKey, AT> = true>)
++
++ template <typename AKey = Key, typename AT = T,
++ QtPrivate::if_map_has_relational_operators<QMultiMap, AKey, AT> = true>
++ friend auto compareThreeWay(const QMultiMap &lhs, const QMultiMap &rhs)
++ {
++ return QtOrderingPrivate::lexicographicalCompareThreeWay(lhs.constKeyValueBegin(),
++ lhs.constKeyValueEnd(),
++ rhs.constKeyValueBegin(),
++ rhs.constKeyValueEnd());
++ }
++ QT_DECLARE_ORDERING_HELPER_AUTO(QMultiMap, QMultiMap, /* non-constexpr */, noexcept(false),
++ template <typename AKey = Key, typename AT = T,
++ QtPrivate::if_map_has_relational_operators<QMultiMap, AKey, AT> = true>)
++ public:
++ #else
++ friend bool operator==(const QMultiMap &lhs, const QMultiMap &rhs);
++ friend bool operator!=(const QMultiMap &lhs, const QMultiMap &rhs);
++ friend bool operator<(const QMultiMap &lhs, const QMultiMap &rhs);
++ friend bool operator>(const QMultiMap &lhs, const QMultiMap &rhs);
++ friend bool operator<=(const QMultiMap &lhs, const QMultiMap &rhs);
++ friend bool operator>=(const QMultiMap &lhs, const QMultiMap &rhs);
++ friend auto operator<=>(const QMultiMap &lhs, const QMultiMap &rhs);
++ #endif // Q_QDOC
++
++ size_type size() const { return d ? size_type(d->m.size()) : size_type(0); }
++
++ [[nodiscard]]
++ bool isEmpty() const { return d ? d->m.empty() : true; }
++
++ void detach()
++ {
++ if (d)
++ d.detach();
++ else
++ d.reset(new MapData);
++ }
++
++ // A detach for holding an already shared copy, until calling function
++ // is done using references to keys or values that might reference it.
++ [[nodiscard]] QMultiMap referenceHoldingDetach()
++ {
++ if (!d) {
++ d.reset(new MapData);
++ } else if (d.isShared()) {
++ auto hold = *this;
++ d.detach();
++ return hold;
++ }
++ return {};
++ }
++
++ // Specialized version of referenceHoldingDetach(), which will not copy skipit, if copying
++ [[nodiscard]] QMultiMap referenceHoldingDetachExceptFor(const typename Map::iterator &skipit)
++ {
++ Q_ASSERT(d.isShared());
++ auto hold = *this;
++ QtPrivate::QExplicitlySharedDataPointerV2<MapData> newData(new MapData);
++ newData->copyExceptFor(d->m, skipit);
++ d.swap(newData);
++ return hold;
++ }
++
++ bool isDetached() const noexcept
++ {
++ return d ? !d.isShared() : false; // false makes little sense, but that's shared_null's behavior...
++ }
++
++ bool isSharedWith(const QMultiMap<Key, T> &other) const noexcept
++ {
++ return d == other.d; // also this makes little sense?
++ }
++
++ void clear()
++ {
++ if (!d)
++ return;
++
++ if (!d.isShared())
++ d->m.clear();
++ else
++ d.reset();
++ }
++
++ size_type remove(const Key &key)
++ {
++ if (!d)
++ return 0;
++
++ if (!d.isShared())
++ return size_type(d->m.erase(key));
++
++ MapData *newData = new MapData;
++ size_type result = newData->copyIfNotEquivalentTo(d->m, key).count;
++
++ d.reset(newData);
++
++ return result;
++ }
++
++ size_type remove(const Key &key, const T &value)
++ {
++ if (!d)
++ return 0;
++
++ size_type result = 0;
++ const auto &keyCompare = d->m.key_comp();
++
++ if (d.isShared()) {
++ QtPrivate::QExplicitlySharedDataPointerV2<MapData> newData(new MapData);
++ const auto keep = [&newData](auto it) { newData->m.insert(newData->m.cend(), *it); };
++
++ auto it = d->m.cbegin();
++ const auto end = d->m.cend();
++ for (; it != end && keyCompare(it->first, key); ++it)
++ keep(it);
++ // Keep matching keys if value match, otherwise skip and count
++ for (; it != end && !keyCompare(key, it->first); ++it) {
++ if (!(it->second == value))
++ keep(it);
++ else
++ ++result;
++ }
++ for (; it != end; ++it)
++ keep(it);
++
++ d.swap(newData);
++ return result;
++ }
++
++ // d->m.erase_if(....) would be nice, but that's C++20.
++ // So let's do like find(keyCopy, valueCopy):
++ auto [i, e] = d->m.equal_range(key);
++ if (i == e)
++ return result;
++
++ // value may belong to this map. As such, we need to copy it to ensure
++ // it stays valid throughout the iteration below (which may destroy it)
++ const T valueCopy = value;
++ while (i != e) {
++ if (i->second == valueCopy) {
++ i = d->m.erase(i);
++ ++result;
++ } else {
++ ++i;
++ }
++ }
++
++ return result;
++ }
++
++ template <typename Predicate>
++ size_type removeIf(Predicate pred)
++ {
++ return QtPrivate::associative_erase_if(*this, pred);
++ }
++
++ T take(const Key &key)
++ {
++ if (!d)
++ return T();
++
++ auto i = findIteratorByKey(key);
++ if (d.isShared()) {
++ if (i == d->m.end()) {
++ // NB: take always detaches, even if the key isn't found. This is for historic reasons.
++ detach();
++ return T();
++ }
++ const auto hold = referenceHoldingDetachExceptFor(i);
++ return i->second;
++ }
++
++ if (i == d->m.end())
++ return T();
++
++ #ifdef __cpp_lib_node_extract
++ return std::move(d->m.extract(i).mapped());
++ #else
++ // ### breaks RVO on most compilers (but only on old-fashioned ones, so who cares?)
++ T result(std::move(i->second));
++ d->m.erase(i);
++ return result;
++ #endif
++ }
++
++ bool contains(const Key &key) const
++ {
++ if (!d)
++ return false;
++ auto i = d->m.find(key);
++ return i != d->m.end();
++ }
++
++ bool contains(const Key &key, const T &value) const
++ {
++ return find(key, value) != end();
++ }
++
++ Key key(const T &value, const Key &defaultKey = Key()) const
++ {
++ if (!d)
++ return defaultKey;
++
++ return d->key(value, defaultKey);
++ }
++
++ T value(const Key &key, const T &defaultValue = T()) const
++ {
++ if (!d)
++ return defaultValue;
++ auto i = findIteratorByKey(key);
++ if (i != d->m.cend())
++ return i->second;
++ return defaultValue;
++ }
++
++ QList<Key> keys() const
++ {
++ if (!d)
++ return {};
++ return d->keys();
++ }
++
++ QList<Key> keys(const T &value) const
++ {
++ if (!d)
++ return {};
++ return d->keys(value);
++ }
++
++ QList<Key> uniqueKeys() const
++ {
++ QList<Key> result;
++ if (!d)
++ return result;
++
++ result.reserve(size());
++
++ std::unique_copy(keyBegin(), keyEnd(),
++ std::back_inserter(result));
++
++ result.shrink_to_fit();
++ return result;
++ }
++
++ QList<T> values() const
++ {
++ if (!d)
++ return {};
++ return d->values();
++ }
++
++ QList<T> values(const Key &key) const
++ {
++ QList<T> result;
++ const auto range = equal_range(key);
++ result.reserve(std::distance(range.first, range.second));
++ std::copy(range.first, range.second, std::back_inserter(result));
++ return result;
++ }
++
++ size_type count(const Key &key) const
++ {
++ if (!d)
++ return 0;
++ return d->count(key);
++ }
++
++ size_type count(const Key &key, const T &value) const
++ {
++ if (!d)
++ return 0;
++
++ // TODO: improve; no need of scanning the equal_range twice.
++ auto range = d->m.equal_range(key);
++
++ return size_type(std::count_if(range.first,
++ range.second,
++ MapData::valueIsEqualTo(value)));
++ }
++
++ inline const Key &firstKey() const { Q_ASSERT(!isEmpty()); return constBegin().key(); }
++ inline const Key &lastKey() const { Q_ASSERT(!isEmpty()); return std::next(constEnd(), -1).key(); }
++
++ inline T &first() { Q_ASSERT(!isEmpty()); return *begin(); }
++ inline const T &first() const { Q_ASSERT(!isEmpty()); return *constBegin(); }
++ inline T &last() { Q_ASSERT(!isEmpty()); return *std::next(end(), -1); }
++ inline const T &last() const { Q_ASSERT(!isEmpty()); return *std::next(constEnd(), -1); }
++
++ class const_iterator;
++
++ class iterator
++ {
++ friend class QMultiMap<Key, T>;
++ friend class const_iterator;
++
++ typename Map::iterator i;
++ explicit iterator(typename Map::iterator it) : i(it) {}
++ public:
++ using iterator_category = std::bidirectional_iterator_tag;
++ using difference_type = qptrdiff;
++ using value_type = T;
++ using pointer = T *;
++ using reference = T &;
++
++ iterator() = default;
++
++ const Key &key() const { return i->first; }
++ T &value() const { return i->second; }
++ T &operator*() const { return i->second; }
++ T *operator->() const { return &i->second; }
++ friend bool operator==(const iterator &lhs, const iterator &rhs) { return lhs.i == rhs.i; }
++ friend bool operator!=(const iterator &lhs, const iterator &rhs) { return lhs.i != rhs.i; }
++
++ iterator &operator++()
++ {
++ ++i;
++ return *this;
++ }
++ iterator operator++(int)
++ {
++ iterator r = *this;
++ ++i;
++ return r;
++ }
++ iterator &operator--()
++ {
++ --i;
++ return *this;
++ }
++ iterator operator--(int)
++ {
++ iterator r = *this;
++ --i;
++ return r;
++ }
++
++ #if QT_DEPRECATED_SINCE(6, 0)
++ QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMultiMap iterators are not random access")
++ //! [qmultimap-op-it-plus-step]
++ friend iterator operator+(iterator it, difference_type j) { return std::next(it, j); }
++
++ QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMultiMap iterators are not random access")
++ //! [qmultimap-op-it-minus-step]
++ friend iterator operator-(iterator it, difference_type j) { return std::prev(it, j); }
++
++ QT_DEPRECATED_VERSION_X_6_0("Use std::next or std::advance; QMultiMap iterators are not random access")
++ iterator &operator+=(difference_type j) { std::advance(*this, j); return *this; }
++
++ QT_DEPRECATED_VERSION_X_6_0("Use std::prev or std::advance; QMultiMap iterators are not random access")
++ iterator &operator-=(difference_type j) { std::advance(*this, -j); return *this; }
++
++ QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMultiMap iterators are not random access")
++ //! [qmultimap-op-step-plus-it]
++ friend iterator operator+(difference_type j, iterator it) { return std::next(it, j); }
++
++ QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMultiMap iterators are not random access")
++ //! [qmultimap-op-step-minus-it]
++ friend iterator operator-(difference_type j, iterator it) { return std::prev(it, j); }
++ #endif
++ };
++
++ class const_iterator
++ {
++ friend class QMultiMap<Key, T>;
++ typename Map::const_iterator i;
++ explicit const_iterator(typename Map::const_iterator it) : i(it) {}
++
++ public:
++ using iterator_category = std::bidirectional_iterator_tag;
++ using difference_type = qptrdiff;
++ using value_type = T;
++ using pointer = const T *;
++ using reference = const T &;
++
++ const_iterator() = default;
++ Q_IMPLICIT const_iterator(const iterator &o) : i(o.i) {}
++
++ const Key &key() const { return i->first; }
++ const T &value() const { return i->second; }
++ const T &operator*() const { return i->second; }
++ const T *operator->() const { return &i->second; }
++ friend bool operator==(const const_iterator &lhs, const const_iterator &rhs) { return lhs.i == rhs.i; }
++ friend bool operator!=(const const_iterator &lhs, const const_iterator &rhs) { return lhs.i != rhs.i; }
++
++ const_iterator &operator++()
++ {
++ ++i;
++ return *this;
++ }
++ const_iterator operator++(int)
++ {
++ const_iterator r = *this;
++ ++i;
++ return r;
++ }
++ const_iterator &operator--()
++ {
++ --i;
++ return *this;
++ }
++ const_iterator operator--(int)
++ {
++ const_iterator r = *this;
++ --i;
++ return r;
++ }
++
++ #if QT_DEPRECATED_SINCE(6, 0)
++ QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMultiMap iterators are not random access")
++ //! [qmultimap-op-it-plus-step-const]
++ friend const_iterator operator+(const_iterator it, difference_type j) { return std::next(it, j); }
++
++ QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMultiMap iterators are not random access")
++ //! [qmultimap-op-it-minus-step-const]
++ friend const_iterator operator-(const_iterator it, difference_type j) { return std::prev(it, j); }
++
++ QT_DEPRECATED_VERSION_X_6_0("Use std::next or std::advance; QMultiMap iterators are not random access")
++ const_iterator &operator+=(difference_type j) { std::advance(*this, j); return *this; }
++
++ QT_DEPRECATED_VERSION_X_6_0("Use std::prev or std::advance; QMultiMap iterators are not random access")
++ const_iterator &operator-=(difference_type j) { std::advance(*this, -j); return *this; }
++
++ QT_DEPRECATED_VERSION_X_6_0("Use std::next; QMultiMap iterators are not random access")
++ //! [qmultimap-op-step-plus-it-const]
++ friend const_iterator operator+(difference_type j, const_iterator it) { return std::next(it, j); }
++
++ QT_DEPRECATED_VERSION_X_6_0("Use std::prev; QMultiMap iterators are not random access")
++ //! [qmultimap-op-step-minus-it-const]
++ friend const_iterator operator-(difference_type j, const_iterator it) { return std::prev(it, j); }
++ #endif
++ };
++
++ class key_iterator
++ {
++ const_iterator i;
++
++ public:
++ typedef typename const_iterator::iterator_category iterator_category;
++ typedef typename const_iterator::difference_type difference_type;
++ typedef Key value_type;
++ typedef const Key *pointer;
++ typedef const Key &reference;
++
++ key_iterator() = default;
++ explicit key_iterator(const_iterator o) : i(o) { }
++
++ const Key &operator*() const { return i.key(); }
++ const Key *operator->() const { return &i.key(); }
++ bool operator==(key_iterator o) const { return i == o.i; }
++ bool operator!=(key_iterator o) const { return i != o.i; }
++
++ inline key_iterator &operator++() { ++i; return *this; }
++ inline key_iterator operator++(int) { return key_iterator(i++);}
++ inline key_iterator &operator--() { --i; return *this; }
++ inline key_iterator operator--(int) { return key_iterator(i--); }
++ const_iterator base() const { return i; }
++ };
++
++ typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator;
++ typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator;
++
++ // STL style
++ iterator begin() { detach(); return iterator(d->m.begin()); }
++ const_iterator begin() const { if (!d) return const_iterator(); return const_iterator(d->m.cbegin()); }
++ const_iterator constBegin() const { return begin(); }
++ const_iterator cbegin() const { return begin(); }
++ iterator end() { detach(); return iterator(d->m.end()); }
++ const_iterator end() const { if (!d) return const_iterator(); return const_iterator(d->m.end()); }
++ const_iterator constEnd() const { return end(); }
++ const_iterator cend() const { return end(); }
++ key_iterator keyBegin() const { return key_iterator(begin()); }
++ key_iterator keyEnd() const { return key_iterator(end()); }
++ key_value_iterator keyValueBegin() { return key_value_iterator(begin()); }
++ key_value_iterator keyValueEnd() { return key_value_iterator(end()); }
++ const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); }
++ const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); }
++ const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); }
++ const_key_value_iterator constKeyValueEnd() const { return const_key_value_iterator(end()); }
++ auto asKeyValueRange() & { return QtPrivate::QKeyValueRange<QMultiMap &>(*this); }
++ auto asKeyValueRange() const & { return QtPrivate::QKeyValueRange<const QMultiMap &>(*this); }
++ auto asKeyValueRange() && { return QtPrivate::QKeyValueRange<QMultiMap>(std::move(*this)); }
++ auto asKeyValueRange() const && { return QtPrivate::QKeyValueRange<QMultiMap>(std::move(*this)); }
++
++ iterator erase(const_iterator it)
++ {
++ return erase(it, std::next(it));
++ }
++
++ iterator erase(const_iterator afirst, const_iterator alast)
++ {
++ if (!d)
++ return iterator();
++
++ if (!d.isShared())
++ return iterator(d->m.erase(afirst.i, alast.i));
++
++ auto result = d->erase(afirst.i, alast.i);
++ d.reset(result.data);
++ return iterator(result.it);
++ }
++
++ // more Qt
++ typedef iterator Iterator;
++ typedef const_iterator ConstIterator;
++
++ size_type count() const
++ {
++ return size();
++ }
++
++ iterator find(const Key &key)
++ {
++ const auto hold = referenceHoldingDetach();
++ return iterator(findIteratorByKey(key));
++ }
++
++ const_iterator find(const Key &key) const
++ {
++ if (!d)
++ return const_iterator();
++ return const_iterator(findIteratorByKey(key));
++ }
++
++ const_iterator constFind(const Key &key) const
++ {
++ return find(key);
++ }
++
++ iterator find(const Key &key, const T &value)
++ {
++ const auto hold = referenceHoldingDetach();
++
++ auto range = d->m.equal_range(key);
++ auto i = std::find_if(range.first, range.second,
++ MapData::valueIsEqualTo(value));
++
++ if (i != range.second)
++ return iterator(i);
++ return iterator(d->m.end());
++ }
++
++ const_iterator find(const Key &key, const T &value) const
++ {
++ if (!d)
++ return const_iterator();
++
++ auto range = d->m.equal_range(key);
++ auto i = std::find_if(range.first, range.second,
++ MapData::valueIsEqualTo(value));
++
++ if (i != range.second)
++ return const_iterator(i);
++ return const_iterator(d->m.end());
++ }
++
++ const_iterator constFind(const Key &key, const T &value) const
++ {
++ return find(key, value);
++ }
++
++ iterator lowerBound(const Key &key)
++ {
++ const auto hold = referenceHoldingDetach();
++ return iterator(d->m.lower_bound(key));
++ }
++
++ const_iterator lowerBound(const Key &key) const
++ {
++ if (!d)
++ return const_iterator();
++ return const_iterator(d->m.lower_bound(key));
++ }
++
++ iterator upperBound(const Key &key)
++ {
++ const auto hold = referenceHoldingDetach();
++ return iterator(d->m.upper_bound(key));
++ }
++
++ const_iterator upperBound(const Key &key) const
++ {
++ if (!d)
++ return const_iterator();
++ return const_iterator(d->m.upper_bound(key));
++ }
++
++ iterator insert(const Key &key, const T &value)
++ {
++ const auto hold = referenceHoldingDetach();
++ // note that std::multimap inserts at the end of an equal_range for a key,
++ // QMultiMap at the beginning.
++ auto i = d->m.lower_bound(key);
++ return iterator(d->m.insert(i, {key, value}));
++ }
++
++ iterator insert(const_iterator pos, const Key &key, const T &value)
++ {
++ if (!d) {
++ d.reset(new MapData);
++ return iterator(d->m.insert({ key, value }));
++ } else if (d.isShared()) {
++ auto posDistance = std::distance(d->m.cbegin(), pos.i);
++ auto hold = referenceHoldingDetach();
++ auto dpos = std::next(d->m.cbegin(), posDistance);
++ return iterator(d->m.insert(dpos, {key, value}));
++ }
++
++ return iterator(d->m.insert(pos.i, {key, value}));
++ }
++
++ #if QT_DEPRECATED_SINCE(6, 0)
++ QT_DEPRECATED_VERSION_X_6_0("Use insert() instead")
++ iterator insertMulti(const Key &key, const T &value)
++ {
++ return insert(key, value);
++ }
++ QT_DEPRECATED_VERSION_X_6_0("Use insert() instead")
++ iterator insertMulti(const_iterator pos, const Key &key, const T &value)
++ {
++ return insert(pos, key, value);
++ }
++
++ QT_DEPRECATED_VERSION_X_6_0("Use unite() instead")
++ void insert(const QMultiMap<Key, T> &map)
++ {
++ unite(map);
++ }
++
++ QT_DEPRECATED_VERSION_X_6_0("Use unite() instead")
++ void insert(QMultiMap<Key, T> &&map)
++ {
++ unite(std::move(map));
++ }
++ #endif
++
++ iterator replace(const Key &key, const T &value)
++ {
++ if (!d) {
++ d.reset(new MapData);
++ return iterator(d->m.insert({ key, value }));
++ }
++ auto i = findIteratorByKey(key);
++ if (d.isShared()) {
++ const auto hold = referenceHoldingDetachExceptFor(i);
++ return iterator(d->m.insert({ key, value }));
++ }
++
++ // Similarly, improve here (e.g. lower_bound and hinted insert);
++ // there's no insert_or_assign on multimaps
++ if (i != d->m.end())
++ i->second = value;
++ else
++ i = d->m.insert({key, value});
++
++ return iterator(i);
++ }
++
++ // STL compatibility
++ [[nodiscard]]
++ inline bool empty() const { return isEmpty(); }
++
++ std::pair<iterator, iterator> equal_range(const Key &akey)
++ {
++ const auto hold = referenceHoldingDetach();
++ auto result = d->m.equal_range(akey);
++ return {iterator(result.first), iterator(result.second)};
++ }
++
++ std::pair<const_iterator, const_iterator> equal_range(const Key &akey) const
++ {
++ if (!d)
++ return {};
++ auto result = d->m.equal_range(akey);
++ return {const_iterator(result.first), const_iterator(result.second)};
++ }
++
++ QMultiMap &unite(const QMultiMap &other)
++ {
++ if (other.isEmpty())
++ return *this;
++
++ detach();
++
++ auto copy = other.d->m;
++ #ifdef __cpp_lib_node_extract
++ copy.merge(std::move(d->m));
++ #else
++ copy.insert(std::make_move_iterator(d->m.begin()),
++ std::make_move_iterator(d->m.end()));
++ #endif
++ d->m = std::move(copy);
++ return *this;
++ }
++
++ QMultiMap &unite(QMultiMap<Key, T> &&other)
++ {
++ if (!other.d || other.d->m.empty())
++ return *this;
++
++ if (other.d.isShared()) {
++ // fall back to a regular copy
++ unite(other);
++ return *this;
++ }
++
++ detach();
++
++ #ifdef __cpp_lib_node_extract
++ other.d->m.merge(std::move(d->m));
++ #else
++ other.d->m.insert(std::make_move_iterator(d->m.begin()),
++ std::make_move_iterator(d->m.end()));
++ #endif
++ *this = std::move(other);
++ return *this;
++ }
++ };
++
++ Q_DECLARE_ASSOCIATIVE_ITERATOR(MultiMap)
++ Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(MultiMap)
++
++ template <typename Key, typename T>
++ QMultiMap<Key, T> operator+(const QMultiMap<Key, T> &lhs, const QMultiMap<Key, T> &rhs)
++ {
++ auto result = lhs;
++ result += rhs;
++ return result;
++ }
++
++ template <typename Key, typename T>
++ QMultiMap<Key, T> operator+=(QMultiMap<Key, T> &lhs, const QMultiMap<Key, T> &rhs)
++ {
++ return lhs.unite(rhs);
++ }
++
++ template <typename Key, typename T, typename Predicate>
++ qsizetype erase_if(QMultiMap<Key, T> &map, Predicate pred)
++ {
++ return QtPrivate::associative_erase_if(map, pred);
++ }
++
++ QT_END_NAMESPACE
++
++ #endif // QMAP_H