// 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