EIC code displayed by LXR master/​include/​QtCore/​qmap.h	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2026-10-31 09:40:53

 // 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))
     {}
 
     // used in remove(); copies from source all the values not matching key.
     // returns how many were NOT copied (removed).
     size_type copyIfNotEquivalentTo(const Map &source, const Key &key)
     {
         Q_ASSERT(m.empty());
 
         size_type result = 0;
 
         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)
             ++result;
         // Keep all after:
         for (; it != end; ++it)
             keep(it);
 
         return result;
     }
 
     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;
     }
 };
 
 //
 // 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>)
     // TODO: add the other comparison operators; std::map has them.
 public:
 #else
     friend bool operator==(const QMap &lhs, const QMap &rhs);
     friend bool 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.
     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
     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);
 
         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()) {
             Map m;
             // For historic reasons, we always un-share (was: detach()) when
             // this function is called, even if `key` isn't found
             const auto commit = qScopeGuard([&] { QMap{std::move(m)}.swap(*this); });
 
             // This way of copying ought to be O(N) (not NlogN) and not causing
             // any rebalancings in `m`, because we build in-order and with hint
             // [[citation needed]].
 
             const auto keep = [&m] (auto it) { m.insert(m.cend(), *it); };
 
             auto it = d->m.cbegin();
             const auto end = d->m.cend();
             const auto cmp = d->m.key_comp();
             while (it != end) {
                 if (cmp(it->first, key)) { // still before
                     keep(it);
                     ++it;
                 } else if (cmp(key, it->first)) { // after, iow: not found
                     // This should be faster than an actual range-insert, because
                     // the latter cannot assume that the input is sorted; we can:
                     while (it != end) {
                         keep(it);
                         ++it;
                     }
                     break;
                 } else { // found!
                     return [&] {
                         T r = it->second; // we cannot move (isShared()!)
                         while (++it != end)
                             keep(it);
                         return r;
                     }();
                 }
             }
             // 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>)
     // TODO: add the other comparison operators; std::multimap has them.
 public:
 #else
     friend bool operator==(const QMultiMap &lhs, const QMultiMap &rhs);
     friend bool 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);
 
         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 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

This page was automatically generated by the 2.3.7 LXR engine. The LXR team