Long Live QMap as a refcounted std::map!

... and QMultiMap as std::multimap.

Just use the implementation from the STL; we can't really claim that
our code is much better than STL's, or does things any differently
(de facto they're both red-black trees).

Decouple QMultiMap from QMap, by making it NOT inherit from
QMap any longer. This completes the deprecation started in 5.15:
QMap now does not store duplicated keys any more.

Something to establish is where to put the
QExplictlySharedDataPointer replcement that is in there as an
ad-hoc solution. There's a number of patches in-flight by Marc
that try to introduce the same (or very similar) functionality.

Miscellanea changes to the Q(Multi)Map code itself:

* consistently use size_type instead of int;
* pass iterators by value;
* drop QT_STRICT_ITERATORS;
* iterators implictly convert to const_iterators, and APIs
  take const_iterators;
* iterators are just bidirectional and not random access;
* added noexcept where it makes sense;
* "inline" dropped (churn);
* qMapLessThanKey dropped (undocumented, 0 hits in Qt, 1 hit in KDE);
* operator== on Q(Multi)Map requires operator== on the key type
  (we're checking for equality, not equivalence!).

Very few breakages occur in qtbase.

[ChangeLog][Potentially Source-Incompatible Changes] QMap does not
support multiple equivalent keys any more. Any related functionality
has been removed from QMap, following the deprecation that happened
in Qt 5.15. Use QMultiMap for this use case.

[ChangeLog][Potentially Source-Incompatible Changes] QMap and
QMultiMap iterators random-access API have been removed. Note that
the iterators have always been just bidirectional; moving
an iterator by N positions can still be achieved using std::next
or std::advance, at the same cost as before (O(N)).

[ChangeLog][Potentially Source-Incompatible Changes] QMultiMap does
not inherit from QMap any more. Amongst other things, this means
that iterators on a QMultiMap now belong to the QMultiMap class
(and not to the QMap class); new Java iterators have been added.

Change-Id: I5a0fe9b020f92c21b37065a1defff783b5d2b7a9
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
Reviewed-by: Lars Knoll <lars.knoll@qt.io>

10 files changed, 3224 insertions, 1966 deletions

diff --git a/src/corelib/CMakeLists.txt b/src/corelib/CMakeLists.txt
index fda150251c..0702c32170 100644
--- a/src/corelib/CMakeLists.txt
+++ b/src/corelib/CMakeLists.txt
@@ -213,7 +213,7 @@ qt_add_module(Core
         tools/qline.cpp tools/qline.h
         tools/qlist.cpp tools/qlist.h
         tools/qmakearray_p.h
-        tools/qmap.cpp tools/qmap.h
+        tools/qmap.h
         tools/qmargins.cpp tools/qmargins.h
         tools/qmessageauthenticationcode.cpp tools/qmessageauthenticationcode.h
         tools/qoffsetstringarray_p.h
diff --git a/src/corelib/doc/snippets/code/doc_src_qiterator.cpp b/src/corelib/doc/snippets/code/doc_src_qiterator.cpp
index ed0cf9e329..2ee618d394 100644
--- a/src/corelib/doc/snippets/code/doc_src_qiterator.cpp
+++ b/src/corelib/doc/snippets/code/doc_src_qiterator.cpp
@@ -183,6 +183,35 @@ while (i.findNext(widget)) {
 }
 //! [28]
 
+//! [26multi]
+QMultiMap<int, QWidget *> multimap;
+...
+QMultiMapIterator<int, QWidget *> i(multimap);
+while (i.hasNext()) {
+    i.next();
+    qDebug() << i.key() << ": " << i.value();
+}
+//! [26multi]
+
+
+//! [27multi]
+QMultiMapIterator<int, QWidget *> i(multimap);
+i.toBack();
+while (i.hasPrevious()) {
+    i.previous();
+    qDebug() << i.key() << ": " << i.value();
+}
+//! [27multi]
+
+
+//! [28multi]
+QMultiMapIterator<int, QWidget *> i(multimap);
+while (i.findNext(widget)) {
+    qDebug() << "Found widget " << widget << " under key "
+             << i.key();
+}
+//! [28multi]
+
 
 //! [29]
 QHash<int, QWidget *> hash;
@@ -244,6 +273,46 @@ while (i.hasNext()) {
 //! [35]
 
 
+//! [32multi]
+QMultiMap<int, QWidget *> multimap;
+...
+QMutableMultiMapIterator<int, QWidget *> i(multimap);
+while (i.hasNext()) {
+    i.next();
+    qDebug() << i.key() << ": " << i.value();
+}
+//! [32multi]
+
+
+//! [33multi]
+QMutableMultiMapIterator<int, QWidget *> i(multimap);
+i.toBack();
+while (i.hasPrevious()) {
+    i.previous();
+    qDebug() << i.key() << ": " << i.value();
+}
+//! [33multi]
+
+
+//! [34multi]
+QMutableMultiMapIterator<int, QWidget *> i(multimap);
+while (i.findNext(widget)) {
+    qDebug() << "Found widget " << widget << " under key "
+             << i.key();
+}
+//! [34multi]
+
+
+//! [35multi]
+QMutableMultiMapIterator<QString, QString> i(multimap);
+while (i.hasNext()) {
+    i.next();
+    if (i.key() == i.value())
+        i.remove();
+}
+//! [35multi]
+
+
 //! [36]
 QHash<int, QWidget *> hash;
 ...
diff --git a/src/corelib/doc/snippets/code/src_corelib_tools_qmultimap.cpp b/src/corelib/doc/snippets/code/src_corelib_tools_qmultimap.cpp
new file mode 100644
index 0000000000..9c2a01834b
--- /dev/null
+++ b/src/corelib/doc/snippets/code/src_corelib_tools_qmultimap.cpp
@@ -0,0 +1,324 @@
+/****************************************************************************
+**
+** Copyright (C) 2020 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
+** Copyright (C) 2016 The Qt Company Ltd.
+** Contact: https://www.qt.io/licensing/
+**
+** This file is part of the documentation of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:BSD$
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and The Qt Company. For licensing terms
+** and conditions see https://www.qt.io/terms-conditions. For further
+** information use the contact form at https://www.qt.io/contact-us.
+**
+** BSD License Usage
+** Alternatively, you may use this file under the terms of the BSD license
+** as follows:
+**
+** "Redistribution and use in source and binary forms, with or without
+** modification, are permitted provided that the following conditions are
+** met:
+**   * Redistributions of source code must retain the above copyright
+**     notice, this list of conditions and the following disclaimer.
+**   * Redistributions in binary form must reproduce the above copyright
+**     notice, this list of conditions and the following disclaimer in
+**     the documentation and/or other materials provided with the
+**     distribution.
+**   * Neither the name of The Qt Company Ltd nor the names of its
+**     contributors may be used to endorse or promote products derived
+**     from this software without specific prior written permission.
+**
+**
+** THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+** "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+** LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+** A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+** OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+** SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+** LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+** DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+** THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+** (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+** OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE."
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+//! [0]
+QMultiMap<QString, int> multimap;
+//! [0]
+
+
+//! [2]
+multimap.insert("a", 1);
+multimap.insert("b", 3);
+multimap.insert("c", 7);
+multimap.insert("c", -5);
+//! [2]
+
+
+//! [3]
+int num2 = multimap.value("a"); // 1
+int num3 = multimap.value("thirteen"); // not found; 0
+int num3 = 0;
+auto it = multimap.value("b");
+if (it != multimap.end()) {
+    num3 = it.value();
+}
+//! [3]
+
+
+//! [4]
+int timeout = 30;
+if (multimap.contains("TIMEOUT"))
+    timeout = multimap.value("TIMEOUT");
+
+// better:
+auto it = multimap.find("TIMEOUT");
+if (it != multimap.end())
+    timeout = it.value();
+//! [4]
+
+
+//! [5]
+int timeout = multimap.value("TIMEOUT", 30);
+//! [5]
+
+
+//! [7]
+QMultiMapIterator<QString, int> i(multimap);
+while (i.hasNext()) {
+    i.next();
+    cout << i.key() << ": " << i.value() << Qt::endl;
+}
+//! [7]
+
+
+//! [8]
+auto i = multimap.constBegin();
+while (i != multimap.constEnd()) {
+    cout << i.key() << ": " << i.value() << Qt::endl;
+    ++i;
+}
+//! [8]
+
+
+//! [9]
+multimap.insert("plenty", 100);
+multimap.insert("plenty", 2000);
+// multimap.size() == 2
+//! [9]
+
+
+//! [10]
+QList<int> values = multimap.values("plenty");
+for (int i = 0; i < values.size(); ++i)
+    cout << values.at(i) << Qt::endl;
+//! [10]
+
+
+//! [11]
+QMultiMap<QString, int>::iterator i = multimap.find("plenty");
+while (i != map.end() && i.key() == "plenty") {
+    cout << i.value() << Qt::endl;
+    ++i;
+}
+
+// better:
+auto [i, end] = multimap.equal_range("plenty");
+while (i != end) {
+    cout << i.value() << Qt::endl;
+    ++i;
+}
+//! [11]
+
+
+//! [12]
+QMap<QString, int> multimap;
+...
+foreach (int value, multimap)
+    cout << value << Qt::endl;
+//! [12]
+
+
+//! [13]
+#ifndef EMPLOYEE_H
+#define EMPLOYEE_H
+
+class Employee
+{
+public:
+    Employee() {}
+    Employee(const QString &name, QDate dateOfBirth);
+    ...
+
+private:
+    QString myName;
+    QDate myDateOfBirth;
+};
+
+inline bool operator<(const Employee &e1, const Employee &e2)
+{
+    if (e1.name() != e2.name())
+        return e1.name() < e2.name();
+    return e1.dateOfBirth() < e2.dateOfBirth();
+}
+
+#endif // EMPLOYEE_H
+//! [13]
+
+
+//! [15]
+QMultiMap<int, QString> multimap;
+multimap.insert(1, "one");
+multimap.insert(5, "five");
+multimap.insert(5, "five (2)");
+multimap.insert(10, "ten");
+
+multimap.lowerBound(0);      // returns iterator to (1, "one")
+multimap.lowerBound(1);      // returns iterator to (1, "one")
+multimap.lowerBound(2);      // returns iterator to (5, "five")
+multimap.lowerBound(5);      // returns iterator to (5, "five")
+multimap.lowerBound(6);      // returns iterator to (10, "ten")
+multimap.lowerBound(10);     // returns iterator to (10, "ten")
+multimap.lowerBound(999);    // returns end()
+//! [15]
+
+
+//! [16]
+QMap<QString, int> multimap;
+...
+QMap<QString, int>::const_iterator i = multimap.lowerBound("HDR");
+QMap<QString, int>::const_iterator upperBound = multimap.upperBound("HDR");
+while (i != upperBound) {
+    cout << i.value() << Qt::endl;
+    ++i;
+}
+//! [16]
+
+
+//! [17]
+QMultiMap<int, QString> multimap;
+multimap.insert(1, "one");
+multimap.insert(5, "five");
+multimap.insert(5, "five (2)");
+multimap.insert(10, "ten");
+
+multimap.upperBound(0);      // returns iterator to (1, "one")
+multimap.upperBound(1);      // returns iterator to (5, "five")
+multimap.upperBound(2);      // returns iterator to (5, "five")
+multimap.lowerBound(5);      // returns iterator to (5, "five (2)")
+multimap.lowerBound(6);      // returns iterator to (10, "ten")
+multimap.upperBound(10);     // returns end()
+multimap.upperBound(999);    // returns end()
+//! [17]
+
+
+//! [18]
+QMultiMap<QString, int> multimap;
+multimap.insert("January", 1);
+multimap.insert("February", 2);
+...
+multimap.insert("December", 12);
+
+QMap<QString, int>::iterator i;
+for (i = multimap.begin(); i != multimap.end(); ++i)
+    cout << i.key() << ": " << i.value() << Qt::endl;
+//! [18]
+
+
+//! [19]
+QMultiMap<QString, int>::iterator i;
+for (i = multimap.begin(); i != multimap.end(); ++i)
+    i.value() += 2;
+//! [19]
+
+
+//! [20]
+QMultiMap<QString, int>::iterator i = multimap.begin();
+while (i != multimap.end()) {
+    if (i.key().startsWith('_'))
+        i = multimap.erase(i);
+    else
+        ++i;
+}
+//! [20]
+
+
+//! [21]
+QMultiMap<QString, int>::iterator i = multimap.begin();
+while (i != multimap.end()) {
+    QMap<QString, int>::iterator prev = i;
+    ++i;
+    if (prev.key().startsWith('_'))
+        multimap.erase(prev);
+}
+//! [21]
+
+
+//! [22]
+// WRONG
+while (i != multimap.end()) {
+    if (i.key().startsWith('_'))
+        multimap.erase(i);
+    ++i;
+}
+//! [22]
+
+
+//! [23]
+if (i.key() == "Hello")
+    i.value() = "Bonjour";
+//! [23]
+
+
+//! [24]
+QMultiMap<QString, int> multi;
+multimap.insert("January", 1);
+multimap.insert("February", 2);
+...
+multimap.insert("December", 12);
+
+QMultiMap<QString, int>::const_iterator i;
+for (i = multimap.constBegin(); i != multimap.constEnd(); ++i)
+    cout << i.key() << ": " << i.value() << Qt::endl;
+//! [24]
+
+
+//! [25]
+QMultiMap<QString, int> map1, map2, map3;
+
+map1.insert("plenty", 100);
+map1.insert("plenty", 2000);
+// map1.size() == 2
+
+map2.insert("plenty", 5000);
+// map2.size() == 1
+
+map3 = map1 + map2;
+// map3.size() == 3
+//! [25]
+
+//! [keyiterator1]
+for (QMultiMap<int, QString>::const_iterator it = multimap.cbegin(), end = multimap.cend(); it != end; ++it) {
+    cout << "The key: " << it.key() << Qt::endl
+    cout << "The value: " << it.value() << Qt::endl;
+    cout << "Also the value: " << (*it) << Qt::endl;
+}
+//! [keyiterator1]
+
+//! [keyiterator2]
+// Inefficient, keys() is expensive
+QList<int> keys = multimap.keys();
+int numPrimes = std::count_if(multimap.cbegin(), multimap.cend(), isPrimeNumber);
+qDeleteAll(multimap2.keys());
+
+// Efficient, no memory allocation needed
+int numPrimes = std::count_if(multimap.keyBegin(), multimap.keyEnd(), isPrimeNumber);
+qDeleteAll(multimap2.keyBegin(), multimap2.keyEnd());
+//! [keyiterator2]
diff --git a/src/corelib/kernel/qvariant.cpp b/src/corelib/kernel/qvariant.cpp
index 8a34806c60..f8859ddedc 100644
--- a/src/corelib/kernel/qvariant.cpp
+++ b/src/corelib/kernel/qvariant.cpp
@@ -924,7 +924,7 @@ static bool convert(const QVariant::Private *d, int t, void *result, bool *ok)
             const QVariantHash *hash = v_cast<QVariantHash>(d);
             const auto end = hash->end();
             for (auto it = hash->begin(); it != end; ++it)
-                static_cast<QMultiMap<QString, QVariant> *>(map)->insert(it.key(), it.value());
+                map->insert(it.key(), it.value());
 #ifndef QT_BOOTSTRAPPED
         } else if (d->type().id() == QMetaType::QCborValue) {
             if (!v_cast<QCborValue>(d)->isMap())
diff --git a/src/corelib/kernel/qvariant.h b/src/corelib/kernel/qvariant.h
index 87fb16485f..e7b64c2aed 100644
--- a/src/corelib/kernel/qvariant.h
+++ b/src/corelib/kernel/qvariant.h
@@ -808,7 +808,7 @@ namespace QtPrivate {
                 QAssociativeIterable iter = QVariantValueHelperInterface<QAssociativeIterable>::invoke(v);
                 QVariantMap l;
                 for (QAssociativeIterable::const_iterator it = iter.begin(), end = iter.end(); it != end; ++it)
-                    static_cast<QMultiMap<QString, QVariant> &>(l).insert(it.key().toString(), it.value());
+                    l.insert(it.key().toString(), it.value());
                 return l;
             }
             return QVariantValueHelper<QVariantMap>::invoke(v);
diff --git a/src/corelib/tools/qiterator.qdoc b/src/corelib/tools/qiterator.qdoc
index 4b61ae7778..49ee9ef00c 100644
--- a/src/corelib/tools/qiterator.qdoc
+++ b/src/corelib/tools/qiterator.qdoc
@@ -709,15 +709,15 @@
     \class QMapIterator
     \inmodule QtCore
 
-    \brief The QMapIterator class provides a Java-style const iterator for QMap and QMultiMap.
+    \brief The QMapIterator class provides a Java-style const iterator for QMap.
 
     QMap has both \l{Java-style iterators} and \l{STL-style
     iterators}. The Java-style iterators are more high-level and
     easier to use than the STL-style iterators; on the other hand,
     they are slightly less efficient.
 
-    QMapIterator\<Key, T\> allows you to iterate over a QMap (or a
-    QMultiMap). If you want to modify the map as you iterate over
+    QMapIterator\<Key, T\> allows you to iterate over a QMap.
+    If you want to modify the map as you iterate over
     it, use QMutableMapIterator instead.
 
     The QMapIterator constructor takes a QMap as argument. After
@@ -758,6 +758,57 @@
 */
 
 /*!
+    \class QMultiMapIterator
+    \inmodule QtCore
+
+    \brief The QMultiMapIterator class provides a Java-style const iterator for QMultiMap.
+    QMultiMap has both \l{Java-style iterators} and \l{STL-style
+    iterators}. The Java-style iterators are more high-level and
+    easier to use than the STL-style iterators; on the other hand,
+    they are slightly less efficient.
+
+    QMultiMapIterator\<Key, T\> allows you to iterate over a QMultiMap.
+    If you want to modify the map as you iterate over
+    it, use QMutableMultiMapIterator instead.
+
+    The QMultiMapIterator constructor takes a QMultiMap as argument. After
+    construction, the iterator is located at the very beginning of
+    the map (before the first item). Here's how to iterate over all
+    the elements sequentially:
+
+    \snippet code/doc_src_qiterator.cpp 26multi
+
+    The next() function returns the next item in the map and
+    advances the iterator. The key() and value() functions return the
+    key and value of the last item that was jumped over.
+
+    Unlike STL-style iterators, Java-style iterators point \e between
+    items rather than directly \e at items. The first call to next()
+    advances the iterator to the position between the first and
+    second item, and returns the first item; the second call to
+    next() advances the iterator to the position between the second
+    and third item; and so on.
+
+    \image javaiterators1.png
+
+    Here's how to iterate over the elements in reverse order:
+
+    \snippet code/doc_src_qiterator.cpp 27multi
+
+    If you want to find all occurrences of a particular value, use
+    findNext() or findPrevious() in a loop. For example:
+
+    \snippet code/doc_src_qiterator.cpp 28multi
+
+    Multiple iterators can be used on the same map. If the map is
+    modified while a QMultiMapIterator is active, the QMultiMapIterator will
+    continue iterating over the original map, ignoring the modified
+    copy.
+
+    \sa QMutableMultiMapIterator, QMultiMapIterator::const_iterator
+*/
+
+/*!
     \class QHashIterator
     \inmodule QtCore
 
@@ -809,7 +860,7 @@
     \class QMutableMapIterator
     \inmodule QtCore
 
-    \brief The QMutableMapIterator class provides a Java-style non-const iterator for QMap and QMultiMap.
+    \brief The QMutableMapIterator class provides a Java-style non-const iterator for QMap.
 
     QMap has both \l{Java-style iterators} and \l{STL-style
     iterators}. The Java-style iterators are more high-level and
@@ -817,7 +868,7 @@
     they are slightly less efficient.
 
     QMutableMapIterator\<Key, T\> allows you to iterate over a QMap
-    (or a QMultiMap) and modify the map. If you don't want to modify
+    and modify the map. If you don't want to modify
     the map (or have a const QMap), use the slightly faster
     QMapIterator instead.
 
@@ -871,6 +922,71 @@
 */
 
 /*!
+    \class QMutableMultiMapIterator
+    \inmodule QtCore
+
+    \brief The QMutableMultiMapIterator class provides a Java-style non-const iterator for QMultiMap.
+
+    QMultiMap has both \l{Java-style iterators} and \l{STL-style
+    iterators}. The Java-style iterators are more high-level and
+    easier to use than the STL-style iterators; on the other hand,
+    they are slightly less efficient.
+
+    QMutableMultiMapIterator\<Key, T\> allows you to iterate over a QMultiMap
+    and modify the map. If you don't want to modify
+    the map (or have a const QMultiMap), use the slightly faster
+    QMultiMapIterator instead.
+
+    The QMutableMultiMapIterator constructor takes a QMultiMap as argument.
+    After construction, the iterator is located at the very beginning
+    of the map (before the first item). Here's how to iterate over
+    all the elements sequentially:
+
+    \snippet code/doc_src_qiterator.cpp 32multi
+
+    The next() function returns the next item in the map and
+    advances the iterator. The key() and value() functions return the
+    key and value of the last item that was jumped over.
+
+    Unlike STL-style iterators, Java-style iterators point \e between
+    items rather than directly \e at items. The first call to next()
+    advances the iterator to the position between the first and
+    second item, and returns the first item; the second call to
+    next() advances the iterator to the position between the second
+    and third item; and so on.
+
+    \image javaiterators1.png
+
+    Here's how to iterate over the elements in reverse order:
+
+    \snippet code/doc_src_qiterator.cpp 33multi
+
+    If you want to find all occurrences of a particular value, use
+    findNext() or findPrevious() in a loop. For example:
+
+    \snippet code/doc_src_qiterator.cpp 34multi
+
+    If you want to remove items as you iterate over the map, use
+    remove(). If you want to modify the value of an item, use
+    setValue().
+
+    Example:
+
+    \snippet code/doc_src_qiterator.cpp 35multi
+
+    The example removes all (key, value) pairs where the key and the
+    value are the same.
+
+    Only one mutable iterator can be active on a given map at any
+    time. Furthermore, no changes should be done directly to the map
+    while the iterator is active (as opposed to through the
+    iterator), since this could invalidate the iterator and lead to
+    undefined behavior.
+
+    \sa QMultiMapIterator, QMultiMap::iterator
+*/
+
+/*!
     \class QMutableHashIterator
     \inmodule QtCore
 
@@ -933,6 +1049,8 @@
 
 /*! \fn template <class Key, class T> QMapIterator<Key, T>::QMapIterator(const QMap<Key, T> &map)
     \fn template <class Key, class T> QMutableMapIterator<Key, T>::QMutableMapIterator(QMap<Key, T> &map)
+    \fn template <class Key, class T> QMultiMapIterator<Key, T>::QMultiMapIterator(const QMultiMap<Key, T> &map)
+    \fn template <class Key, class T> QMutableMultiMapIterator<Key, T>::QMutableMultiMapIterator(QMultiMap<Key, T> &map)
 
     Constructs an iterator for traversing \a map. The iterator is set
     to be at the front of the map (before the first item).
@@ -951,6 +1069,8 @@
 
 /*! \fn template <class Key, class T> QMapIterator &QMapIterator<Key, T>::operator=(const QMap<Key, T> &map)
     \fn template <class Key, class T> QMutableMapIterator &QMutableMapIterator<Key, T>::operator=(QMap<Key, T> &map)
+    \fn template <class Key, class T> QMultiMapIterator &QMultiMapIterator<Key, T>::operator=(const QMultiMap<Key, T> &map)
+    \fn template <class Key, class T> QMutableMultiMapIterator &QMutableMultiMapIterator<Key, T>::operator=(QMultiMap<Key, T> &map)
 
     Makes the iterator operate on \a map. The iterator is set to be
     at the front of the map (before the first item).
@@ -968,8 +1088,10 @@
 */
 
 /*! \fn template <class Key, class T> void QMapIterator<Key, T>::toFront()
+    \fn template <class Key, class T> void QMultiMapIterator<Key, T>::toFront()
     \fn template <class Key, class T> void QHashIterator<Key, T>::toFront()
     \fn template <class Key, class T> void QMutableMapIterator<Key, T>::toFront()
+    \fn template <class Key, class T> void QMutableMultiMapIterator<Key, T>::toFront()
     \fn template <class Key, class T> void QMutableHashIterator<Key, T>::toFront()
 
     Moves the iterator to the front of the container (before the
@@ -979,7 +1101,9 @@
 */
 
 /*! \fn template <class Key, class T> void QMapIterator<Key, T>::toBack()
+    \fn template <class Key, class T> void QMultiMapIterator<Key, T>::toBack()
     \fn template <class Key, class T> void QMutableMapIterator<Key, T>::toBack()
+    \fn template <class Key, class T> void QMutableMultiMapIterator<Key, T>::toBack()
 
     Moves the iterator to the back of the container (after the last
     item).
@@ -998,7 +1122,9 @@
 */
 
 /*! \fn template <class Key, class T> bool QMapIterator<Key, T>::hasNext() const
+    \fn template <class Key, class T> bool QMultiMapIterator<Key, T>::hasNext() const
     \fn template <class Key, class T> bool QMutableMapIterator<Key, T>::hasNext() const
+    \fn template <class Key, class T> bool QMutableMultiMapIterator<Key, T>::hasNext() const
 
     Returns \c true if there is at least one item ahead of the iterator,
     i.e. the iterator is \e not at the back of the container;
@@ -1019,6 +1145,7 @@
 */
 
 /*! \fn template <class Key, class T> QMapIterator<Key, T>::Item QMapIterator<Key, T>::next()
+    \fn template <class Key, class T> QMultiMapIterator<Key, T>::Item QMultiMapIterator<Key, T>::next()
 
     Returns the next item and advances the iterator by one position.
 
@@ -1032,6 +1159,7 @@
 */
 
 /*! \fn template <class Key, class T> QMutableMapIterator<Key, T>::Item QMutableMapIterator<Key, T>::next()
+    \fn template <class Key, class T> QMutableMultiMapIterator<Key, T>::Item QMutableMultiMapIterator<Key, T>::next()
 
     Returns the next item and advances the iterator by one position.
 
@@ -1073,6 +1201,7 @@
 */
 
 /*! \fn template <class Key, class T> QMapIterator<Key, T>::Item QMapIterator<Key, T>::peekNext() const
+    \fn template <class Key, class T> QMutableMapIterator<Key, T>::Item QMutableMapIterator<Key, T>::peekNext()
 
     Returns the next item without moving the iterator.
 
@@ -1086,6 +1215,7 @@
 */
 
 /*! \fn template <class Key, class T> QMutableMapIterator<Key, T>::Item QMutableMapIterator<Key, T>::peekNext() const
+    \fn template <class Key, class T> QMutableMultiMapIterator<Key, T>::Item QMutableMultiMapIterator<Key, T>::peekNext()
 
     Returns a reference to the next item without moving the iterator.
 
@@ -1127,7 +1257,9 @@
 */
 
 /*! \fn template <class Key, class T> bool QMapIterator<Key, T>::hasPrevious() const
+    \fn template <class Key, class T> bool QMultiMapIterator<Key, T>::hasPrevious() const
     \fn template <class Key, class T> bool QMutableMapIterator<Key, T>::hasPrevious() const
+    \fn template <class Key, class T> bool QMutableMultiMapIterator<Key, T>::hasPrevious() const
 
     Returns \c true if there is at least one item behind the iterator,
     i.e. the iterator is \e not at the front of the container;
@@ -1160,6 +1292,8 @@
 
 /*! \fn template <class Key, class T> QMapIterator<Key, T>::Item QMapIterator<Key, T>::previous()
     \fn template <class Key, class T> QMutableMapIterator<Key, T>::Item QMutableMapIterator<Key, T>::previous()
+    \fn template <class Key, class T> QMultiMapIterator<Key, T>::Item QMultiMapIterator<Key, T>::previous()
+    \fn template <class Key, class T> QMutableMultiMapIterator<Key, T>::Item QMutableMultiMapIterator<Key, T>::previous()
 
     Returns the previous item and moves the iterator back by one
     position.
@@ -1207,6 +1341,8 @@
 
 /*! \fn template <class Key, class T> QMapIterator<Key, T>::Item QMapIterator<Key, T>::peekPrevious() const
     \fn template <class Key, class T> QMutableMapIterator<Key, T>::Item QMutableMapIterator<Key, T>::peekPrevious() const
+    \fn template <class Key, class T> QMultiMapIterator<Key, T>::Item QMultiMapIterator<Key, T>::peekPrevious() const
+    \fn template <class Key, class T> QMutableMultiMapIterator<Key, T>::Item QMutableMultiMapIterator<Key, T>::peekPrevious() const
 
     Returns the previous item without moving the iterator.
 
@@ -1250,6 +1386,7 @@
 */
 
 /*! \fn template <class Key, class T> const T &QMapIterator<Key, T>::value() const
+    \fn template <class Key, class T> const T &QMultiMapIterator<Key, T>::value() const
 
     Returns the value of the last item that was jumped over using one
     of the traversal functions (next(), previous(), findNext(),
@@ -1264,6 +1401,7 @@
 
 /*!
     \fn template <class Key, class T> const T &QMutableMapIterator<Key, T>::value() const
+    \fn template <class Key, class T> const T &QMutableMultiMapIterator<Key, T>::value() const
 
     Returns the value of the last item that was jumped over using one
     of the traversal functions (next(), previous(), findNext(),
@@ -1295,6 +1433,7 @@
 
 /*!
     \fn template <class Key, class T> T &QMutableMapIterator<Key, T>::value()
+    \fn template <class Key, class T> T &QMutableMultiMapIterator<Key, T>::value()
     \fn template <class Key, class T> T &QMutableHashIterator<Key, T>::value()
     \overload
 
@@ -1305,6 +1444,8 @@
 
 /*! \fn template <class Key, class T> const Key &QMapIterator<Key, T>::key() const
     \fn template <class Key, class T> const Key &QMutableMapIterator<Key, T>::key() const
+    \fn template <class Key, class T> const Key &QMultiMapIterator<Key, T>::key() const
+    \fn template <class Key, class T> const Key &QMutableMultiMapIterator<Key, T>::key() const
 
     Returns the key of the last item that was jumped over using one
     of the traversal functions (next(), previous(), findNext(),
@@ -1328,6 +1469,8 @@
 
 /*! \fn template <class Key, class T> bool QMapIterator<Key, T>::findNext(const T &value)
     \fn template <class Key, class T> bool QMutableMapIterator<Key, T>::findNext(const T &value)
+    \fn template <class Key, class T> bool QMultiMapIterator<Key, T>::findNext(const T &value)
+    \fn template <class Key, class T> bool QMutableMultiMapIterator<Key, T>::findNext(const T &value)
 
     Searches for \a value starting from the current iterator position
     forward. Returns \c true if a (key, value) pair with value \a value
@@ -1354,6 +1497,8 @@
 
 /*! \fn template <class Key, class T> bool QMapIterator<Key, T>::findPrevious(const T &value)
     \fn template <class Key, class T> bool QMutableMapIterator<Key, T>::findPrevious(const T &value)
+    \fn template <class Key, class T> bool QMultiMapIterator<Key, T>::findPrevious(const T &value)
+    \fn template <class Key, class T> bool QMutableMultiMapIterator<Key, T>::findPrevious(const T &value)
 
     Searches for \a value starting from the current iterator position
     backward. Returns \c true if a (key, value) pair with value \a value
@@ -1397,6 +1542,7 @@
 */
 
 /*! \fn template <class Key, class T> void QMutableMapIterator<Key, T>::remove()
+    \fn template <class Key, class T> void QMutableMultiMapIterator<Key, T>::remove()
 
     Removes the last item that was jumped over using one of the
     traversal functions (next(), previous(), findNext(), findPrevious()).
@@ -1413,6 +1559,7 @@
 */
 
 /*! \fn template <class Key, class T> void QMutableMapIterator<Key, T>::setValue(const T &value)
+    \fn template <class Key, class T> void QMutableMultiMapIterator<Key, T>::setValue(const T &value)
 
     Replaces the value of the last item that was jumped over using
     one of the traversal functions with \a value.
diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h
index d3e27f09ef..2a87912c4a 100644
--- a/src/corelib/tools/qmap.h
+++ b/src/corelib/tools/qmap.h
@@ -1,5 +1,6 @@
 /****************************************************************************
 **
+** Copyright (C) 2020 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
 ** Copyright (C) 2016 The Qt Company Ltd.
 ** Contact: https://www.qt.io/licensing/
 **
@@ -44,376 +45,357 @@
 #include <QtCore/qlist.h>
 #include <QtCore/qrefcount.h>
 #include <QtCore/qpair.h>
-
-#ifdef Q_MAP_DEBUG
-#include <QtCore/qdebug.h>
-#endif
+#include <QtCore/qshareddata.h>
+#include <QtCore/qshareddata_impl.h>
 
 #include <functional>
 #include <initializer_list>
 #include <map>
-#include <new>
+#include <algorithm>
 
 QT_BEGIN_NAMESPACE
 
-/*
-    QMap uses qMapLessThanKey() to compare keys. The default
-    implementation uses operator<(). For pointer types,
-    qMapLessThanKey() uses std::less (because operator<() on
-    pointers can be used only between pointers in the same array).
-*/
-
-template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key2)
+// common code shared between QMap and QMultimap
+template <typename AMap>
+class QMapData : public QSharedData
 {
-    return key1 < key2;
-}
+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;
+
+    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 &keyCompare = source.key_comp();
+        const auto filter = [&result, &key, &keyCompare](const auto &v)
+        {
+            if (!keyCompare(key, v.first) && !keyCompare(v.first, key)) {
+                // keys are equivalent (neither a<b nor b<a) => found it
+                ++result;
+                return true;
+            }
+            return false;
+        };
 
-template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2)
-{
-    return std::less<const Ptr *>()(key1, key2);
-}
+        std::remove_copy_if(source.cbegin(), source.cend(),
+                            std::inserter(m, m.end()),
+                            filter);
+        return result;
+    }
 
-struct QMapDataBase;
-template <class Key, class T> struct QMapData;
+    // 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; };
+    }
 
-struct Q_CORE_EXPORT QMapNodeBase
-{
-    quintptr p;
-    QMapNodeBase *left;
-    QMapNodeBase *right;
-
-    enum Color { Red = 0, Black = 1 };
-    enum { Mask = 3 }; // reserve the second bit as well
-
-    const QMapNodeBase *nextNode() const;
-    QMapNodeBase *nextNode() { return const_cast<QMapNodeBase *>(const_cast<const QMapNodeBase *>(this)->nextNode()); }
-    const QMapNodeBase *previousNode() const;
-    QMapNodeBase *previousNode() { return const_cast<QMapNodeBase *>(const_cast<const QMapNodeBase *>(this)->previousNode()); }
-
-    Color color() const { return Color(p & 1); }
-    void setColor(Color c) { if (c == Black) p |= Black; else p &= ~Black; }
-    QMapNodeBase *parent() const { return reinterpret_cast<QMapNodeBase *>(p & ~Mask); }
-    void setParent(QMapNodeBase *pp) { p = (p & Mask) | quintptr(pp); }
-
-    template <typename T>
-    static typename std::enable_if<QTypeInfo<T>::isComplex>::type
-    callDestructorIfNecessary(T &t) noexcept { Q_UNUSED(t); t.~T(); } // Q_UNUSED: silence MSVC unused 't' warning
-    template <typename T>
-    static typename std::enable_if<!QTypeInfo<T>::isComplex>::type
-    callDestructorIfNecessary(T &) noexcept {}
-};
+    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;
 
-template <class Key, class T>
-struct QMapNode : public QMapNodeBase
-{
-    Key key;
-    T value;
+        return defaultKey;
+    }
 
-    inline QMapNode *leftNode() const { return static_cast<QMapNode *>(left); }
-    inline QMapNode *rightNode() const { return static_cast<QMapNode *>(right); }
+    QList<Key> keys() const
+    {
+        QList<Key> result;
+        result.reserve(m.size());
 
-    inline const QMapNode *nextNode() const { return reinterpret_cast<const QMapNode *>(QMapNodeBase::nextNode()); }
-    inline const QMapNode *previousNode() const { return static_cast<const QMapNode *>(QMapNodeBase::previousNode()); }
-    inline QMapNode *nextNode() { return reinterpret_cast<QMapNode *>(QMapNodeBase::nextNode()); }
-    inline QMapNode *previousNode() { return static_cast<QMapNode *>(QMapNodeBase::previousNode()); }
+        const auto extractKey = [](const auto &v) { return v.first; };
 
-    QMapNode<Key, T> *copy(QMapData<Key, T> *d) const;
+        std::transform(m.cbegin(),
+                       m.cend(),
+                       std::back_inserter(result),
+                       extractKey);
+        return result;
+    }
 
-    void destroySubTree()
+    QList<Key> keys(const T &value) const
     {
-        callDestructorIfNecessary(key);
-        callDestructorIfNecessary(value);
-        doDestroySubTree(std::integral_constant<bool, QTypeInfo<T>::isComplex || QTypeInfo<Key>::isComplex>());
+        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;
     }
 
-    QMapNode<Key, T> *lowerBound(const Key &key);
-    QMapNode<Key, T> *upperBound(const Key &key);
-
-private:
-    void doDestroySubTree(std::false_type) {}
-    void doDestroySubTree(std::true_type)
+    QList<T> values() const
     {
-        if (left)
-            leftNode()->destroySubTree();
-        if (right)
-            rightNode()->destroySubTree();
+        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;
     }
 
-    QMapNode() = delete;
-    Q_DISABLE_COPY(QMapNode)
+    size_type count(const Key &key) const
+    {
+        return m.count(key);
+    }
 };
 
-template <class Key, class T>
-inline QMapNode<Key, T> *QMapNode<Key, T>::lowerBound(const Key &akey)
-{
-    QMapNode<Key, T> *n = this;
-    QMapNode<Key, T> *lastNode = nullptr;
-    while (n) {
-        if (!qMapLessThanKey(n->key, akey)) {
-            lastNode = n;
-            n = n->leftNode();
-        } else {
-            n = n->rightNode();
-        }
-    }
-    return lastNode;
-}
+//
+// QMap
+//
 
 template <class Key, class T>
-inline QMapNode<Key, T> *QMapNode<Key, T>::upperBound(const Key &akey)
+class QMap
 {
-    QMapNode<Key, T> *n = this;
-    QMapNode<Key, T> *lastNode = nullptr;
-    while (n) {
-        if (qMapLessThanKey(akey, n->key)) {
-            lastNode = n;
-            n = n->leftNode();
-        } else {
-            n = n->rightNode();
-        }
-    }
-    return lastNode;
-}
+    using MapData = QMapData<std::map<Key, T>>;
+    QtPrivate::QExplicitlySharedDataPointerV2<MapData> d;
 
+public:
+    using key_type = Key;
+    using mapped_type = T;
+    using difference_type = qptrdiff;
+    using size_type = qsizetype;
 
+    constexpr QMap() noexcept {}
 
-struct Q_CORE_EXPORT QMapDataBase
-{
-    QtPrivate::RefCount ref;
-    qsizetype size;
-    QMapNodeBase header;
-    QMapNodeBase *mostLeftNode;
+    // implicitly generated special member functions are OK!
 
-    void rotateLeft(QMapNodeBase *x);
-    void rotateRight(QMapNodeBase *x);
-    void rebalance(QMapNodeBase *x);
-    void freeNodeAndRebalance(QMapNodeBase *z);
-    void recalcMostLeftNode();
-
-    QMapNodeBase *createNode(size_t size, size_t alignment, QMapNodeBase *parent, bool left);
-    void freeTree(QMapNodeBase *root, size_t alignment);
+    void swap(QMap<Key, T> &other) noexcept
+    {
+        qSwap(d, other.d);
+    }
 
-    static const QMapDataBase shared_null;
+    QMap(std::initializer_list<std::pair<Key, T>> list)
+    {
+        for (auto &p : list)
+            insert(p.first, p.second);
+    }
 
-    static QMapDataBase *createData();
-    static void freeData(QMapDataBase *d);
-};
+    explicit QMap(const std::map<Key, T> &other)
+        : d(other.empty() ? nullptr : new MapData(other))
+    {
+    }
 
-template <class Key, class T>
-struct QMapData : public QMapDataBase
-{
-    typedef QMapNode<Key, T> Node;
-
-    Node *root() const { return static_cast<Node *>(header.left); }
-
-    // using reinterpret_cast because QMapDataBase::header is not
-    // actually a QMapNode.
-    const Node *end() const { return reinterpret_cast<const Node *>(&header); }
-    Node *end() { return reinterpret_cast<Node *>(&header); }
-    const Node *begin() const { if (root()) return static_cast<const Node*>(mostLeftNode); return end(); }
-    Node *begin() { if (root()) return static_cast<Node*>(mostLeftNode); return end(); }
-
-    void deleteNode(Node *z);
-    Node *findNode(const Key &akey) const;
-    void nodeRange(const Key &akey, Node **firstNode, Node **lastNode);
-
-    Node *createNode(const Key &k, const T &v, Node *parent = nullptr, bool left = false)
-    {
-        Node *n = static_cast<Node *>(QMapDataBase::createNode(sizeof(Node), alignof(Node),
-                                      parent, left));
-        QT_TRY {
-            new (&n->key) Key(k);
-            QT_TRY {
-                new (&n->value) T(v);
-            } QT_CATCH(...) {
-                n->key.~Key();
-                QT_RETHROW;
-            }
-        } QT_CATCH(...) {
-            QMapDataBase::freeNodeAndRebalance(n);
-            QT_RETHROW;
-        }
-        return n;
+    explicit QMap(std::map<Key, T> &&other)
+        : d(other.empty() ? nullptr : new MapData(std::move(other)))
+    {
     }
 
-    static QMapData *create() {
-        return static_cast<QMapData *>(createData());
+    std::map<Key, T> toStdMap() const &
+    {
+        if (d)
+            return d->m;
+        return {};
     }
 
-    void destroy() {
-        if (root()) {
-            root()->destroySubTree();
-            freeTree(header.left, alignof(Node));
+    std::map<Key, T> toStdMap() &&
+    {
+        if (d) {
+            if (d.isShared())
+                return d->m;
+            else
+                return std::move(d->m);
         }
-        freeData(this);
+
+        return {};
     }
-};
 
-template <class Key, class T>
-QMapNode<Key, T> *QMapNode<Key, T>::copy(QMapData<Key, T> *d) const
-{
-    QMapNode<Key, T> *n = d->createNode(key, value);
-    n->setColor(color());
-    if (left) {
-        n->left = leftNode()->copy(d);
-        n->left->setParent(n);
-    } else {
-        n->left = nullptr;
-    }
-    if (right) {
-        n->right = rightNode()->copy(d);
-        n->right->setParent(n);
-    } else {
-        n->right = nullptr;
-    }
-    return n;
-}
+    // CHANGE: non-member equality comparison
+    template <typename AKey, typename AT>
+    friend QTypeTraits::compare_eq_result<AKey, AT> operator==(const QMap<AKey, AT> &lhs, const QMap<AKey, AT> &rhs);
+    template <typename AKey, typename AT>
+    friend QTypeTraits::compare_eq_result<AKey, AT> operator!=(const QMap<AKey, AT> &lhs, const QMap<AKey, AT> &rhs);
 
-template <class Key, class T>
-void QMapData<Key, T>::deleteNode(QMapNode<Key, T> *z)
-{
-    QMapNodeBase::callDestructorIfNecessary(z->key);
-    QMapNodeBase::callDestructorIfNecessary(z->value);
-    freeNodeAndRebalance(z);
-}
+    // TODO: add the other comparison operators; std::map has them.
 
-template <class Key, class T>
-QMapNode<Key, T> *QMapData<Key, T>::findNode(const Key &akey) const
-{
-    if (Node *r = root()) {
-        Node *lb = r->lowerBound(akey);
-        if (lb && !qMapLessThanKey(akey, lb->key))
-            return lb;
+    size_type size() const { return d ? size_type(d->m.size()) : size_type(0); }
+
+    bool isEmpty() const { return d ? d->m.empty() : true; }
+
+    void detach()
+    {
+        if (d)
+            d.detach();
+        else
+            d.reset(new MapData);
     }
-    return nullptr;
-}
 
+    bool isDetached() const noexcept
+    {
+        return d ? !d.isShared() : false; // false makes little sense, but that's shared_null's behavior...
+    }
 
-template <class Key, class T>
-void QMapData<Key, T>::nodeRange(const Key &akey, QMapNode<Key, T> **firstNode, QMapNode<Key, T> **lastNode)
-{
-    Node *n = root();
-    Node *l = end();
-    while (n) {
-        if (qMapLessThanKey(akey, n->key)) {
-            l = n;
-            n = n->leftNode();
-        } else if (qMapLessThanKey(n->key, akey)) {
-            n = n->rightNode();
-        } else {
-            *firstNode = n->leftNode() ? n->leftNode()->lowerBound(akey) : nullptr;
-            if (!*firstNode)
-                *firstNode = n;
-            *lastNode = n->rightNode() ? n->rightNode()->upperBound(akey) : nullptr;
-            if (!*lastNode)
-                *lastNode = l;
+    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();
     }
-    *firstNode = *lastNode = l;
-}
 
+    size_type remove(const Key &key)
+    {
+        if (!d)
+            return 0;
+
+        if (!d.isShared())
+            return size_type(d->m.erase(key));
 
-template <class Key, class T>
-class QMap
-{
-    typedef QMapNode<Key, T> Node;
+        MapData *newData = new MapData;
+        size_type result = newData->copyIfNotEquivalentTo(d->m, key);
 
-    QMapData<Key, T> *d;
+        d.reset(newData);
 
-public:
-    inline QMap() noexcept : d(static_cast<QMapData<Key, T> *>(const_cast<QMapDataBase *>(&QMapDataBase::shared_null))) { }
-    inline QMap(std::initializer_list<std::pair<Key,T> > list)
-        : d(static_cast<QMapData<Key, T> *>(const_cast<QMapDataBase *>(&QMapDataBase::shared_null)))
-    {
-        for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it)
-            insert(it->first, it->second);
+        return result;
     }
-    QMap(const QMap<Key, T> &other);
-
-    inline ~QMap() { if (!d->ref.deref()) d->destroy(); }
 
-    QMap<Key, T> &operator=(const QMap<Key, T> &other);
-    inline QMap(QMap<Key, T> &&other) noexcept
-        : d(other.d)
+    T take(const Key &key)
     {
-        other.d = static_cast<QMapData<Key, T> *>(
-                const_cast<QMapDataBase *>(&QMapDataBase::shared_null));
+        if (!d)
+            return T();
+
+        // TODO: improve. There is no need of copying all the
+        // elements (the one to be removed can be skipped).
+        detach();
+
+        auto i = d->m.find(key);
+        if (i != d->m.end()) {
+            T result(std::move(i->second));
+            d->m.erase(i);
+            return result;
+        }
+        return T();
     }
 
-    inline QMap<Key, T> &operator=(QMap<Key, T> &&other) noexcept
-    { QMap moved(std::move(other)); swap(moved); return *this; }
-    inline void swap(QMap<Key, T> &other) noexcept { qSwap(d, other.d); }
-    explicit QMap(const typename std::map<Key, T> &other);
-    std::map<Key, T> toStdMap() const;
-
-    template <typename U = T>
-    QTypeTraits::compare_eq_result<U> operator==(const QMap<Key, T> &other) const
+    bool contains(const Key &key) const
     {
-        if (size() != other.size())
+        if (!d)
             return false;
-        if (d == other.d)
-            return true;
+        auto i = d->m.find(key);
+        return i != d->m.end();
+    }
 
-        const_iterator it1 = begin();
-        const_iterator it2 = other.begin();
+    // ### Qt 6: deprecate value->key lookup.
+    //Q_DECL_DEPRECATED_X("This function is inefficient; don't use it")
+    Key key(const T &value, const Key &defaultKey = Key()) const
+    {
+        if (!d)
+            return defaultKey;
 
-        while (it1 != end()) {
-            if (!(it1.value() == it2.value()) || qMapLessThanKey(it1.key(), it2.key()) || qMapLessThanKey(it2.key(), it1.key()))
-                return false;
-            ++it2;
-            ++it1;
-        }
-        return true;
+        return d->key(value, defaultKey);
     }
-    template <typename U = T>
-    QTypeTraits::compare_eq_result<U> operator!=(const QMap<Key, T> &other) const
-    { return !(*this == other); }
 
-    inline qsizetype size() const { return d->size; }
+    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;
+    }
 
-    inline bool isEmpty() const { return d->size == 0; }
+    T &operator[](const Key &key)
+    {
+        detach();
+        auto i = d->m.find(key);
+        if (i == d->m.end())
+            i = d->m.insert({key, T()}).first;
+        return i->second;
+    }
 
-    inline void detach() { if (d->ref.isShared()) detach_helper(); }
-    inline bool isDetached() const { return !d->ref.isShared(); }
-    inline bool isSharedWith(const QMap<Key, T> &other) const { return d == other.d; }
+    // CHANGE: return T, not const T!
+    T operator[](const Key &key) const
+    {
+        return value(key);
+    }
 
-    void clear();
+    // ### Qt 6: this stuff should be deprecated as well
+    QList<Key> keys() const
+    {
+        if (!d)
+            return {};
+        return d->keys();
+    }
 
-    qsizetype remove(const Key &key);
-    T take(const Key &key);
+    QList<Key> keys(const T &value) const
+    {
+        if (!d)
+            return {};
+        return d->keys(value);
+    }
 
-    bool contains(const Key &key) const;
-    Key key(const T &value, const Key &defaultKey = Key()) const;
-    T value(const Key &key, const T &defaultValue = T()) const;
-    T &operator[](const Key &key);
-    const T operator[](const Key &key) const;
+    QList<T> values() const
+    {
+        if (!d)
+            return {};
+        return d->values();
+    }
 
-    QList<Key> keys() const;
-    QList<Key> keys(const T &value) const;
-    QList<T> values() const;
-#if QT_DEPRECATED_SINCE(5, 15)
-    QT_DEPRECATED_VERSION_X_5_15("Use QMultiMap for maps storing multiple values with the same key.") QList<Key> uniqueKeys() const;
-    QT_DEPRECATED_VERSION_X_5_15("Use QMultiMap for maps storing multiple values with the same key.") QList<T> values(const Key &key) const;
-#endif
-    qsizetype count(const Key &key) const;
+    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() - 1).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() - 1); }
-    inline const T &last() const { Q_ASSERT(!isEmpty()); return *(constEnd() - 1); }
+    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;
-        Node *i;
 
+        typename MapData::Map::iterator i;
+        explicit iterator(typename MapData::Map::iterator it) : i(it) {}
     public:
         typedef std::bidirectional_iterator_tag iterator_category;
         typedef qptrdiff difference_type;
@@ -421,52 +403,44 @@ public:
         typedef T *pointer;
         typedef T &reference;
 
-        inline iterator() : i(nullptr) { }
-        inline iterator(Node *node) : i(node) { }
+        iterator() = default;
 
-        inline const Key &key() const { return i->key; }
-        inline T &value() const { return i->value; }
-        inline T &operator*() const { return i->value; }
-        inline T *operator->() const { return &i->value; }
-        inline bool operator==(const iterator &o) const { return i == o.i; }
-        inline bool operator!=(const iterator &o) const { return i != o.i; }
+        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; }
 
-        inline iterator &operator++() {
-            i = i->nextNode();
+        iterator &operator++()
+        {
+            ++i;
             return *this;
         }
-        inline iterator operator++(int) {
+        iterator operator++(int)
+        {
             iterator r = *this;
-            i = i->nextNode();
+            ++i;
             return r;
         }
-        inline iterator &operator--() {
-            i = i->previousNode();
+        iterator &operator--()
+        {
+            --i;
             return *this;
         }
-        inline iterator operator--(int) {
+        iterator operator--(int)
+        {
             iterator r = *this;
-            i = i->previousNode();
+            --i;
             return r;
         }
-        inline iterator operator+(qsizetype j) const
-        { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
-        inline iterator operator-(qsizetype j) const { return operator+(-j); }
-        inline iterator &operator+=(qsizetype j) { return *this = *this + j; }
-        inline iterator &operator-=(qsizetype j) { return *this = *this - j; }
-        friend inline iterator operator+(qsizetype j, iterator k) { return k + j; }
-
-        inline bool operator==(const const_iterator &o) const { return i == o.i; }
-        inline bool operator!=(const const_iterator &o) const { return i != o.i; }
-        friend class QMap<Key, T>;
-        friend class QMultiMap<Key, T>;
     };
-    friend class iterator;
 
     class const_iterator
     {
-        friend class iterator;
-        const Node *i;
+        friend class QMap<Key, T>;
+        typename MapData::Map::const_iterator i;
+        explicit const_iterator(typename MapData::Map::const_iterator it) : i(it) {}
 
     public:
         typedef std::bidirectional_iterator_tag iterator_category;
@@ -475,46 +449,39 @@ public:
         typedef const T *pointer;
         typedef const T &reference;
 
-        Q_DECL_CONSTEXPR inline const_iterator() : i(nullptr) { }
-        inline const_iterator(const Node *node) : i(node) { }
-        inline const_iterator(const iterator &o) { i = o.i; }
+        const_iterator() = default;
+        /* implicit */ const_iterator(const iterator &o) { i = o.i; }
 
-        inline const Key &key() const { return i->key; }
-        inline const T &value() const { return i->value; }
-        inline const T &operator*() const { return i->value; }
-        inline const T *operator->() const { return &i->value; }
-        Q_DECL_CONSTEXPR inline bool operator==(const const_iterator &o) const { return i == o.i; }
-        Q_DECL_CONSTEXPR inline bool operator!=(const const_iterator &o) const { return 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; }
 
-        inline const_iterator &operator++() {
-            i = i->nextNode();
+        const_iterator &operator++()
+        {
+            ++i;
             return *this;
         }
-        inline const_iterator operator++(int) {
+        const_iterator operator++(int)
+        {
             const_iterator r = *this;
-            i = i->nextNode();
+            ++i;
             return r;
         }
-        inline const_iterator &operator--() {
-            i = i->previousNode();
+        const_iterator &operator--()
+        {
+            --i;
             return *this;
         }
-        inline const_iterator operator--(int) {
+        const_iterator operator--(int)
+        {
             const_iterator r = *this;
-            i = i->previousNode();
+            --i;
             return r;
         }
-        inline const_iterator operator+(qsizetype j) const
-        { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
-        inline const_iterator operator-(qsizetype j) const { return operator+(-j); }
-        inline const_iterator &operator+=(qsizetype j) { return *this = *this + j; }
-        inline const_iterator &operator-=(qsizetype j) { return *this = *this - j; }
-        friend inline const_iterator operator+(qsizetype j, const_iterator k) { return k + j; }
-
-        friend class QMap<Key, T>;
-        friend class QMultiMap<Key, T>;
     };
-    friend class const_iterator;
 
     class key_iterator
     {
@@ -546,814 +513,870 @@ public:
     typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator;
 
     // STL style
-    inline iterator begin() { detach(); return iterator(d->begin()); }
-    inline const_iterator begin() const { return const_iterator(d->begin()); }
-    inline const_iterator constBegin() const { return const_iterator(d->begin()); }
-    inline const_iterator cbegin() const { return const_iterator(d->begin()); }
-    inline iterator end() { detach(); return iterator(d->end()); }
-    inline const_iterator end() const { return const_iterator(d->end()); }
-    inline const_iterator constEnd() const { return const_iterator(d->end()); }
-    inline const_iterator cend() const { return const_iterator(d->end()); }
-    inline key_iterator keyBegin() const { return key_iterator(begin()); }
-    inline key_iterator keyEnd() const { return key_iterator(end()); }
-    inline key_value_iterator keyValueBegin() { return key_value_iterator(begin()); }
-    inline key_value_iterator keyValueEnd() { return key_value_iterator(end()); }
-    inline const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); }
-    inline const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); }
-    inline const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); }
-    inline const_key_value_iterator constKeyValueEnd() const { return const_key_value_iterator(end()); }
-    iterator erase(iterator it);
+    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()); }
+
+    iterator erase(const_iterator it)
+    {
+        if (!d)
+            return iterator();
+
+        if (!d.isShared())
+            return iterator(d->m.erase(it.i));
+
+        MapData *newData = new MapData;
+        const auto newDataEnd = newData->m.end();
+
+        auto i = d->m.begin();
+        auto e = d->m.end();
+        size_type steps = 0;
+
+        while (i != it.i) {
+            newData->m.insert(newDataEnd, *i);
+            ++i;
+            ++steps;
+        }
+
+        if (i != e)
+            ++i;
+
+        while (i != e)
+            newData->m.insert(newDataEnd, *i);
+
+        d.reset(newData);
+
+        auto result = std::next(d->m.begin(), steps);
+        return iterator(result);
+    }
 
     // more Qt
     typedef iterator Iterator;
     typedef const_iterator ConstIterator;
-    inline qsizetype count() const { return d->size; }
-    iterator find(const Key &key);
-    const_iterator find(const Key &key) const;
-    const_iterator constFind(const Key &key) const;
-    iterator lowerBound(const Key &key);
-    const_iterator lowerBound(const Key &key) const;
-    iterator upperBound(const Key &key);
-    const_iterator upperBound(const Key &key) const;
-    iterator insert(const Key &key, const T &value);
-    iterator insert(const_iterator pos, const Key &key, const T &value);
-    void insert(const QMap<Key, T> &map);
-#if QT_DEPRECATED_SINCE(5, 15)
-    QT_DEPRECATED_VERSION_X_5_15("Use QMultiMap for maps storing multiple values with the same key.") iterator insertMulti(const Key &key, const T &value);
-    QT_DEPRECATED_VERSION_X_5_15("Use QMultiMap for maps storing multiple values with the same key.") iterator insertMulti(const_iterator pos, const Key &akey, const T &avalue);
-    QT_DEPRECATED_VERSION_X_5_15("Use QMultiMap for maps storing multiple values with the same key.") QMap<Key, T> &unite(const QMap<Key, T> &other);
-#endif
 
-    // STL compatibility
-    typedef Key key_type;
-    typedef T mapped_type;
-    typedef T value_type;
-    typedef qptrdiff difference_type;
-    typedef qsizetype size_type;
-    inline bool empty() const { return isEmpty(); }
-    QPair<iterator, iterator> equal_range(const Key &akey);
-    QPair<const_iterator, const_iterator> equal_range(const Key &akey) const;
+    iterator find(const Key &key)
+    {
+        detach();
+        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)
+    {
+        detach();
+        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)
+    {
+        detach();
+        return iterator(d->m.upper_bound(key));
+    }
 
-#ifdef Q_MAP_DEBUG
-    void dump() const;
+    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)
+    {
+        // TODO: improve. In case of assignment, why copying first?
+        detach();
+        return iterator(d->m.insert_or_assign(key, value).first);
+    }
+
+    iterator insert(const_iterator pos, const Key &key, const T &value)
+    {
+        // TODO: improve. In case of assignment, why copying first?
+        auto posDistance = d ? std::distance(d->m.cbegin(), pos.i) : 0;
+        detach();
+        auto detachedPos = std::next(d->m.cbegin(), posDistance);
+        return iterator(d->m.insert_or_assign(detachedPos, key, value));
+    }
+
+    void insert(const QMap<Key, T> &map)
+    {
+        // TODO: improve. In case of assignment, why copying first?
+        if (map.isEmpty())
+            return;
+
+        detach();
+
+#ifdef __cpp_lib_node_extract
+        auto copy = map.d->m;
+        copy.merge(std::move(d->m));
+        d->m = std::move(copy);
+#else
+        // this is a std::copy, but we can't use std::inserter (need insert_or_assign...).
+        // copy in reverse order, trying to make effective use of insertionHint.
+        auto insertionHint = d->m.end();
+        auto mapIt = map.d->m.crbegin();
+        auto end = map.d->m.crend();
+        for (; mapIt != end; ++mapIt)
+            insertionHint = d->m.insert_or_assign(insertionHint, mapIt->first, mapIt->second);
 #endif
+    }
 
-private:
-    void detach_helper();
-    bool isValidIterator(const const_iterator &ci) const
+    void insert(QMap<Key, T> &&map)
     {
-#if defined(QT_DEBUG) && !defined(Q_MAP_NO_ITERATOR_DEBUG)
-        const QMapNodeBase *n = ci.i;
-        while (n->parent())
-            n = n->parent();
-        return n->left == d->root();
+        if (!map.d || map.d->m.empty())
+            return;
+
+        detach();
+
+#ifdef __cpp_lib_node_extract
+        map.d->m.merge(std::move(d->m));
+        *this = std::move(map);
 #else
-        Q_UNUSED(ci);
-        return true;
+        // same as above
+        auto insertionHint = d->m.end();
+        auto mapIt = map.d->m.crbegin();
+        auto end = map.d->m.crend();
+        for (; mapIt != end; ++mapIt)
+            insertionHint = d->m.insert_or_assign(insertionHint, std::move(mapIt->first), std::move(mapIt->second));
 #endif
     }
 
-    friend class QMultiMap<Key, T>;
-};
+    // STL compatibility
+    inline bool empty() const
+    {
+        return isEmpty();
+    }
 
-template <class Key, class T>
-inline QMap<Key, T>::QMap(const QMap<Key, T> &other)
-{
-    if (other.d->ref.ref()) {
-        d = other.d;
-    } else {
-        d = QMapData<Key, T>::create();
-        if (other.d->header.left) {
-            d->header.left = static_cast<Node *>(other.d->header.left)->copy(d);
-            d->header.left->setParent(&d->header);
-            d->recalcMostLeftNode();
-        }
+    QPair<iterator, iterator> equal_range(const Key &akey)
+    {
+        detach();
+        auto result = d->m.equal_range(akey);
+        return {iterator(result.first), iterator(result.second)};
     }
-}
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other)
-{
-    if (d != other.d) {
-        QMap<Key, T> tmp(other);
-        tmp.swap(*this);
+    QPair<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)};
     }
-    return *this;
-}
+};
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE void QMap<Key, T>::clear()
+Q_DECLARE_ASSOCIATIVE_ITERATOR(Map)
+Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map)
+
+template <typename AKey, typename AT>
+QTypeTraits::compare_eq_result<AKey, AT> operator==(const QMap<AKey, AT> &lhs, const QMap<AKey, AT> &rhs)
 {
-    *this = QMap<Key, T>();
+    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_WARNING_PUSH
-QT_WARNING_DISABLE_CLANG("-Wreturn-stack-address")
-
-template <class Key, class T>
-Q_INLINE_TEMPLATE T QMap<Key, T>::value(const Key &akey, const T &adefaultValue) const
+template <typename AKey, typename AT>
+QTypeTraits::compare_eq_result<AKey, AT> operator!=(const QMap<AKey, AT> &lhs, const QMap<AKey, AT> &rhs)
 {
-    Node *n = d->findNode(akey);
-    return n ? n->value : adefaultValue;
+    return !(lhs == rhs);
 }
 
-QT_WARNING_POP
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE const T QMap<Key, T>::operator[](const Key &akey) const
-{
-    return value(akey);
-}
+//
+// QMultiMap
+//
 
 template <class Key, class T>
-Q_INLINE_TEMPLATE T &QMap<Key, T>::operator[](const Key &akey)
+class QMultiMap
 {
-    detach();
-    Node *n = d->findNode(akey);
-    if (!n)
-        return *insert(akey, T());
-    return n->value;
-}
+    using MapData = QMapData<std::multimap<Key, T>>;
+    QtPrivate::QExplicitlySharedDataPointerV2<MapData> d;
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE qsizetype QMap<Key, T>::count(const Key &akey) const
-{
-    Node *firstNode;
-    Node *lastNode;
-    d->nodeRange(akey, &firstNode, &lastNode);
-
-    const_iterator ci_first(firstNode);
-    const const_iterator ci_last(lastNode);
-    int cnt = 0;
-    while (ci_first != ci_last) {
-        ++cnt;
-        ++ci_first;
-    }
-    return cnt;
-}
+public:
+    using key_type = Key;
+    using mapped_type = T;
+    using difference_type = qptrdiff;
+    using size_type = qsizetype;
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE bool QMap<Key, T>::contains(const Key &akey) const
-{
-    return d->findNode(akey) != nullptr;
-}
+    constexpr QMultiMap() noexcept {}
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey, const T &avalue)
-{
-    detach();
-    Node *n = d->root();
-    Node *y = d->end();
-    Node *lastNode = nullptr;
-    bool  left = true;
-    while (n) {
-        y = n;
-        if (!qMapLessThanKey(n->key, akey)) {
-            lastNode = n;
-            left = true;
-            n = n->leftNode();
-        } else {
-            left = false;
-            n = n->rightNode();
-        }
+    // 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);
     }
-    if (lastNode && !qMapLessThanKey(akey, lastNode->key)) {
-        lastNode->value = avalue;
-        return iterator(lastNode);
+
+    void swap(QMultiMap<Key, T> &other) noexcept
+    {
+        qSwap(d, other.d);
     }
-    Node *z = d->createNode(akey, avalue, y, left);
-    return iterator(z);
-}
 
-template <class Key, class T>
-typename QMap<Key, T>::iterator QMap<Key, T>::insert(const_iterator pos, const Key &akey, const T &avalue)
-{
-    if (d->ref.isShared())
-        return this->insert(akey, avalue);
-
-    Q_ASSERT_X(isValidIterator(pos), "QMap::insert", "The specified const_iterator argument 'it' is invalid");
-
-    if (pos == constEnd()) {
-        // Hint is that the Node is larger than (or equal to) the largest value.
-        Node *n = static_cast<Node *>(pos.i->left);
-        if (n) {
-            while (n->right)
-                n = static_cast<Node *>(n->right);
-
-            if (!qMapLessThanKey(n->key, akey))
-                return this->insert(akey, avalue); // ignore hint
-            // This can be optimized by checking equal too.
-            // we can overwrite if previous node key is strictly smaller
-            // (or there is no previous node)
-
-            Node *z = d->createNode(akey, avalue, n, false); // insert right most
-            return iterator(z);
-        }
-        return this->insert(akey, avalue);
-    } else {
-        // Hint indicates that the node should be less (or equal to) the hint given
-        // but larger than the previous value.
-        Node *next = const_cast<Node*>(pos.i);
-        if (qMapLessThanKey(next->key, akey))
-            return this->insert(akey, avalue); // ignore hint
-
-        if (pos == constBegin()) {
-            // There is no previous value
-            // Maybe overwrite left most value
-            if (!qMapLessThanKey(akey, next->key)) {
-                next->value = avalue; // overwrite current iterator
-                return iterator(next);
-            }
-            // insert left most.
-            Node *z = d->createNode(akey, avalue, begin().i, true);
-            return iterator(z);
-        } else {
-            Node *prev = const_cast<Node*>(pos.i->previousNode());
-            if (!qMapLessThanKey(prev->key, akey)) {
-                return this->insert(akey, avalue); // ignore hint
-            }
-            // Hint is ok
-            if (!qMapLessThanKey(akey, next->key)) {
-                next->value = avalue; // overwrite current iterator
-                return iterator(next);
-            }
+    explicit QMultiMap(const std::multimap<Key, T> &other)
+        : d(other.empty() ? nullptr : new MapData(other))
+    {
+    }
 
-            // we need to insert (not overwrite)
-            if (prev->right == nullptr) {
-                Node *z = d->createNode(akey, avalue, prev, false);
-                return iterator(z);
-            }
-            if (next->left == nullptr) {
-                Node *z = d->createNode(akey, avalue, next, true);
-                return iterator(z);
-            }
-            Q_ASSERT(false); // We should have prev->right == nullptr or next->left == nullptr.
-            return this->insert(akey, avalue);
-        }
+    explicit QMultiMap(std::multimap<Key, T> &&other)
+        : d(other.empty() ? nullptr : new MapData(std::move(other)))
+    {
     }
-}
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE void QMap<Key, T>::insert(const QMap<Key, T> &map)
-{
-    if (d == map.d)
-        return;
-
-    detach();
-
-    Node *n = d->root();
-    auto it = map.cbegin();
-    const auto e = map.cend();
-    while (it != e) {
-        // Insertion here is based on insert(Key, T)
-        auto parent = d->end();
-        bool left = true;
-        Node *lastNode = nullptr;
-        while (n) {
-            parent = n;
-            if (!qMapLessThanKey(n->key, it.key())) {
-                lastNode = n;
-                n = n->leftNode();
-                left = true;
-            } else {
-                n = n->rightNode();
-                left = false;
-            }
-        }
-        if (lastNode && !qMapLessThanKey(it.key(), lastNode->key)) {
-            lastNode->value = it.value();
-            n = lastNode;
-        } else {
-            n = d->createNode(it.key(), it.value(), parent, left);
-        }
-        ++it;
-        if (it != e) {
-            // Move back up the tree until we find the next branch or node which is
-            // relevant for the next key.
-            while (n != d->root() && qMapLessThanKey(n->key, it.key()))
-                n = static_cast<Node *>(n->parent());
+    // 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 {};
     }
-}
 
+    // CHANGE: non-member equality comparison
+    template <typename AKey, typename AT>
+    friend QTypeTraits::compare_eq_result<AKey, AT> operator==(const QMultiMap<AKey, AT> &lhs, const QMultiMap<AKey, AT> &rhs);
+    template <typename AKey, typename AT>
+    friend QTypeTraits::compare_eq_result<AKey, AT> operator!=(const QMultiMap<AKey, AT> &lhs, const QMultiMap<AKey, AT> &rhs);
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::constFind(const Key &akey) const
-{
-    Node *n = d->findNode(akey);
-    return const_iterator(n ? n : d->end());
-}
+    // TODO: add the other comparison operators; std::multimap has them.
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &akey) const
-{
-    return constFind(akey);
-}
+    size_type size() const { return d ? size_type(d->m.size()) : size_type(0); }
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::find(const Key &akey)
-{
-    detach();
-    Node *n = d->findNode(akey);
-    return iterator(n ? n : d->end());
-}
+    bool isEmpty() const { return d ? d->m.empty() : true; }
 
-template <class Key, class T>
-QPair<typename QMap<Key, T>::iterator, typename QMap<Key, T>::iterator> QMap<Key, T>::equal_range(const Key &akey)
-{
-    detach();
-    Node *firstNode, *lastNode;
-    d->nodeRange(akey, &firstNode, &lastNode);
-    return QPair<iterator, iterator>(iterator(firstNode), iterator(lastNode));
-}
+    void detach()
+    {
+        if (d)
+            d.detach();
+        else
+            d.reset(new MapData);
+    }
 
-template <class Key, class T>
-QPair<typename QMap<Key, T>::const_iterator, typename QMap<Key, T>::const_iterator>
-QMap<Key, T>::equal_range(const Key &akey) const
-{
-    Node *firstNode, *lastNode;
-    d->nodeRange(akey, &firstNode, &lastNode);
-    return qMakePair(const_iterator(firstNode), const_iterator(lastNode));
-}
+    bool isDetached() const noexcept
+    {
+        return d ? !d.isShared() : false; // false makes little sense, but that's shared_null's behavior...
+    }
 
-#ifdef Q_MAP_DEBUG
-template <class Key, class T>
-void QMap<Key, T>::dump() const
-{
-    const_iterator it = begin();
-    qDebug("map dump:");
-    while (it != end()) {
-        const QMapNodeBase *n = it.i;
-        int depth = 0;
-        while (n && n != d->root()) {
-            ++depth;
-            n = n->parent();
-        }
-        QByteArray space(4*depth, ' ');
-        qDebug() << space << (it.i->color() == Node::Red ? "Red  " : "Black") << it.i << it.i->left << it.i->right
-                 << it.key() << it.value();
-        ++it;
+    bool isSharedWith(const QMultiMap<Key, T> &other) const noexcept
+    {
+        return d == other.d; // also this makes little sense?
     }
-    qDebug("---------");
-}
-#endif
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE qsizetype QMap<Key, T>::remove(const Key &akey)
-{
-    detach();
-    qsizetype n = 0;
-    while (Node *node = d->findNode(akey)) {
-        d->deleteNode(node);
-        ++n;
+    void clear()
+    {
+        if (!d)
+            return;
+
+        if (!d.isShared())
+            d->m.clear();
+        else
+            d.reset();
     }
-    return n;
-}
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE T QMap<Key, T>::take(const Key &akey)
-{
-    detach();
+    size_type remove(const Key &key)
+    {
+        if (!d)
+            return 0;
 
-    Node *node = d->findNode(akey);
-    if (node) {
-        T t = std::move(node->value);
-        d->deleteNode(node);
-        return t;
+        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;
     }
-    return T();
-}
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::erase(iterator it)
-{
-    if (it == iterator(d->end()))
-        return it;
+    size_type remove(const Key &key, const T &value)
+    {
+        if (!d)
+            return 0;
 
-    Q_ASSERT_X(isValidIterator(const_iterator(it)), "QMap::erase", "The specified iterator argument 'it' is invalid");
+        // TODO: improve. Copy over only the elements not to be removed.
+        detach();
 
-    if (d->ref.isShared()) {
-        const_iterator oldBegin = constBegin();
-        const_iterator old = const_iterator(it);
-        qsizetype backStepsWithSameKey = 0;
+        size_type result = 0;
+        const auto &keyCompare = d->m.key_comp();
 
-        while (old != oldBegin) {
-            --old;
-            if (qMapLessThanKey(old.key(), it.key()))
-                break;
-            ++backStepsWithSameKey;
+        auto i = d->m.find(key);
+        const auto e = d->m.end();
+
+        while (i != e && !keyCompare(key, i->first)) {
+            if (i->second == value) {
+                i = d->m.erase(i);
+                ++result;
+            } else {
+                ++i;
+            }
         }
 
-        it = find(old.key()); // ensures detach
-        Q_ASSERT_X(it != iterator(d->end()), "QMap::erase", "Unable to locate same key in erase after detach.");
+        return result;
+    }
 
-        while (backStepsWithSameKey > 0) {
-            ++it;
-            --backStepsWithSameKey;
+    T take(const Key &key)
+    {
+        if (!d)
+            return T();
+
+        // TODO: improve. There is no need of copying all the
+        // elements (the one to be removed can be skipped).
+        detach();
+
+        auto i = d->m.find(key);
+        if (i != d->m.end()) {
+            T result(std::move(i->second));
+            d->m.erase(i);
+            return result;
         }
+        return T();
     }
 
-    Node *n = it.i;
-    ++it;
-    d->deleteNode(n);
-    return it;
-}
+    bool contains(const Key &key) const
+    {
+        if (!d)
+            return false;
+        auto i = d->m.find(key);
+        return i != d->m.end();
+    }
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::detach_helper()
-{
-    QMapData<Key, T> *x = QMapData<Key, T>::create();
-    if (d->header.left) {
-        x->header.left = static_cast<Node *>(d->header.left)->copy(x);
-        x->header.left->setParent(&x->header);
-    }
-    if (!d->ref.deref())
-        d->destroy();
-    d = x;
-    d->recalcMostLeftNode();
-}
+    bool contains(const Key &key, const T &value) const
+    {
+        return find(key, value) != end();
+    }
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys() const
-{
-    QList<Key> res;
-    res.reserve(size());
-    const_iterator i = begin();
-    while (i != end()) {
-        res.append(i.key());
-        ++i;
-    }
-    return res;
-}
+    // ### Qt 6: deprecate value->key lookup.
+    //Q_DECL_DEPRECATED_X("This function is inefficient; don't use it")
+    Key key(const T &value, const Key &defaultKey = Key()) const
+    {
+        if (!d)
+            return defaultKey;
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys(const T &avalue) const
-{
-    QList<Key> res;
-    const_iterator i = begin();
-    while (i != end()) {
-        if (i.value() == avalue)
-            res.append(i.key());
-        ++i;
-    }
-    return res;
-}
+        return d->key(value, defaultKey);
+    }
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE Key QMap<Key, T>::key(const T &avalue, const Key &defaultKey) const
-{
-    const_iterator i = begin();
-    while (i != end()) {
-        if (i.value() == avalue)
-            return i.key();
-        ++i;
+    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;
     }
 
-    return defaultKey;
-}
+    // ### Qt 6: deprecate value->key lookup.
+    QList<Key> keys() const
+    {
+        if (!d)
+            return {};
+        return d->keys();
+    }
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values() const
-{
-    QList<T> res;
-    res.reserve(size());
-    const_iterator i = begin();
-    while (i != end()) {
-        res.append(i.value());
-        ++i;
-    }
-    return res;
-}
+    QList<Key> keys(const T &value) const
+    {
+        if (!d)
+            return {};
+        return d->keys(value);
+    }
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::lowerBound(const Key &akey) const
-{
-    Node *lb = d->root() ? d->root()->lowerBound(akey) : nullptr;
-    if (!lb)
-        lb = d->end();
-    return const_iterator(lb);
-}
+    QList<Key> uniqueKeys() const
+    {
+        QList<Key> result;
+        if (!d)
+            return result;
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::lowerBound(const Key &akey)
-{
-    detach();
-    Node *lb = d->root() ? d->root()->lowerBound(akey) : nullptr;
-    if (!lb)
-        lb = d->end();
-    return iterator(lb);
-}
+        result.reserve(size());
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator
-QMap<Key, T>::upperBound(const Key &akey) const
-{
-    Node *ub = d->root() ? d->root()->upperBound(akey) : nullptr;
-    if (!ub)
-        ub = d->end();
-    return const_iterator(ub);
-}
+        std::unique_copy(keyBegin(), keyEnd(),
+                         std::back_inserter(result));
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::upperBound(const Key &akey)
-{
-    detach();
-    Node *ub = d->root() ? d->root()->upperBound(akey) : nullptr;
-    if (!ub)
-        ub = d->end();
-    return iterator(ub);
-}
+        result.shrink_to_fit();
+        return result;
+    }
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE QMap<Key, T>::QMap(const std::map<Key, T> &other)
-{
-    d = QMapData<Key, T>::create();
-    typename std::map<Key,T>::const_iterator it = other.end();
-    while (it != other.begin()) {
-        --it;
-        d->createNode((*it).first, (*it).second, d->begin(), true); // insert on most left node.
+    QList<T> values() const
+    {
+        if (!d)
+            return {};
+        return d->values();
     }
-}
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE std::map<Key, T> QMap<Key, T>::toStdMap() const
-{
-    std::map<Key, T> map;
-    const_iterator it = end();
-    while (it != begin()) {
-        --it;
-        map.insert(map.begin(), std::pair<Key, T>(it.key(), it.value()));
+    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;
     }
-    return map;
-}
 
-template <class Key, class T>
-class QMultiMap : public QMap<Key, T>
-{
-public:
-    QMultiMap() noexcept {}
-    inline QMultiMap(std::initializer_list<std::pair<Key,T> > list)
-    {
-        for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it)
-            insert(it->first, it->second);
-    }
-    QMultiMap(const QMap<Key, T> &other) : QMap<Key, T>(other) {}
-    QMultiMap(QMap<Key, T> &&other) noexcept : QMap<Key, T>(std::move(other)) {}
-    void swap(QMultiMap<Key, T> &other) noexcept { QMap<Key, T>::swap(other); }
-
-    QList<Key> uniqueKeys() const;
-    QList<T> values(const Key &key) const;
-
-    inline typename QMap<Key, T>::iterator replace(const Key &key, const T &value)
-    { return QMap<Key, T>::insert(key, value); }
-    typename QMap<Key, T>::iterator insert(const Key &key, const T &value);
-    //! [qmultimap-insert-pos]
-    typename QMap<Key, T>::iterator insert(typename QMap<Key, T>::const_iterator pos,
-                                           const Key &key, const T &value);
-
-    //! [qmultimap-unite]
-    QMultiMap &unite(const QMultiMap &other);
-    inline QMultiMap &operator+=(const QMultiMap &other)
-    { return unite(other); }
-    inline QMultiMap operator+(const QMultiMap &other) const
-    { QMultiMap result = *this; result += other; return result; }
-
-    using QMap<Key, T>::contains;
-    using QMap<Key, T>::remove;
-    using QMap<Key, T>::count;
-    using QMap<Key, T>::find;
-    using QMap<Key, T>::constFind;
-    using QMap<Key, T>::values;
-    using QMap<Key, T>::size;
-    using QMap<Key, T>::detach;
-    using QMap<Key, T>::erase;
-    using QMap<Key, T>::isValidIterator;
-    using typename QMap<Key, T>::Node;
-
-    bool contains(const Key &key, const T &value) const;
-
-    qsizetype remove(const Key &key, const T &value);
-
-    qsizetype count(const Key &key, const T &value) const;
-
-    typename QMap<Key, T>::iterator find(const Key &key, const T &value) {
-        typename QMap<Key, T>::iterator i(find(key));
-        typename QMap<Key, T>::iterator end(this->end());
-        while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
-            if (i.value() == value)
-                return i;
+    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 MapData::Map::iterator i;
+        explicit iterator(typename MapData::Map::iterator it) : i(it) {}
+    public:
+        typedef std::bidirectional_iterator_tag iterator_category;
+        typedef qptrdiff difference_type;
+        typedef T value_type;
+        typedef T *pointer;
+        typedef T &reference;
+
+        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;
         }
-        return end;
-    }
-    typename QMap<Key, T>::const_iterator find(const Key &key, const T &value) const {
-        typename QMap<Key, T>::const_iterator i(constFind(key));
-        typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());
-        while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
-            if (i.value() == value)
-                return i;
+        iterator operator++(int)
+        {
+            iterator r = *this;
             ++i;
+            return r;
         }
-        return end;
-    }
-    typename QMap<Key, T>::const_iterator constFind(const Key &key, const T &value) const
-        { return find(key, value); }
-private:
-    T &operator[](const Key &key);
-    const T operator[](const Key &key) const;
-};
-
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE QList<Key> QMultiMap<Key, T>::uniqueKeys() const
-{
-    QList<Key> res;
-    res.reserve(size()); // May be too much, but assume short lifetime
-    typename QMap<Key, T>::const_iterator i = this->begin();
-    if (i != this->end()) {
-        for (;;) {
-            const Key &aKey = i.key();
-            res.append(aKey);
-            do {
-                if (++i == this->end())
-                    goto break_out_of_outer_loop;
-            } while (!qMapLessThanKey(aKey, i.key()));   // loop while (key == i.key())
+        iterator &operator--()
+        {
+            --i;
+            return *this;
         }
-    }
-break_out_of_outer_loop:
-    return res;
-}
+        iterator operator--(int)
+        {
+            iterator r = *this;
+            --i;
+            return r;
+        }
+    };
 
-template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE QList<T> QMultiMap<Key, T>::values(const Key &akey) const
-{
-    QList<T> res;
-    Node *n = this->d->findNode(akey);
-    if (n) {
-        typename QMap<Key, T>::const_iterator it(n);
-        do {
-            res.append(*it);
-            ++it;
-        } while (it != this->constEnd() && !qMapLessThanKey<Key>(akey, it.key()));
-    }
-    return res;
-}
+    class const_iterator
+    {
+        friend class QMultiMap<Key, T>;
+        typename MapData::Map::const_iterator i;
+        explicit const_iterator(typename MapData::Map::const_iterator it) : i(it) {}
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMultiMap<Key, T>::insert(const Key &akey,
-                                                                            const T &avalue)
-{
-    detach();
-    Node* y = this->d->end();
-    Node* x = static_cast<Node *>(this->d->root());
-    bool left = true;
-    while (x != nullptr) {
-        left = !qMapLessThanKey(x->key, akey);
-        y = x;
-        x = left ? x->leftNode() : x->rightNode();
-    }
-    Node *z = this->d->createNode(akey, avalue, y, left);
-    return typename QMap<Key, T>::iterator(z);
-}
+    public:
+        typedef std::bidirectional_iterator_tag iterator_category;
+        typedef qptrdiff difference_type;
+        typedef T value_type;
+        typedef const T *pointer;
+        typedef const T &reference;
 
-#ifndef Q_CLANG_QDOC
-template <class Key, class T>
-typename QMap<Key, T>::iterator QMultiMap<Key, T>::insert(typename QMap<Key, T>::const_iterator pos,
-                                                          const Key &akey, const T &avalue)
-{
-    if (this->d->ref.isShared())
-        return insert(akey, avalue);
-
-    Q_ASSERT_X(isValidIterator(pos), "QMap::insert", "The specified const_iterator argument 'pos' is invalid");
-
-    if (pos == this->constEnd()) {
-        // Hint is that the Node is larger than (or equal to) the largest value.
-        Node *n = static_cast<Node *>(pos.i->left);
-        if (n) {
-            while (n->right)
-                n = static_cast<Node *>(n->right);
-
-            if (!qMapLessThanKey(n->key, akey))
-                return insert(akey, avalue); // ignore hint
-            Node *z = this->d->createNode(akey, avalue, n, false); // insert right most
-            return typename QMap<Key, T>::iterator(z);
+        const_iterator() = default;
+        /* 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;
         }
-        return insert(akey, avalue);
-    } else {
-        // Hint indicates that the node should be less (or equal to) the hint given
-        // but larger than the previous value.
-        Node *next = const_cast<Node*>(pos.i);
-        if (qMapLessThanKey(next->key, akey))
-            return insert(akey, avalue); // ignore hint
-
-        if (pos == this->constBegin()) {
-            // There is no previous value (insert left most)
-            Node *z = this->d->createNode(akey, avalue, this->begin().i, true);
-            return typename QMap<Key, T>::iterator(z);
-        } else {
-            Node *prev = const_cast<Node*>(pos.i->previousNode());
-            if (!qMapLessThanKey(prev->key, akey))
-                return insert(akey, avalue); // ignore hint
-
-            // Hint is ok - do insert
-            if (prev->right == nullptr) {
-                Node *z = this->d->createNode(akey, avalue, prev, false);
-                return typename QMap<Key, T>::iterator(z);
-            }
-            if (next->left == nullptr) {
-                Node *z = this->d->createNode(akey, avalue, next, true);
-                return typename QMap<Key, T>::iterator(z);
-            }
-            Q_ASSERT(false); // We should have prev->right == nullptr or next->left == nullptr.
-            return insert(akey, avalue);
+        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;
+        }
+    };
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE QMultiMap<Key, T> &QMultiMap<Key, T>::unite(const QMultiMap<Key, T> &other)
-{
-    QMultiMap<Key, T> copy(other);
-    typename QMap<Key, T>::const_iterator it = copy.constEnd();
-    const typename QMap<Key, T>::const_iterator b = copy.constBegin();
-    while (it != b) {
-        --it;
-        insert(it.key(), it.value());
-    }
-    return *this;
-}
-#endif // Q_CLANG_QDOC
+    class key_iterator
+    {
+        const_iterator i;
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const
-{
-    return constFind(key, value) != QMap<Key, T>::constEnd();
-}
+    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;
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE qsizetype QMultiMap<Key, T>::remove(const Key &key, const T &value)
-{
-    qsizetype n = 0;
-    typename QMap<Key, T>::iterator i(find(key));
-    typename QMap<Key, T>::iterator end(QMap<Key, T>::end());
-    while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
-        if (i.value() == value) {
-            i = erase(i);
-            ++n;
-        } else {
+        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()); }
+
+    iterator erase(const_iterator it)
+    {
+        if (!d)
+            return iterator();
+
+        if (!d.isShared())
+            return iterator(d->m.erase(it.i));
+
+        auto newData = new MapData;
+        const auto newDataEnd = newData->m.end();
+
+        auto i = d->m.begin();
+        auto e = d->m.end();
+        size_type steps = 0;
+
+        while (i != it.i) {
+            newData->m.insert(newDataEnd, *i);
             ++i;
+            ++steps;
         }
+
+        if (i != e)
+            ++i;
+
+        while (i != e)
+            newData->m.insert(newDataEnd, *i++);
+
+        d.reset(newData);
+
+        auto result = std::next(d->m.begin(), steps);
+        return iterator(result);
     }
-    return n;
-}
 
-template <class Key, class T>
-Q_INLINE_TEMPLATE qsizetype QMultiMap<Key, T>::count(const Key &key, const T &value) const
-{
-    qsizetype n = 0;
-    typename QMap<Key, T>::const_iterator i(constFind(key));
-    typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());
-    while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
-        if (i.value() == value)
-            ++n;
-        ++i;
-    }
-    return n;
-}
+    // more Qt
+    typedef iterator Iterator;
+    typedef const_iterator ConstIterator;
 
-#if QT_DEPRECATED_SINCE(5, 15)
-template<class Key, class T>
-QList<Key> QMap<Key, T>::uniqueKeys() const
-{
-    return static_cast<const QMultiMap<Key, T> *>(this)->uniqueKeys();
-}
+    size_type count() const
+    {
+        return size();
+    }
 
-template<class Key, class T>
-QList<T> QMap<Key, T>::values(const Key &key) const
+    iterator find(const Key &key)
+    {
+        detach();
+        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 find(const Key &key, const T &value)
+    {
+        if (!d)
+            return iterator();
+
+        auto range = d->m.equal_range(key);
+        auto i = std::find_if(range.first, range.second,
+                              MapData::valueIsEqualTo(value));
+
+        return iterator(i);
+    }
+
+    const_iterator find(const Key &key, const T &value) const
+    {
+        if (!d)
+            return const_iterator();
+        // a bit evil, but effective
+        return const_iterator(const_cast<QMultiMap *>(this)->find(key, value));
+    }
+
+    const_iterator constFind(const Key &key, const T &value) const
+    {
+        return find(key, value);
+    }
+
+    iterator lowerBound(const Key &key)
+    {
+        detach();
+        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)
+    {
+        detach();
+        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)
+    {
+        detach();
+        // 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)
+    {
+        auto posDistance = d ? std::distance(d->m.cbegin(), pos.i) : 0;
+        detach();
+        auto detachedPos = std::next(d->m.cbegin(), posDistance);
+        return iterator(d->m.insert(detachedPos, {key, value}));
+    }
+
+    // CHANGE: provide insertMulti for compatibility
+    iterator insertMulti(const Key &key, const T &value)
+    {
+        return insert(key, value);
+    }
+
+    iterator insertMulti(const_iterator pos, const Key &key, const T &value)
+    {
+        return insert(pos, key, value);
+    }
+
+    void insert(const QMultiMap<Key, T> &map)
+    {
+        if (map.isEmpty())
+            return;
+
+        detach();
+
+        auto copy = map.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);
+    }
+
+    void insert(QMultiMap<Key, T> &&map)
+    {
+        if (!map.d || map.d->m.empty())
+            return;
+
+        detach();
+
+#ifdef __cpp_lib_node_extract
+        map.d->m.merge(std::move(d->m));
+#else
+        map.d->m.insert(std::make_move_iterator(d->m.begin()),
+                        std::make_move_iterator(d->m.end()));
+#endif
+        *this = std::move(map);
+    }
+
+    iterator replace(const Key &key, const T &value)
+    {
+        // TODO: improve. No need of copying and then overwriting.
+        detach();
+
+        // Similarly, improve here (e.g. lower_bound and hinted insert);
+        // there's no insert_or_assign on multimaps
+        auto i = d->m.find(key);
+        if (i != d->m.end())
+            i->second = value;
+        else
+            i = d->m.insert({key, value});
+
+        return iterator(i);
+    }
+
+    // STL compatibility
+    inline bool empty() const { return isEmpty(); }
+
+    QPair<iterator, iterator> equal_range(const Key &akey)
+    {
+        detach();
+        auto result = d->m.equal_range(akey);
+        return {iterator(result.first), iterator(result.second)};
+    }
+
+    QPair<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)
+    {
+        insert(other);
+        return *this;
+    }
+};
+
+Q_DECLARE_ASSOCIATIVE_ITERATOR(MultiMap)
+Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(MultiMap)
+
+template <typename AKey, typename AT>
+QTypeTraits::compare_eq_result<AKey, AT> operator==(const QMultiMap<AKey, AT> &lhs, const QMultiMap<AKey, AT> &rhs)
 {
-    return static_cast<const QMultiMap<Key, T> *>(this)->values(key);
+    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();
 }
 
-template<class Key, class T>
-typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &key, const T &value)
+template <typename AKey, typename AT>
+QTypeTraits::compare_eq_result<AKey, AT> operator!=(const QMultiMap<AKey, AT> &lhs, const QMultiMap<AKey, AT> &rhs)
 {
-    return static_cast<QMultiMap<Key, T> *>(this)->insert(key, value);
+    return !(lhs == rhs);
 }
 
-template<class Key, class T>
-typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const_iterator pos, const Key &akey, const T &avalue)
+template <typename Key, typename T>
+QMultiMap<Key, T> operator+(const QMultiMap<Key, T> &lhs, const QMultiMap<Key, T> &rhs)
 {
-    return static_cast<QMultiMap<Key, T> *>(this)->insert(pos, akey, avalue);
+    auto result = lhs;
+    result += rhs;
+    return result;
 }
 
-template<class Key, class T>
-QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other)
+template <typename Key, typename T>
+QMultiMap<Key, T> operator+=(QMultiMap<Key, T> &lhs, const QMultiMap<Key, T> &rhs)
 {
-    return static_cast<QMultiMap<Key, T> *>(this)->unite(other);
+    return lhs.unite(rhs);
 }
-#endif
-
-Q_DECLARE_ASSOCIATIVE_ITERATOR(Map)
-Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map)
 
 QT_END_NAMESPACE
 
diff --git a/src/corelib/tools/qmap.cpp b/src/corelib/tools/qmap.qdoc
index 279dacda0b..09798620b7 100644
--- a/src/corelib/tools/qmap.cpp
+++ b/src/corelib/tools/qmap.qdoc
@@ -1,5 +1,6 @@
 /****************************************************************************
 **
+** Copyright (C) 2020 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
 ** Copyright (C) 2016 The Qt Company Ltd.
 ** Contact: https://www.qt.io/licensing/
 **
@@ -37,348 +38,10 @@
 **
 ****************************************************************************/
 
-#include "qmap.h"
-
-#include <stdlib.h>
-
-#ifdef QT_QMAP_DEBUG
-# include <qstring.h>
-# include <qlist.h>
-#endif
-
-QT_BEGIN_NAMESPACE
-
-const QMapDataBase QMapDataBase::shared_null = { Q_REFCOUNT_INITIALIZE_STATIC, 0, { 0, nullptr, nullptr }, nullptr };
-
-const QMapNodeBase *QMapNodeBase::nextNode() const
-{
-    const QMapNodeBase *n = this;
-    if (n->right) {
-        n = n->right;
-        while (n->left)
-            n = n->left;
-    } else {
-        const QMapNodeBase *y = n->parent();
-        while (y && n == y->right) {
-            n = y;
-            y = n->parent();
-        }
-        n = y;
-    }
-    return n;
-}
-
-const QMapNodeBase *QMapNodeBase::previousNode() const
-{
-    const QMapNodeBase *n = this;
-    if (n->left) {
-        n = n->left;
-        while (n->right)
-            n = n->right;
-    } else {
-        const QMapNodeBase *y = n->parent();
-        while (y && n == y->left) {
-            n = y;
-            y = n->parent();
-        }
-        n = y;
-    }
-    return n;
-}
-
-
-void QMapDataBase::rotateLeft(QMapNodeBase *x)
-{
-    QMapNodeBase *&root = header.left;
-    QMapNodeBase *y = x->right;
-    x->right = y->left;
-    if (y->left != nullptr)
-        y->left->setParent(x);
-    y->setParent(x->parent());
-    if (x == root)
-        root = y;
-    else if (x == x->parent()->left)
-        x->parent()->left = y;
-    else
-        x->parent()->right = y;
-    y->left = x;
-    x->setParent(y);
-}
-
-
-void QMapDataBase::rotateRight(QMapNodeBase *x)
-{
-    QMapNodeBase *&root = header.left;
-    QMapNodeBase *y = x->left;
-    x->left = y->right;
-    if (y->right != nullptr)
-        y->right->setParent(x);
-    y->setParent(x->parent());
-    if (x == root)
-        root = y;
-    else if (x == x->parent()->right)
-        x->parent()->right = y;
-    else
-        x->parent()->left = y;
-    y->right = x;
-    x->setParent(y);
-}
-
-
-void QMapDataBase::rebalance(QMapNodeBase *x)
-{
-    QMapNodeBase *&root = header.left;
-    x->setColor(QMapNodeBase::Red);
-    while (x != root && x->parent()->color() == QMapNodeBase::Red) {
-        if (x->parent() == x->parent()->parent()->left) {
-            QMapNodeBase *y = x->parent()->parent()->right;
-            if (y && y->color() == QMapNodeBase::Red) {
-                x->parent()->setColor(QMapNodeBase::Black);
-                y->setColor(QMapNodeBase::Black);
-                x->parent()->parent()->setColor(QMapNodeBase::Red);
-                x = x->parent()->parent();
-            } else {
-                if (x == x->parent()->right) {
-                    x = x->parent();
-                    rotateLeft(x);
-                }
-                x->parent()->setColor(QMapNodeBase::Black);
-                x->parent()->parent()->setColor(QMapNodeBase::Red);
-                rotateRight (x->parent()->parent());
-            }
-        } else {
-            QMapNodeBase *y = x->parent()->parent()->left;
-            if (y && y->color() == QMapNodeBase::Red) {
-                x->parent()->setColor(QMapNodeBase::Black);
-                y->setColor(QMapNodeBase::Black);
-                x->parent()->parent()->setColor(QMapNodeBase::Red);
-                x = x->parent()->parent();
-            } else {
-                if (x == x->parent()->left) {
-                    x = x->parent();
-                    rotateRight(x);
-                }
-                x->parent()->setColor(QMapNodeBase::Black);
-                x->parent()->parent()->setColor(QMapNodeBase::Red);
-                rotateLeft(x->parent()->parent());
-            }
-        }
-    }
-    root->setColor(QMapNodeBase::Black);
-}
-
-void QMapDataBase::freeNodeAndRebalance(QMapNodeBase *z)
-{
-    QMapNodeBase *&root = header.left;
-    QMapNodeBase *y = z;
-    QMapNodeBase *x;
-    QMapNodeBase *x_parent;
-    if (y->left == nullptr) {
-        x = y->right;
-        if (y == mostLeftNode) {
-            if (x)
-                mostLeftNode = x; // It cannot have (left) children due the red black invariant.
-            else
-                mostLeftNode = y->parent();
-        }
-    } else {
-        if (y->right == nullptr) {
-            x = y->left;
-        } else {
-            y = y->right;
-            while (y->left != nullptr)
-                y = y->left;
-            x = y->right;
-        }
-    }
-    if (y != z) {
-        z->left->setParent(y);
-        y->left = z->left;
-        if (y != z->right) {
-            x_parent = y->parent();
-            if (x)
-                x->setParent(y->parent());
-            y->parent()->left = x;
-            y->right = z->right;
-            z->right->setParent(y);
-        } else {
-            x_parent = y;
-        }
-        if (root == z)
-            root = y;
-        else if (z->parent()->left == z)
-            z->parent()->left = y;
-        else
-            z->parent()->right = y;
-        y->setParent(z->parent());
-        // Swap the colors
-        QMapNodeBase::Color c = y->color();
-        y->setColor(z->color());
-        z->setColor(c);
-        y = z;
-    } else {
-        x_parent = y->parent();
-        if (x)
-            x->setParent(y->parent());
-        if (root == z)
-            root = x;
-        else if (z->parent()->left == z)
-            z->parent()->left = x;
-        else
-            z->parent()->right = x;
-    }
-    if (y->color() != QMapNodeBase::Red) {
-        while (x != root && (x == nullptr || x->color() == QMapNodeBase::Black)) {
-            if (x == x_parent->left) {
-                QMapNodeBase *w = x_parent->right;
-                if (w->color() == QMapNodeBase::Red) {
-                    w->setColor(QMapNodeBase::Black);
-                    x_parent->setColor(QMapNodeBase::Red);
-                    rotateLeft(x_parent);
-                    w = x_parent->right;
-                }
-                if ((w->left == nullptr || w->left->color() == QMapNodeBase::Black) &&
-                    (w->right == nullptr || w->right->color() == QMapNodeBase::Black)) {
-                    w->setColor(QMapNodeBase::Red);
-                    x = x_parent;
-                    x_parent = x_parent->parent();
-                } else {
-                    if (w->right == nullptr || w->right->color() == QMapNodeBase::Black) {
-                        if (w->left)
-                            w->left->setColor(QMapNodeBase::Black);
-                        w->setColor(QMapNodeBase::Red);
-                        rotateRight(w);
-                        w = x_parent->right;
-                    }
-                    w->setColor(x_parent->color());
-                    x_parent->setColor(QMapNodeBase::Black);
-                    if (w->right)
-                        w->right->setColor(QMapNodeBase::Black);
-                    rotateLeft(x_parent);
-                    break;
-                }
-            } else {
-            QMapNodeBase *w = x_parent->left;
-            if (w->color() == QMapNodeBase::Red) {
-                w->setColor(QMapNodeBase::Black);
-                x_parent->setColor(QMapNodeBase::Red);
-                rotateRight(x_parent);
-                w = x_parent->left;
-            }
-            if ((w->right == nullptr || w->right->color() == QMapNodeBase::Black) &&
-                (w->left == nullptr|| w->left->color() == QMapNodeBase::Black)) {
-                w->setColor(QMapNodeBase::Red);
-                x = x_parent;
-                x_parent = x_parent->parent();
-            } else {
-                if (w->left == nullptr || w->left->color() == QMapNodeBase::Black) {
-                    if (w->right)
-                        w->right->setColor(QMapNodeBase::Black);
-                    w->setColor(QMapNodeBase::Red);
-                    rotateLeft(w);
-                    w = x_parent->left;
-                }
-                w->setColor(x_parent->color());
-                x_parent->setColor(QMapNodeBase::Black);
-                if (w->left)
-                    w->left->setColor(QMapNodeBase::Black);
-                rotateRight(x_parent);
-                break;
-            }
-        }
-    }
-    if (x)
-        x->setColor(QMapNodeBase::Black);
-    }
-    free(y);
-    --size;
-}
-
-void QMapDataBase::recalcMostLeftNode()
-{
-    mostLeftNode = &header;
-    while (mostLeftNode->left)
-        mostLeftNode = mostLeftNode->left;
-}
-
-static inline size_t qMapAlignmentThreshold()
-{
-    // malloc on 32-bit platforms should return pointers that are 8-byte
-    // aligned or more while on 64-bit platforms they should be 16-byte aligned
-    // or more
-    return 2 * sizeof(void*);
-}
-
-static inline void *qMapAllocate(size_t alloc, size_t alignment)
-{
-    return alignment > qMapAlignmentThreshold()
-        ? qMallocAligned(alloc, alignment)
-        : ::malloc(alloc);
-}
-
-static inline void qMapDeallocate(QMapNodeBase *node, size_t alignment)
-{
-    if (alignment > qMapAlignmentThreshold())
-        qFreeAligned(node);
-    else
-        ::free(node);
-}
-
-QMapNodeBase *QMapDataBase::createNode(size_t alloc, size_t alignment, QMapNodeBase *parent, bool left)
-{
-    QMapNodeBase *node = static_cast<QMapNodeBase *>(qMapAllocate(alloc, alignment));
-    Q_CHECK_PTR(node);
-
-    memset(node, 0, alloc);
-    ++size;
-
-    if (parent) {
-        if (left) {
-            parent->left = node;
-            if (parent == mostLeftNode)
-                mostLeftNode = node;
-        } else {
-            parent->right = node;
-        }
-        node->setParent(parent);
-        rebalance(node);
-    }
-    return node;
-}
-
-void QMapDataBase::freeTree(QMapNodeBase *root, size_t alignment)
-{
-    if (root->left)
-        freeTree(root->left, alignment);
-    if (root->right)
-        freeTree(root->right, alignment);
-    qMapDeallocate(root, alignment);
-}
-
-QMapDataBase *QMapDataBase::createData()
-{
-    QMapDataBase *d = new QMapDataBase;
-
-    d->ref.initializeOwned();
-    d->size = 0;
-
-    d->header.p = 0;
-    d->header.left = nullptr;
-    d->header.right = nullptr;
-    d->mostLeftNode = &(d->header);
-
-    return d;
-}
-
-void QMapDataBase::freeData(QMapDataBase *d)
-{
-    delete d;
-}
-
 /*!
     \class QMap
     \inmodule QtCore
-    \brief The QMap class is a template class that provides a red-black-tree-based dictionary.
+    \brief The QMap class is a template class that provides an associative array.
 
     \ingroup tools
     \ingroup shared
@@ -468,14 +131,13 @@ void QMapDataBase::freeData(QMapDataBase *d)
     \snippet code/src_corelib_tools_qmap.cpp 9
 
     However, you can store multiple values per key by using
-    using the subclass QMultiMap. If you want
+    QMultiMap. If you want
     to retrieve all the values for a single key, you can use
     values(const Key &key), which returns a QList<T>:
 
     \snippet code/src_corelib_tools_qmap.cpp 10
 
-    The items that share the same key are available from most
-    recently to least recently inserted. Another approach is to call
+    Another approach is to call
     find() to get the STL-style iterator for the first item with a
     key and iterate from there:
 
@@ -496,7 +158,7 @@ void QMapDataBase::freeData(QMapDataBase *d)
     but the compiler won't let you, for example, store a QWidget as a
     value; instead, store a QWidget *. In addition, QMap's key type
     must provide operator<(). QMap uses it to keep its items sorted,
-    and assumes that two keys \c x and \c y are equal if neither \c{x
+    and assumes that two keys \c x and \c y are equivalent if neither \c{x
     < y} nor \c{y < x} is true.
 
     Example:
@@ -515,15 +177,6 @@ void QMapDataBase::freeData(QMapDataBase *d)
     \sa clear()
 */
 
-/*!
-    \fn template <class Key, class T> QMap<Key, T>::QMap(QMap<Key, T> &&other)
-
-    Move-constructs a QMap instance, making it point at the same
-    object that \a other was pointing to.
-
-    \since 5.2
-*/
-
 /*! \fn template <class Key, class T> QMap<Key, T>::QMap(const QMap<Key, T> &other)
 
     Constructs a copy of \a other.
@@ -533,29 +186,28 @@ void QMapDataBase::freeData(QMapDataBase *d)
     function very fast. If a shared instance is modified, it will be
     copied (copy-on-write), and this takes \l{linear time}.
 
-    \sa operator=()
+    \sa operator=
 */
 
-/*! \fn template <class Key, class T> QMap<Key, T>::QMap(const typename std::map<Key, T> & other)
+/*!
+    \fn template <class Key, class T> QMap<Key, T>::QMap(QMap<Key, T> &&other)
 
-    Constructs a copy of \a other.
+    Move-constructs a QMap instance.
 
-    \sa toStdMap()
+    \since 5.2
 */
 
-/*! \fn template <class Key, class T> QMap<Key, T>::QMap(std::initializer_list<std::pair<Key,T> > list)
-    \since 5.1
-
-    Constructs a map with a copy of each of the elements in the
-    initializer list \a list.
+/*! \fn template <class Key, class T> QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other)
 
-    This function is only available if the program is being
-    compiled in C++11 mode.
+    Assigns \a other to this map and returns a reference to this map.
 */
 
-/*! \fn template <class Key, class T> std::map<Key, T> QMap<Key, T>::toStdMap() const
+/*!
+    \fn template <class Key, class T> QMap<Key, T> &QMap<Key, T>::operator=(QMap<Key, T> &&other)
 
-    Returns an STL map equivalent to this QMap.
+    Move-assigns \a other to this QMap instance.
+
+    \since 5.2
 */
 
 /*! \fn template <class Key, class T> QMap<Key, T>::~QMap()
@@ -564,62 +216,70 @@ void QMapDataBase::freeData(QMapDataBase *d)
     iterators over this map, become invalid.
 */
 
-/*! \fn template <class Key, class T> QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other)
+/*! \fn template <class Key, class T> void QMap<Key, T>::swap(QMap<Key, T> &other) noexcept
+    \since 4.8
 
-    Assigns \a other to this map and returns a reference to this map.
+    Swaps map \a other with this map. This operation is very
+    fast and never fails.
 */
 
-/*!
-    \fn template <class Key, class T> QMap<Key, T> &QMap<Key, T>::operator=(QMap<Key, T> &&other)
+/*! \fn template <class Key, class T> QMap<Key, T>::QMap(std::initializer_list<std::pair<Key,T> > list)
+    \since 5.1
 
-    Move-assigns \a other to this QMap instance.
+    Constructs a map with a copy of each of the elements in the
+    initializer list \a list.
+*/
 
-    \since 5.2
+/*! \fn template <class Key, class T> QMap<Key, T>::QMap(const std::map<Key, T> & other)
+
+    Constructs a copy of \a other.
+
+    \sa toStdMap()
 */
 
-/*! \fn template <class Key, class T> void QMap<Key, T>::swap(QMap<Key, T> &other)
-    \since 4.8
+/*! \fn template <class Key, class T> QMap<Key, T>::QMap(std::map<Key, T> && other)
 
-    Swaps map \a other with this map. This operation is very
-    fast and never fails.
+    Constructs a map by moving from \a other.
+
+    \sa toStdMap()
 */
 
-/*! \fn template <class Key, class T> void QMultiMap<Key, T>::swap(QMultiMap<Key, T> &other)
-    \since 4.8
+/*! \fn template <class Key, class T> std::map<Key, T> QMap<Key, T>::toStdMap() const
 
-    Swaps map \a other with this map. This operation is very
-    fast and never fails.
+    Returns an STL map equivalent to this QMap.
 */
 
-/*! \fn template <class Key, class T> bool QMap<Key, T>::operator==(const QMap<Key, T> &other) const
+/*! \fn template <class Key, class T> bool operator==(const QMap<Key, T> &lhs, const QMap<Key, T> &rhs) const
+    \relates QMap
 
-    Returns \c true if \a other is equal to this map; otherwise returns
+    Returns \c true if \a lhs is equal to \a rhs; otherwise returns
     false.
 
     Two maps are considered equal if they contain the same (key,
     value) pairs.
 
-    This function requires the value type to implement \c
+    This function requires the key and the value types to implement \c
     operator==().
 
     \sa operator!=()
 */
 
-/*! \fn template <class Key, class T> bool QMap<Key, T>::operator!=(const QMap<Key, T> &other) const
+/*! \fn template <class Key, class T> bool operator!=(const QMap<Key, T> &lhs, const QMap<Key, T> &rhs) const
+    \relates QMap
 
-    Returns \c true if \a other is not equal to this map; otherwise
-    returns \c false.
+    Returns \c true if \a lhs is not equal to \a rhs; otherwise returns
+    false.
 
     Two maps are considered equal if they contain the same (key,
     value) pairs.
 
-    This function requires the value type to implement \c
+    This function requires the key and the value types to implement \c
     operator==().
 
     \sa operator==()
 */
 
-/*! \fn template <class Key, class T> qsizetype QMap<Key, T>::size() const
+/*! \fn template <class Key, class T> size_type QMap<Key, T>::size() const
 
     Returns the number of (key, value) pairs in the map.
 
@@ -655,11 +315,6 @@ void QMapDataBase::freeData(QMapDataBase *d)
     \sa detach()
 */
 
-/*! \fn template <class Key, class T> void QMap<Key, T>::setSharable(bool sharable)
-
-    \internal
-*/
-
 /*! \fn template <class Key, class T> bool QMap<Key, T>::isSharedWith(const QMap<Key, T> &other) const
 
     \internal
@@ -672,13 +327,13 @@ void QMapDataBase::freeData(QMapDataBase *d)
     \sa remove()
 */
 
-/*! \fn template <class Key, class T> qsizetype QMap<Key, T>::remove(const Key &key)
+/*! \fn template <class Key, class T> size_type QMap<Key, T>::remove(const Key &key)
 
     Removes all the items that have the key \a key from the map.
     Returns the number of items removed which will be 1 if the key
     exists in the map, and 0 otherwise.
 
-    \sa clear(), take(), QMultiMap::remove()
+    \sa clear(), take()
 */
 
 /*! \fn template <class Key, class T> T QMap<Key, T>::take(const Key &key)
@@ -701,7 +356,24 @@ void QMapDataBase::freeData(QMapDataBase *d)
     Returns \c true if the map contains an item with key \a key;
     otherwise returns \c false.
 
-    \sa count(), QMultiMap::contains()
+    \sa count()
+*/
+
+/*!
+    \fn template <class Key, class T> Key QMap<Key, T>::key(const T &value, const Key &defaultKey) const
+    \since 4.3
+    \overload
+
+    Returns the first key with value \a value, or \a defaultKey if
+    the map contains no item with value \a value. If no \a defaultKey
+    is provided the function returns a
+    \l{default-constructed value}{default-constructed key}.
+
+    This function can be slow (\l{linear time}), because QMap's
+    internal data structure is optimized for fast lookup by key, not
+    by value.
+
+    \sa value(), keys()
 */
 
 /*! \fn template <class Key, class T> T QMap<Key, T>::value(const Key &key, const T &defaultValue) const
@@ -710,9 +382,7 @@ void QMapDataBase::freeData(QMapDataBase *d)
 
     If the map contains no item with key \a key, the function returns
     \a defaultValue. If no \a defaultValue is specified, the function
-    returns a \l{default-constructed value}. If there are multiple
-    items for \a key in the map, the value of the most recently
-    inserted one is returned.
+    returns a \l{default-constructed value}.
 
     \sa key(), values(), contains(), operator[]()
 */
@@ -731,31 +401,17 @@ void QMapDataBase::freeData(QMapDataBase *d)
     \sa insert(), value()
 */
 
-/*! \fn template <class Key, class T> const T QMap<Key, T>::operator[](const Key &key) const
+/*! \fn template <class Key, class T> T QMap<Key, T>::operator[](const Key &key) const
 
     \overload
 
     Same as value().
 */
 
-/*! \fn template <class Key, class T> QList<Key> QMap<Key, T>::uniqueKeys() const
-    \since 4.2
-    \obsolete Use QMultiMap for storing multiple values with the same key.
-
-    Returns a list containing all the keys in the map in ascending
-    order. Keys that occur multiple times in the map (because items
-    were inserted with insertMulti(), or unite() was used) occur only
-    once in the returned list.
-
-    \sa QMultiMap::uniqueKeys()
-*/
-
 /*! \fn template <class Key, class T> QList<Key> QMap<Key, T>::keys() const
 
     Returns a list containing all the keys in the map in ascending
-    order. Keys that occur multiple times in the map (because the
-    method is operating on a QMultiMap) also occur multiple times
-    in the list.
+    order.
 
     The order is guaranteed to be the same as that used by values().
 
@@ -778,23 +434,6 @@ void QMapDataBase::freeData(QMapDataBase *d)
     by value.
 */
 
-/*!
-    \fn template <class Key, class T> Key QMap<Key, T>::key(const T &value, const Key &defaultKey) const
-    \since 4.3
-    \overload
-
-    Returns the first key with value \a value, or \a defaultKey if
-    the map contains no item with value \a value. If no \a defaultKey
-    is provided the function returns a
-    \l{default-constructed value}{default-constructed key}.
-
-    This function can be slow (\l{linear time}), because QMap's
-    internal data structure is optimized for fast lookup by key, not
-    by value.
-
-    \sa value(), keys()
-*/
-
 /*! \fn template <class Key, class T> QList<T> QMap<Key, T>::values() const
 
     Returns a list containing all the values in the map, in ascending
@@ -809,29 +448,74 @@ void QMapDataBase::freeData(QMapDataBase *d)
     \sa keys(), value()
 */
 
-/*! \fn template <class Key, class T> QList<T> QMap<Key, T>::values(const Key &key) const
+/*! \fn template <class Key, class T> size_type QMap<Key, T>::count(const Key &key) const
+
+    Returns the number of items associated with key \a key.
+
+    \sa contains()
+*/
+
+/*! \fn template <class Key, class T> size_type QMap<Key, T>::count() const
+
     \overload
-    \obsolete Use QMultiMap for maps storing multiple values with the same key.
 
-    Returns a list containing all the values associated with key
-    \a key, from the most recently inserted to the least recently
-    inserted one.
+    Same as size().
+*/
+
+/*! \fn template <class Key, class T> const Key &QMap<Key, T>::firstKey() const
+    \since 5.2
+
+    Returns a reference to the smallest key in the map.
+    This function assumes that the map is not empty.
 
-    \sa QMultiMap::values()
+    This executes in \l{constant time}.
+
+    \sa lastKey(), first(), keyBegin(), isEmpty()
 */
 
-/*! \fn template <class Key, class T> qsizetype QMap<Key, T>::count(const Key &key) const
+/*! \fn template <class Key, class T> const Key &QMap<Key, T>::lastKey() const
+    \since 5.2
 
-    Returns the number of items associated with key \a key.
+    Returns a reference to the largest key in the map.
+    This function assumes that the map is not empty.
 
-    \sa contains(), QMultiMap::count()
+    This executes in \l{logarithmic time}.
+
+    \sa firstKey(), last(), keyEnd(), isEmpty()
 */
 
-/*! \fn template <class Key, class T> qsizetype QMap<Key, T>::count() const
+/*! \fn template <class Key, class T> T &QMap<Key, T>::first()
+    \since 5.2
+
+    Returns a reference to the first value in the map, that is the value mapped
+    to the smallest key. This function assumes that the map is not empty.
+
+    When unshared (or const version is called), this executes in \l{constant time}.
+
+    \sa last(), firstKey(), isEmpty()
+*/
+
+/*! \fn template <class Key, class T> const T &QMap<Key, T>::first() const
+    \since 5.2
 
     \overload
+*/
 
-    Same as size().
+/*! \fn template <class Key, class T> T &QMap<Key, T>::last()
+    \since 5.2
+
+    Returns a reference to the last value in the map, that is the value mapped
+    to the largest key. This function assumes that the map is not empty.
+
+    When unshared (or const version is called), this executes in \l{logarithmic time}.
+
+    \sa first(), lastKey(), isEmpty()
+*/
+
+/*! \fn template <class Key, class T> const T &QMap<Key, T>::last() const
+    \since 5.2
+
+    \overload
 */
 
 /*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::begin()
@@ -967,63 +651,7 @@ void QMapDataBase::freeData(QMapDataBase *d)
     \sa constKeyValueBegin()
 */
 
-/*! \fn template <class Key, class T> const Key &QMap<Key, T>::firstKey() const
-    \since 5.2
-
-    Returns a reference to the smallest key in the map.
-    This function assumes that the map is not empty.
-
-    This executes in \l{constant time}.
-
-    \sa lastKey(), first(), keyBegin(), isEmpty()
-*/
-
-/*! \fn template <class Key, class T> const Key &QMap<Key, T>::lastKey() const
-    \since 5.2
-
-    Returns a reference to the largest key in the map.
-    This function assumes that the map is not empty.
-
-    This executes in \l{logarithmic time}.
-
-    \sa firstKey(), last(), keyEnd(), isEmpty()
-*/
-
-/*! \fn template <class Key, class T> T &QMap<Key, T>::first()
-    \since 5.2
-
-    Returns a reference to the first value in the map, that is the value mapped
-    to the smallest key. This function assumes that the map is not empty.
-
-    When unshared (or const version is called), this executes in \l{constant time}.
-
-    \sa last(), firstKey(), isEmpty()
-*/
-
-/*! \fn template <class Key, class T> const T &QMap<Key, T>::first() const
-    \since 5.2
-
-    \overload
-*/
-
-/*! \fn template <class Key, class T> T &QMap<Key, T>::last()
-    \since 5.2
-
-    Returns a reference to the last value in the map, that is the value mapped
-    to the largest key. This function assumes that the map is not empty.
-
-    When unshared (or const version is called), this executes in \l{logarithmic time}.
-
-    \sa first(), lastKey(), isEmpty()
-*/
-
-/*! \fn template <class Key, class T> const T &QMap<Key, T>::last() const
-    \since 5.2
-
-    \overload
-*/
-
-/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::erase(iterator pos)
+/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::erase(const_iterator pos)
 
     Removes the (key, value) pair pointed to by the iterator \a pos
     from the map, and returns an iterator to the next item in the
@@ -1040,15 +668,7 @@ void QMapDataBase::freeData(QMapDataBase *d)
     If the map contains no item with key \a key, the function
     returns end().
 
-    If the map contains multiple items with key \a key, this
-    function returns an iterator that points to the most recently
-    inserted value. The other values are accessible by incrementing
-    the iterator. For example, here's some code that iterates over all
-    the items with the same key:
-
-    \snippet code/src_corelib_tools_qmap.cpp 14
-
-    \sa constFind(), value(), values(), lowerBound(), upperBound(), QMultiMap::find()
+    \sa constFind(), value(), values(), lowerBound(), upperBound()
 */
 
 /*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &key) const
@@ -1065,7 +685,7 @@ void QMapDataBase::freeData(QMapDataBase *d)
     If the map contains no item with key \a key, the function
     returns constEnd().
 
-    \sa find(), QMultiMap::constFind()
+    \sa find()
 */
 
 /*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::lowerBound(const Key &key)
@@ -1075,17 +695,6 @@ void QMapDataBase::freeData(QMapDataBase *d)
     function returns an iterator to the nearest item with a greater
     key.
 
-    Example:
-    \snippet code/src_corelib_tools_qmap.cpp 15
-
-    If the map contains multiple items with key \a key, this
-    function returns an iterator that points to the most recently
-    inserted value. The other values are accessible by incrementing
-    the iterator. For example, here's some code that iterates over all
-    the items with the same key:
-
-    \snippet code/src_corelib_tools_qmap.cpp 16
-
     \sa upperBound(), find()
 */
 
@@ -1119,9 +728,6 @@ void QMapDataBase::freeData(QMapDataBase *d)
     If there is already an item with the key \a key, that item's value
     is replaced with \a value.
 
-    If there are multiple items with the key \a key, the most
-    recently inserted item's value is replaced with \a value.
-
     \sa QMultiMap::insert()
 */
 
@@ -1139,9 +745,6 @@ void QMapDataBase::freeData(QMapDataBase *d)
     If there is already an item with the key \a key, that item's value
     is replaced with \a value.
 
-    If there are multiple items with the key \a key, then exactly one of them
-    is replaced with \a value.
-
     If the hint is correct and the map is unshared, the insert executes in amortized \l{constant time}.
 
     When creating a map from sorted data inserting the largest key first with constBegin()
@@ -1168,50 +771,6 @@ void QMapDataBase::freeData(QMapDataBase *d)
     \sa QMultiMap::insert()
 */
 
-/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &key, const T &value)
-    \obsolete Use QMultiMap for storing multiple values with the same key.
-
-    Inserts a new item with the key \a key and a value of \a value.
-
-    If there is already an item with the same key in the map, this
-    function will simply create a new one. (This behavior is
-    different from insert(), which overwrites the value of an
-    existing item.)
-
-    \sa QMultiMap::insert()
-*/
-
-/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const_iterator pos, const Key &key, const T &value)
-    \overload
-    \since 5.1
-    \obsolete Use QMultiMap for storing multiple values with the same key.
-    Inserts a new item with the key \a key and value \a value and with hint \a pos
-    suggesting where to do the insert.
-
-    If constBegin() is used as hint it indicates that the \a key is less than any key in the map
-    while constEnd() suggests that the \a key is larger than any key in the map.
-    Otherwise the hint should meet the condition (\a pos - 1).key() < \a key <= pos.key().
-    If the hint \a pos is wrong it is ignored and a regular insertMulti is done.
-
-    If there is already an item with the same key in the map, this function will simply create a new one.
-
-    \b {Note:} Be careful with the hint. Providing an iterator from an older shared instance might
-    crash but there is also a risk that it will silently corrupt both the map and the \a pos map.
-
-    \sa QMultiMap::insert()
-*/
-
-
-/*! \fn template <class Key, class T> QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other)
-    \obsolete Use QMultiMap for storing multiple values with the same key.
-
-    Inserts all the items in the \a other map into this map. If a
-    key is common to both maps, the resulting map will contain the
-    key multiple times.
-
-    \sa QMultiMap::unite()
-*/
-
 /*! \typedef QMap::Iterator
 
     Qt-style synonym for QMap<Key, T>::iterator.
@@ -1266,7 +825,7 @@ void QMapDataBase::freeData(QMapDataBase *d)
 
 /*! \class QMap::iterator
     \inmodule QtCore
-    \brief The QMap::iterator class provides an STL-style non-const iterator for QMap and QMultiMap.
+    \brief The QMap::iterator class provides an STL-style non-const iterator for QMap.
 
     QMap features both \l{STL-style iterators} and \l{Java-style
     iterators}. The STL-style iterators are more low-level and more
@@ -1274,8 +833,8 @@ void QMapDataBase::freeData(QMapDataBase *d)
     and, for developers who already know STL, have the advantage of
     familiarity.
 
-    QMap\<Key, T\>::iterator allows you to iterate over a QMap (or
-    QMultiMap) and to modify the value (but not the key) stored under
+    QMap\<Key, T\>::iterator allows you to iterate over a QMap
+    and to modify the value (but not the key) stored under
     a particular key. If you want to iterate over a const QMap, you
     should use QMap::const_iterator. It is generally good practice to
     use QMap::const_iterator on a non-const QMap as well, unless you
@@ -1291,9 +850,7 @@ void QMapDataBase::freeData(QMapDataBase *d)
     \snippet code/src_corelib_tools_qmap.cpp 18
 
     Unlike QHash, which stores its items in an arbitrary order, QMap
-    stores its items ordered by key. Items that share the same key
-    (because the map is a QMultiMap) will appear consecutively,
-    from the most recently to the least recently inserted value.
+    stores its items ordered by key.
 
     Let's see a few examples of things we can do with a
     QMap::iterator that we cannot do with a QMap::const_iterator.
@@ -1370,11 +927,6 @@ void QMapDataBase::freeData(QMapDataBase *d)
     \sa QMap::begin(), QMap::end()
 */
 
-/*! \fn template <class Key, class T> QMap<Key, T>::iterator::iterator(Node *)
-
-    \internal
-*/
-
 /*! \fn template <class Key, class T> const Key &QMap<Key, T>::iterator::key() const
 
     Returns the current item's key as a const reference.
@@ -1434,7 +986,7 @@ void QMapDataBase::freeData(QMapDataBase *d)
     \sa operator==()
 */
 
-/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator++()
+/*! \fn template <class Key, class T> QMap<Key, T>::iterator &QMap<Key, T>::iterator::operator++()
 
     The prefix ++ operator (\c{++i}) advances the iterator to the
     next item in the map and returns an iterator to the new current
@@ -1454,7 +1006,7 @@ void QMapDataBase::freeData(QMapDataBase *d)
     current item.
 */
 
-/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator--()
+/*! \fn template <class Key, class T> QMap<Key, T>::iterator &QMap<Key, T>::iterator::operator--()
 
     The prefix -- operator (\c{--i}) makes the preceding item
     current and returns an iterator pointing to the new current item.
@@ -1474,46 +1026,9 @@ void QMapDataBase::freeData(QMapDataBase *d)
     current item.
 */
 
-/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator+(qsizetype j) const
-
-    Returns an iterator to the item at \a j positions forward from
-    this iterator. (If \a j is negative, the iterator goes backward.)
-
-    This operation can be slow for large \a j values.
-
-    \sa operator-()
-
-*/
-
-/*! \fn template <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::iterator::operator-(qsizetype j) const
-
-    Returns an iterator to the item at \a j positions backward from
-    this iterator. (If \a j is negative, the iterator goes forward.)
-
-    This operation can be slow for large \a j values.
-
-    \sa operator+()
-*/
-
-/*! \fn template <class Key, class T> QMap<Key, T>::iterator &QMap<Key, T>::iterator::operator+=(qsizetype j)
-
-    Advances the iterator by \a j items. (If \a j is negative, the
-    iterator goes backward.)
-
-    \sa operator-=(), operator+()
-*/
-
-/*! \fn template <class Key, class T> QMap<Key, T>::iterator &QMap<Key, T>::iterator::operator-=(qsizetype j)
-
-    Makes the iterator go back by \a j items. (If \a j is negative,
-    the iterator goes forward.)
-
-    \sa operator+=(), operator-()
-*/
-
 /*! \class QMap::const_iterator
     \inmodule QtCore
-    \brief The QMap::const_iterator class provides an STL-style const iterator for QMap and QMultiMap.
+    \brief The QMap::const_iterator class provides an STL-style const iterator for QMap.
 
     QMap features both \l{STL-style iterators} and \l{Java-style
     iterators}. The STL-style iterators are more low-level and more
@@ -1521,8 +1036,8 @@ void QMapDataBase::freeData(QMapDataBase *d)
     and, for developers who already know STL, have the advantage of
     familiarity.
 
-    QMap\<Key, T\>::const_iterator allows you to iterate over a QMap
-    (or a QMultiMap). If you want to modify the QMap as you iterate
+    QMap\<Key, T\>::const_iterator allows you to iterate over a QMap.
+    If you want to modify the QMap as you iterate
     over it, you must use QMap::iterator instead. It is generally
     good practice to use QMap::const_iterator on a non-const QMap as
     well, unless you need to change the QMap through the iterator.
@@ -1538,9 +1053,7 @@ void QMapDataBase::freeData(QMapDataBase *d)
     \snippet code/src_corelib_tools_qmap.cpp 24
 
     Unlike QHash, which stores its items in an arbitrary order, QMap
-    stores its items ordered by key. Items that share the same key
-    (because the map is a QMultiMap) will appear consecutively,
-    from the most recently to the least recently inserted value.
+    stores its items ordered by key.
 
     Multiple iterators can be used on the same map. If you add items
     to the map, existing iterators will remain valid. If you remove
@@ -1592,11 +1105,6 @@ void QMapDataBase::freeData(QMapDataBase *d)
     \sa QMap::constBegin(), QMap::constEnd()
 */
 
-/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator::const_iterator(const Node *)
-
-    \internal
-*/
-
 /*! \fn template <class Key, class T> QMap<Key, T>::const_iterator::const_iterator(const iterator &other)
 
     Constructs a copy of \a other.
@@ -1648,7 +1156,7 @@ void QMapDataBase::freeData(QMapDataBase *d)
     \sa operator==()
 */
 
-/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::const_iterator::operator++()
+/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator &QMap<Key, T>::const_iterator::operator++()
 
     The prefix ++ operator (\c{++i}) advances the iterator to the
     next item in the map and returns an iterator to the new current
@@ -1688,50 +1196,10 @@ void QMapDataBase::freeData(QMapDataBase *d)
     current item.
 */
 
-/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::const_iterator::operator+(qsizetype j) const
-
-    Returns an iterator to the item at \a j positions forward from
-    this iterator. (If \a j is negative, the iterator goes backward.)
-
-    This operation can be slow for large \a j values.
-
-    \sa operator-()
-*/
-
-/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator QMap<Key, T>::const_iterator::operator-(qsizetype j) const
-
-    Returns an iterator to the item at \a j positions backward from
-    this iterator. (If \a j is negative, the iterator goes forward.)
-
-    This operation can be slow for large \a j values.
-
-    \sa operator+()
-*/
-
-/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator &QMap<Key, T>::const_iterator::operator+=(qsizetype j)
-
-    Advances the iterator by \a j items. (If \a j is negative, the
-    iterator goes backward.)
-
-    This operation can be slow for large \a j values.
-
-    \sa operator-=(), operator+()
-*/
-
-/*! \fn template <class Key, class T> QMap<Key, T>::const_iterator &QMap<Key, T>::const_iterator::operator-=(qsizetype j)
-
-    Makes the iterator go back by \a j items. (If \a j is negative,
-    the iterator goes forward.)
-
-    This operation can be slow for large \a j values.
-
-    \sa operator+=(), operator-()
-*/
-
 /*! \class QMap::key_iterator
     \inmodule QtCore
     \since 5.6
-    \brief The QMap::key_iterator class provides an STL-style const iterator for QMap and QMultiMap keys.
+    \brief The QMap::key_iterator class provides an STL-style const iterator for QMap keys.
 
     QMap::key_iterator is essentially the same as QMap::const_iterator
     with the difference that operator*() and operator->() return a key
@@ -1859,7 +1327,7 @@ void QMapDataBase::freeData(QMapDataBase *d)
 /*! \typedef QMap::const_key_value_iterator
     \inmodule QtCore
     \since 5.10
-    \brief The QMap::const_key_value_iterator typedef provides an STL-style iterator for QMap and QMultiMap.
+    \brief The QMap::const_key_value_iterator typedef provides an STL-style iterator for QMap.
 
     QMap::const_key_value_iterator is essentially the same as QMap::const_iterator
     with the difference that operator*() returns a key/value pair instead of a
@@ -1871,7 +1339,7 @@ void QMapDataBase::freeData(QMapDataBase *d)
 /*! \typedef QMap::key_value_iterator
     \inmodule QtCore
     \since 5.10
-    \brief The QMap::key_value_iterator typedef provides an STL-style iterator for QMap and QMultiMap.
+    \brief The QMap::key_value_iterator typedef provides an STL-style iterator for QMap.
 
     QMap::key_value_iterator is essentially the same as QMap::iterator
     with the difference that operator*() returns a key/value pair instead of a
@@ -1901,240 +1369,3 @@ void QMapDataBase::freeData(QMapDataBase *d)
 
     \sa{Serializing Qt Data Types}{Format of the QDataStream operators}
 */
-
-/*! \class QMultiMap
-    \inmodule QtCore
-    \brief The QMultiMap class is a convenience QMap subclass that provides multi-valued maps.
-
-    \ingroup tools
-    \ingroup shared
-
-    \reentrant
-
-    QMultiMap\<Key, T\> is one of Qt's generic \l{container classes}.
-    It inherits QMap and extends it with a few functions
-    that make it able to store multi-valued maps. A multi-valued map
-    is a map that allows multiple values with the same key; QMap
-    doesn't allow that.
-
-    Because QMultiMap inherits QMap, all of QMap's functionality also
-    applies to QMultiMap. For example, you can use isEmpty() to test
-    whether the map is empty, and you can traverse a QMultiMap using
-    QMap's iterator classes (for example, QMapIterator). But in
-    addition, it provides an insert() function that inserts but does
-    not overwrite any previous value if the key already exists,
-    and a replace() function that corresponds which does overwite
-    an existing value if they key is already in the map.
-    It also provides convenient operator+() and operator+=().
-
-    Example:
-    \snippet code/src_corelib_tools_qmap.cpp 25
-
-    Unlike QMap, QMultiMap provides no operator[]. Use value() or
-    replace() if you want to access the most recently inserted item
-    with a certain key.
-
-    If you want to retrieve all the values for a single key, you can
-    use values(const Key &key), which returns a QList<T>:
-
-    \snippet code/src_corelib_tools_qmap.cpp 26
-
-    The items that share the same key are available from most
-    recently to least recently inserted.
-
-    If you prefer the STL-style iterators, you can call find() to get
-    the iterator for the first item with a key and iterate from
-    there:
-
-    \snippet code/src_corelib_tools_qmap.cpp 27
-
-    QMultiMap's key and value data types must be \l{assignable data
-    types}. This covers most data types you are likely to encounter,
-    but the compiler won't let you, for example, store a QWidget as a
-    value; instead, store a QWidget *. In addition, QMultiMap's key type
-    must provide operator<(). See the QMap documentation for details.
-
-    \sa QMap, QMapIterator, QMutableMapIterator, QMultiHash
-*/
-
-/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap()
-
-    Constructs an empty map.
-*/
-
-/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(std::initializer_list<std::pair<Key,T> > list)
-    \since 5.1
-
-    Constructs a multi-map with a copy of each of the elements in the
-    initializer list \a list.
-
-    This function is only available if the program is being
-    compiled in C++11 mode.
-*/
-
-/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(const QMap<Key, T> &other)
-
-    Constructs a copy of \a other (which can be a QMap or a
-    QMultiMap).
-
-    \sa operator=()
-*/
-
-/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::replace(const Key &key, const T &value)
-
-    Inserts a new item with the key \a key and a value of \a value.
-
-    If there is already an item with the key \a key, that item's value
-    is replaced with \a value.
-
-    If there are multiple items with the key \a key, the most
-    recently inserted item's value is replaced with \a value.
-
-    \sa insert()
-*/
-
-/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insert(const Key &key, const T &value)
-
-    Inserts a new item with the key \a key and a value of \a value.
-
-    If there is already an item with the same key in the map, this
-    function will simply create a new one. (This behavior is
-    different from replace(), which overwrites the value of an
-    existing item.)
-
-    \sa replace()
-*/
-
-/*! \fn [qmultimap-insert-pos] template <class Key, class T> typename QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insert(typename QMultiMap<Key, T>::const_iterator pos, const Key &key, const T &value)
-
-    \since 5.1
-    Inserts a new item with the key \a key and value \a value and with hint \a pos
-    suggesting where to do the insert.
-
-    If constBegin() is used as hint it indicates that the \a key is less than any key in the map
-    while constEnd() suggests that the \a key is larger than any key in the map.
-    Otherwise the hint should meet the condition (\a pos - 1).key() < \a key <= pos.key().
-    If the hint \a pos is wrong it is ignored and a regular insert is done.
-
-    If there is already an item with the same key in the map, this function will simply create a new one.
-
-    \b {Note:} Be careful with the hint. Providing an iterator from an older shared instance might
-    crash but there is also a risk that it will silently corrupt both the map and the \a pos map.
-*/
-
-/*! \fn template <class Key, class T> QMultiMap &QMultiMap<Key, T>::operator+=(const QMultiMap &other)
-
-    Inserts all the items in the \a other map into this map and
-    returns a reference to this map.
-
-    \sa insert(), operator+()
-*/
-
-/*! \fn template <class Key, class T> QMultiMap QMultiMap<Key, T>::operator+(const QMultiMap &other) const
-
-    Returns a map that contains all the items in this map in
-    addition to all the items in \a other. If a key is common to both
-    maps, the resulting map will contain the key multiple times.
-
-    \sa operator+=()
-*/
-
-/*!
-    \fn template <class Key, class T> bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const
-    \since 4.3
-
-    Returns \c true if the map contains an item with key \a key and
-    value \a value; otherwise returns \c false.
-
-    \sa QMap::contains()
-*/
-
-/*!
-    \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::remove(const Key &key, const T &value)
-    \since 4.3
-
-    Removes all the items that have the key \a key and the value \a
-    value from the map. Returns the number of items removed.
-
-    \sa QMap::remove()
-*/
-
-/*!
-    \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::count(const Key &key, const T &value) const
-    \since 4.3
-
-    Returns the number of items with key \a key and value \a value.
-
-    \sa QMap::count()
-*/
-
-/*!
-    \fn template <class Key, class T> typename QMap<Key, T>::iterator QMultiMap<Key, T>::find(const Key &key, const T &value)
-    \since 4.3
-
-    Returns an iterator pointing to the item with key \a key and
-    value \a value in the map.
-
-    If the map contains no such item, the function returns end().
-
-    If the map contains multiple items with key \a key, this
-    function returns an iterator that points to the most recently
-    inserted value.
-
-    \sa QMap::find()
-*/
-
-/*!
-    \fn template <class Key, class T> typename QMap<Key, T>::const_iterator QMultiMap<Key, T>::find(const Key &key, const T &value) const
-    \since 4.3
-    \overload
-
-    Returns a const iterator pointing to the item with the given \a key and
-    \a value in the map.
-
-    If the map contains no such item, the function returns end().
-
-    If the map contains multiple items with the specified \a key, this
-    function returns a const iterator that points to the most recently
-    inserted value.
-
-    \sa QMap::find()
-*/
-
-/*!
-    \fn template <class Key, class T> typename QMap<Key, T>::const_iterator QMultiMap<Key, T>::constFind(const Key &key, const T &value) const
-    \since 4.3
-
-    Returns an iterator pointing to the item with key \a key and the
-    value \a value in the map.
-
-    If the map contains no such item, the function returns
-    constEnd().
-
-    \sa QMap::constFind()
-*/
-
-/*! \fn template <class Key, class T> QList<T> QMultiMap<Key, T>::values(const Key &key) const
-
-    Returns a list containing all the values associated with key
-    \a key, from the most recently inserted to the least recently
-    inserted one.
-*/
-
-/*! \fn template <class Key, class T> QList<Key> QMultiMap<Key, T>::uniqueKeys() const
-    \since 4.2
-
-    Returns a list containing all the keys in the map in ascending
-    order. Keys that occur multiple times in the map occur only
-    once in the returned list.
-*/
-
-/*!
-    \fn [qmultimap-unite] template <class Key, class T> QMultiMap<Key, T> &QMultiMap<Key, T>::unite(const QMultiMap<Key, T> &other)
-
-    Inserts all the items in the \a other map into this map. If a
-    key is common to both maps, the resulting map will contain the
-    key multiple times.
-*/
-
-QT_END_NAMESPACE
diff --git a/src/corelib/tools/qmultimap.qdoc b/src/corelib/tools/qmultimap.qdoc
new file mode 100644
index 0000000000..3d1081d28b
--- /dev/null
+++ b/src/corelib/tools/qmultimap.qdoc
@@ -0,0 +1,1465 @@
+/****************************************************************************
+**
+** Copyright (C) 2020 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
+** Copyright (C) 2016 The Qt Company Ltd.
+** Contact: https://www.qt.io/licensing/
+**
+** This file is part of the QtCore module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and The Qt Company. For licensing terms
+** and conditions see https://www.qt.io/terms-conditions. For further
+** information use the contact form at https://www.qt.io/contact-us.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 3 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL3 included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 3 requirements
+** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 2.0 or (at your option) the GNU General
+** Public license version 3 or any later version approved by the KDE Free
+** Qt Foundation. The licenses are as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
+** included in the packaging of this file. Please review the following
+** information to ensure the GNU General Public License requirements will
+** be met: https://www.gnu.org/licenses/gpl-2.0.html and
+** https://www.gnu.org/licenses/gpl-3.0.html.
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+/*!
+    \class QMultiMap
+    \inmodule QtCore
+    \brief The QMultiMap class is a template class that provides an associative array with multiple equivalent keys.
+
+    \ingroup tools
+    \ingroup shared
+
+    \reentrant
+
+    QMultiMap\<Key, T\> is one of Qt's generic \l{container classes}. It
+    stores (key, value) pairs and provides fast lookup of the
+    value associated with a key.
+
+    QMultiMap and QMultiHash provide very similar functionality. The
+    differences are:
+
+    \list
+    \li QMultiHash provides average faster lookups than QMultiMap. (See \l{Algorithmic
+       Complexity} for details.)
+    \li When iterating over a QMultiHash, the items are arbitrarily ordered.
+       With QMultiMap, the items are always sorted by key.
+    \li The key type of a QMultiHash must provide operator==() and a global
+       qHash(Key) function. The key type of a QMultiMap must provide
+       operator<() specifying a total order. Since Qt 5.8.1 it is also safe
+       to use a pointer type as key, even if the underlying operator<()
+       does not provide a total order.
+    \endlist
+
+    Here's an example QMultiMap with QString keys and \c int values:
+    \snippet code/src_corelib_tools_qmultimap.cpp 0
+
+    To insert a (key, value) pair into the multi map, you can use insert():
+
+    \snippet code/src_corelib_tools_qmultimap.cpp 2
+
+    This inserts the following three (key, value) pairs into the
+    QMultiMap: ("a", 1), ("b", 3), ("c", 7), and ("c", -5); note
+    that duplicate keys are allowed.
+
+    To look up a value, use find() or value():
+
+    \snippet code/src_corelib_tools_qmultimap.cpp 3
+
+    If there is no item with the specified key in the map, these
+    functions return a \l{default-constructed value}.
+
+    If you want to check whether the map contains a certain key, use
+    contains():
+
+    \snippet code/src_corelib_tools_qmultimap.cpp 4
+
+    There is also a value() overload that uses its second argument as
+    a default value if there is no item with the specified key:
+
+    \snippet code/src_corelib_tools_qmultimap.cpp 5
+
+    If you want to navigate through all the (key, value) pairs stored
+    in a QMultiMap, you can use an iterator. QMultiMap provides both
+    \l{Java-style iterators} (QMultiMapIterator and QMutableMultiMapIterator)
+    and \l{STL-style iterators} (QMultiMap::const_iterator and
+    QMultiMap::iterator). Here's how to iterate over a QMultiMap<QString, int>
+    using a Java-style iterator:
+
+    \snippet code/src_corelib_tools_qmultimap.cpp 7
+
+    Here's the same code, but using an STL-style iterator this time:
+
+    \snippet code/src_corelib_tools_qmultimap.cpp 8
+
+    The items are traversed in ascending key order.
+
+    A QMultiMap allows multiple values per key. If you call
+    insert() with a key that already exists in the map, a
+    new (key, value) pair will be inserted. For example:
+
+    \snippet code/src_corelib_tools_qmultimap.cpp 9
+
+    If you want to retrieve all the values for a single key, you can
+    use values(const Key &key), which returns a QList<T>:
+
+    \snippet code/src_corelib_tools_qmultimap.cpp 10
+
+    The items that share the same key are available from most
+    recently to least recently inserted. Another approach is to call
+    find() to get the STL-style iterator for the first item with a
+    key and iterate from there:
+
+    \snippet code/src_corelib_tools_qmultimap.cpp 11
+
+    If you only need to extract the values from a map (not the keys),
+    you can also use \l{foreach}:
+
+    \snippet code/src_corelib_tools_qmultimap.cpp 12
+
+    Items can be removed from the multi map in several ways. One way is to
+    call remove(); this will remove any item with the given key.
+    Another way is to use QMutableMultiMapIterator::remove(). In addition,
+    you can clear the entire map using clear().
+
+    It is possible to merge two multi maps by calling unite(), by
+    using operator+(), and by using operator+=(). Example:
+
+    \snippet code/src_corelib_tools_qmultimap.cpp 25
+
+    QMultiMap's key and value data types must be \l{assignable data
+    types}. This covers most data types you are likely to encounter,
+    but the compiler won't let you, for example, store a QWidget as a
+    value; instead, store a QWidget *. In addition, QMultiMap's key type
+    must provide operator<(). QMap uses it to keep its items sorted,
+    and assumes that two keys \c x and \c y are equal if neither \c{x
+    < y} nor \c{y < x} is true.
+
+    Example:
+    \snippet code/src_corelib_tools_qmultimap.cpp 13
+
+    In the example, we start by comparing the employees' names. If
+    they're equal, we compare their dates of birth to break the tie.
+
+    \sa QMultiMapIterator, QMutableMultiMapIterator, QMultiHash
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap()
+
+    Constructs an empty multi map.
+
+    \sa clear()
+*/
+
+/*!
+    \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(QMultiMap<Key, T> &&other)
+
+    Move-constructs a QMultiMap instance, making it point at the same
+    object that \a other was pointing to.
+
+    \since 5.2
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(const QMultiMap<Key, T> &other)
+
+    Constructs a copy of \a other.
+
+    This operation occurs in \l{constant time}, because QMultiMap is
+    \l{implicitly shared}. This makes returning a QMultiMap from a
+    function very fast. If a shared instance is modified, it will be
+    copied (copy-on-write), and this takes \l{linear time}.
+
+    \sa operator=()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T> &QMultiMap<Key, T>::operator=(const QMultiMap<Key, T> &other)
+
+    Assigns \a other to this multi map and returns a reference to this multi map.
+*/
+
+/*!
+    \fn template <class Key, class T> QMultiMap<Key, T> &QMultiMap<Key, T>::operator=(QMultiMap<Key, T> &&other)
+
+    Move-assigns \a other to this QMultiMap instance.
+
+    \since 5.2
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::~QMultiMap()
+
+    Destroys the multi map. References to the values in the multi map, and all
+    iterators over this multi map, become invalid.
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(std::initializer_list<std::pair<Key,T> > list)
+    \since 5.1
+
+    Constructs a multi map with a copy of each of the elements in the
+    initializer list \a list.
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::QMultiMap(const typename std::multimap<Key, T> & other)
+
+    Constructs a copy of \a other.
+
+    \sa toStdMultiMap()
+*/
+
+/*! \fn template <class Key, class T> std::multimap<Key, T> QMultiMap<Key, T>::toStdMap() const
+    \obsolete Use toStdMultiMap() instead.
+
+    Returns an STL multi map equivalent to this QMultiMap.
+*/
+
+/*! \fn template <class Key, class T> std::multimap<Key, T> QMultiMap<Key, T>::toStdMultiMap() const
+
+    Returns an STL multi map equivalent to this QMultiMap.
+*/
+
+/*! \fn template <class Key, class T> void QMultiMap<Key, T>::swap(QMultiMap<Key, T> &other)
+    \since 4.8
+
+    Swaps multi map \a other with this multi map. This operation is very
+    fast and never fails.
+*/
+
+/*! \fn template <class Key, class T> bool QMultiMap<Key, T>::operator==(const QMultiMap<Key, T> &other) const
+
+    Returns \c true if \a other is equal to this multi map; otherwise returns
+    false.
+
+    Two multi maps are considered equal if they contain the same (key,
+    value) pairs, in the same order (which matters for duplicate keys).
+
+    This function requires the key and the value types to implement \c
+    operator==().
+
+    \sa operator!=()
+*/
+
+/*! \fn template <class Key, class T> bool QMultiMap<Key, T>::operator!=(const QMultiMap<Key, T> &other) const
+
+    Returns \c true if \a other is not equal to this multi map; otherwise
+    returns \c false.
+
+    Two multi maps are considered equal if they contain the same (key,
+    value) pairs, in the same order (which matters for duplicate keys).
+
+    This function requires the key and the value types to implement \c
+    operator==().
+
+    \sa operator==()
+*/
+
+/*! \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::size() const
+
+    Returns the number of (key, value) pairs in the multi map.
+
+    \sa isEmpty(), count()
+*/
+
+/*!
+    \fn template <class Key, class T> bool QMultiMap<Key, T>::isEmpty() const
+
+    Returns \c true if the multi map contains no items; otherwise returns
+    false.
+
+    \sa size()
+*/
+
+/*! \fn template <class Key, class T> void QMultiMap<Key, T>::detach()
+
+    \internal
+
+    Detaches this map from any other multi maps with which it may share
+    data.
+
+    \sa isDetached()
+*/
+
+/*! \fn template <class Key, class T> bool QMultiMap<Key, T>::isDetached() const
+
+    \internal
+
+    Returns \c true if the multi map's internal data isn't shared with any
+    other map object; otherwise returns \c false.
+
+    \sa detach()
+*/
+
+/*! \fn template <class Key, class T> bool QMultiMap<Key, T>::isSharedWith(const QMultiMap<Key, T> &other) const
+
+    \internal
+*/
+
+/*! \fn template <class Key, class T> void QMultiMap<Key, T>::clear()
+
+    Removes all items from the multi map.
+
+    \sa remove()
+*/
+
+/*! \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::remove(const Key &key)
+
+    Removes all the items that have the key \a key from the multi map.
+    Returns the number of items removed.
+
+    \sa clear(), take()
+*/
+
+/*! \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::remove(const Key &key, const T &value)
+
+    Removes all the items that have the key \a key and value \a value
+    from the multi map.
+    Returns the number of items removed.
+
+    \sa clear(), take()
+*/
+
+/*! \fn template <class Key, class T> T QMultiMap<Key, T>::take(const Key &key)
+
+    Removes the item with the key \a key from the multi map and returns
+    the value associated with it.
+
+    If the item does not exist in the multi map, the function simply
+    returns a \l{default-constructed value}. If there are multiple
+    items for \a key in the map, only the most recently inserted one
+    is removed and returned.
+
+    If you don't use the return value, remove() is more efficient.
+
+    \sa remove()
+*/
+
+/*! \fn template <class Key, class T> bool QMultiMap<Key, T>::contains(const Key &key) const
+
+    Returns \c true if the multi map contains an item with key \a key;
+    otherwise returns \c false.
+
+    \sa count()
+*/
+
+/*! \fn template <class Key, class T> bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const
+    \since 4.3
+
+    Returns \c true if the multi map contains an item with key \a key
+    and value \a value; otherwise returns \c false.
+
+    \sa count()
+*/
+
+/*!
+    \fn template <class Key, class T> Key QMultiMap<Key, T>::key(const T &value, const Key &defaultKey) const
+    \since 4.3
+    \overload
+
+    Returns the first key with value \a value, or \a defaultKey if
+    the multi map contains no item with value \a value. If no \a defaultKey
+    is provided the function returns a
+    \l{default-constructed value}{default-constructed key}.
+
+    This function can be slow (\l{linear time}), because QMultiMap's
+    internal data structure is optimized for fast lookup by key, not
+    by value.
+
+    \sa value(), keys()
+*/
+
+/*! \fn template <class Key, class T> T QMultiMap<Key, T>::value(const Key &key, const T &defaultValue) const
+
+    Returns the value associated with the key \a key.
+
+    If the multi map contains no item with key \a key, the function returns
+    \a defaultValue. If no \a defaultValue is specified, the function
+    returns a \l{default-constructed value}. If there are multiple
+    items for \a key in the multi map, the value of the most recently
+    inserted one is returned.
+
+    \sa key(), values(), contains(), operator[]()
+*/
+
+/*! \fn template <class Key, class T> QList<Key> QMultiMap<Key, T>::keys() const
+
+    Returns a list containing all the keys in the multi map in ascending
+    order. Keys that occur multiple times in the multi map
+    also occur multiple times in the list.
+
+    The order is guaranteed to be the same as that used by values().
+
+    \sa values(), key()
+*/
+
+/*! \fn template <class Key, class T> QList<Key> QMultiMap<Key, T>::keys(const T &value) const
+
+    \overload
+
+    Returns a list containing all the keys associated with value \a
+    value in ascending order.
+
+    This function can be slow (\l{linear time}), because QMultiMap's
+    internal data structure is optimized for fast lookup by key, not
+    by value.
+*/
+
+/*! \fn template <class Key, class T> QList<Key> QMultiMap<Key, T>::uniqueKeys() const
+    \since 4.2
+
+    Returns a list containing all the keys in the map in ascending
+    order. Keys that occur multiple times in the map occur only
+    once in the returned list.
+*/
+
+/*! \fn template <class Key, class T> QList<T> QMultiMap<Key, T>::values() const
+
+    Returns a list containing all the values in the map, in ascending
+    order of their keys. If a key is associated with multiple values,
+    all of its values will be in the list, and not just the most
+    recently inserted one.
+
+    \sa keys(), value()
+*/
+
+/*! \fn template <class Key, class T> QList<T> QMultiMap<Key, T>::values(const Key &key) const
+
+    Returns a list containing all the values associated with key
+    \a key, from the most recently inserted to the least recently
+    inserted one.
+
+    \sa keys(), value()
+*/
+
+/*! \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::count() const
+
+    \overload
+
+    Same as size().
+*/
+
+/*! \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::count(const Key &key) const
+
+    Returns the number of items associated with key \a key.
+
+    \sa contains(), QMultiMap::count()
+*/
+
+/*! \fn template <class Key, class T> qsizetype QMultiMap<Key, T>::count(const Key &key, const T &value) const
+
+    Returns the number of items with key \a key and value \a value.
+
+    \sa contains(), QMultiMap::count()
+*/
+
+
+/*! \fn template <class Key, class T> const Key &QMultiMap<Key, T>::firstKey() const
+    \since 5.2
+
+    Returns a reference to the smallest key in the multi map.
+    This function assumes that the multi map is not empty.
+
+    This executes in \l{constant time}.
+
+    \sa lastKey(), first(), keyBegin(), isEmpty()
+*/
+
+/*! \fn template <class Key, class T> const Key &QMultiMap<Key, T>::lastKey() const
+    \since 5.2
+
+    Returns a reference to the largest key in the multi map.
+    This function assumes that the multi map is not empty.
+
+    This executes in \l{logarithmic time}.
+
+    \sa firstKey(), last(), keyEnd(), isEmpty()
+*/
+
+/*! \fn template <class Key, class T> T &QMultiMap<Key, T>::first()
+    \since 5.2
+
+    Returns a reference to the first value in the multi map, that is the value mapped
+    to the smallest key. This function assumes that the multi map is not empty.
+
+    When unshared (or const version is called), this executes in \l{constant time}.
+
+    \sa last(), firstKey(), isEmpty()
+*/
+
+/*! \fn template <class Key, class T> const T &QMultiMap<Key, T>::first() const
+    \since 5.2
+
+    \overload
+*/
+
+/*! \fn template <class Key, class T> T &QMultiMap<Key, T>::last()
+    \since 5.2
+
+    Returns a reference to the last value in the multi map, that is the value mapped
+    to the largest key. This function assumes that the map is not empty.
+
+    When unshared (or const version is called), this executes in \l{logarithmic time}.
+
+    \sa first(), lastKey(), isEmpty()
+*/
+
+/*! \fn template <class Key, class T> const T &QMultiMap<Key, T>::last() const
+    \since 5.2
+
+    \overload
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::begin()
+
+    Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in
+    the multi map.
+
+    \sa constBegin(), end()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::begin() const
+
+    \overload
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::cbegin() const
+    \since 5.0
+
+    Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
+    in the multi map.
+
+    \sa begin(), cend()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::constBegin() const
+
+    Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
+    in the multi map.
+
+    \sa begin(), constEnd()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::key_iterator QMultiMap<Key, T>::keyBegin() const
+    \since 5.6
+
+    Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first key
+    in the multi map.
+
+    \sa keyEnd(), firstKey()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::end()
+
+    Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item
+    after the last item in the multi map.
+
+    \sa begin(), constEnd()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::end() const
+
+    \overload
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::cend() const
+    \since 5.0
+
+    Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
+    item after the last item in the multi map.
+
+    \sa cbegin(), end()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::constEnd() const
+
+    Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
+    item after the last item in the multi map.
+
+    \sa constBegin(), end()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::key_iterator QMultiMap<Key, T>::keyEnd() const
+    \since 5.6
+
+    Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
+    item after the last key in the multi map.
+
+    \sa keyBegin(), lastKey()
+*/
+
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::key_value_iterator QMultiMap<Key, T>::keyValueBegin()
+    \since 5.10
+
+    Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first entry
+    in the multi map.
+
+    \sa keyValueEnd()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::key_value_iterator QMultiMap<Key, T>::keyValueEnd()
+    \since 5.10
+
+    Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
+    entry after the last entry in the multi map.
+
+    \sa keyValueBegin()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_key_value_iterator QMultiMap<Key, T>::keyValueBegin() const
+    \since 5.10
+
+    Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
+    in the multi map.
+
+    \sa keyValueEnd()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_key_value_iterator QMultiMap<Key, T>::constKeyValueBegin() const
+    \since 5.10
+
+    Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
+    in the multi map.
+
+    \sa keyValueBegin()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_key_value_iterator QMultiMap<Key, T>::keyValueEnd() const
+    \since 5.10
+
+    Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
+    entry after the last entry in the multi map.
+
+    \sa keyValueBegin()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_key_value_iterator QMultiMap<Key, T>::constKeyValueEnd() const
+    \since 5.10
+
+    Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
+    entry after the last entry in the multi map.
+
+    \sa constKeyValueBegin()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::erase(const_iterator pos)
+
+    Removes the (key, value) pair pointed to by the iterator \a pos
+    from the multi map, and returns an iterator to the next item in the
+    map.
+
+    \sa remove()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::find(const Key &key)
+
+    Returns an iterator pointing to the item with key \a key in the
+    multi map.
+
+    If the multi map contains no item with key \a key, the function
+    returns end().
+
+    If the map contains multiple items with key \a key, this
+    function returns an iterator that points to the most recently
+    inserted value. The other values are accessible by incrementing
+    the iterator. For example, here's some code that iterates over all
+    the items with the same key:
+
+    \snippet code/src_corelib_tools_qmultimap.cpp 11
+
+    \sa constFind(), value(), values(), lowerBound(), upperBound()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::find(const Key &key) const
+
+    \overload
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::constFind(const Key &key) const
+    \since 4.1
+
+    Returns an const iterator pointing to the item with key \a key in the
+    multi map.
+
+    If the multi map contains no item with key \a key, the function
+    returns constEnd().
+
+    \sa find(), QMultiMap::constFind()
+*/
+
+/*!
+    \fn template <class Key, class T> typename QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::find(const Key &key, const T &value) const
+    \since 4.3
+    \overload
+
+    Returns a const iterator pointing to the item with the given \a key and
+    \a value in the map.
+
+    If the map contains no such item, the function returns end().
+
+    If the map contains multiple items with the specified \a key, this
+    function returns a const iterator that points to the most recently
+    inserted value.
+*/
+
+/*!
+    \fn template <class Key, class T> typename QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::constFind(const Key &key, const T &value) const
+    \since 4.3
+
+    Returns an iterator pointing to the item with key \a key and the
+    value \a value in the map.
+
+    If the map contains no such item, the function returns
+    constEnd().
+
+    \sa QMap::constFind()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::lowerBound(const Key &key)
+
+    Returns an iterator pointing to the first item with key \a key in
+    the map. If the map contains no item with key \a key, the
+    function returns an iterator to the nearest item with a greater
+    key.
+
+    Example:
+    \snippet code/src_corelib_tools_qmultimap.cpp 15
+
+    If the map contains multiple items with key \a key, this
+    function returns an iterator that points to the most recently
+    inserted value. The other values are accessible by incrementing
+    the iterator. For example, here's some code that iterates over all
+    the items with the same key:
+
+    \snippet code/src_corelib_tools_qmultimap.cpp 16
+
+    \sa upperBound(), find()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::lowerBound(const Key &key) const
+
+    \overload
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::upperBound(const Key &key)
+
+    Returns an iterator pointing to the item that immediately follows
+    the last item with key \a key in the map. If the map contains no
+    item with key \a key, the function returns an iterator to the
+    nearest item with a greater key.
+
+    Example:
+    \snippet code/src_corelib_tools_qmultimap.cpp 17
+
+    \sa lowerBound(), find()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::upperBound(const Key &key) const
+
+    \overload
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insert(const Key &key, const T &value)
+
+    Inserts a new item with the key \a key and a value of \a value.
+
+    If there is already an item with the same key in the map, this
+    function will simply create a new one. (This behavior is
+    different from replace(), which overwrites the value of an
+    existing item.)
+
+    \sa replace()
+*/
+
+/*! \fn [qmultimap-insert-pos] template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insert(const_iterator pos, const Key &key, const T &value)
+    \overload
+    \since 5.1
+    Inserts a new item with the key \a key and value \a value and with hint \a pos
+    suggesting where to do the insert.
+
+    If constBegin() is used as hint it indicates that the \a key is less than any key in the multi map
+    while constEnd() suggests that the \a key is (strictly) larger than any key in the multi map.
+    Otherwise the hint should meet the condition (\a pos - 1).key() < \a key <= pos.key().
+    If the hint \a pos is wrong it is ignored and a regular insert is done.
+
+    If the hint is correct and the multi map is unshared, the insert executes in amortized \l{constant time}.
+
+    If there is already an item with the same key in the map, this function will simply create a new one.
+
+    When creating a multi map from sorted data inserting the largest key first with constBegin()
+    is faster than inserting in sorted order with constEnd(), since constEnd() - 1 (which is needed
+    to check if the hint is valid) needs \l{logarithmic time}.
+
+    \b {Note:} Be careful with the hint. Providing an iterator from an older shared instance might
+    crash but there is also a risk that it will silently corrupt both the multi map and the \a pos multi map.
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insertMulti(const Key &key, const T &value)
+
+    Same as insert().
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::insertMulti(const_iterator pos, const Key &key, const T &value)
+    \overload
+
+    Same as insert().
+*/
+
+/*! \fn template <class Key, class T> void QMultiMap<Key, T>::insert(const QMultiMap<Key, T> &map)
+    \since 5.15
+
+    Same as unite().
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::replace(const Key &key, const T &value)
+
+    Inserts a new item with the key \a key and a value of \a value.
+
+    If there is already an item with the key \a key, that item's value
+    is replaced with \a value.
+
+    If there are multiple items with the key \a key, the most
+    recently inserted item's value is replaced with \a value.
+
+    \sa insert()
+*/
+
+/*! \typedef QMultiMap::Iterator
+
+    Qt-style synonym for QMultiMap<Key, T>::iterator.
+*/
+
+/*! \typedef QMultiMap::ConstIterator
+
+    Qt-style synonym for QMultiMap<Key, T>::const_iterator.
+*/
+
+/*! \typedef QMultiMap::difference_type
+
+    Typedef for ptrdiff_t. Provided for STL compatibility.
+*/
+
+/*! \typedef QMultiMap::key_type
+
+    Typedef for Key. Provided for STL compatibility.
+*/
+
+/*! \typedef QMultiMap::mapped_type
+
+    Typedef for T. Provided for STL compatibility.
+*/
+
+/*! \typedef QMultiMap::size_type
+
+    Typedef for int. Provided for STL compatibility.
+*/
+
+/*!
+    \fn template <class Key, class T> bool QMultiMap<Key, T>::empty() const
+
+    This function is provided for STL compatibility. It is equivalent
+    to isEmpty(), returning true if the map is empty; otherwise
+    returning false.
+*/
+
+/*!
+  \fn template <class Key, class T> QPair<typename QMultiMap<Key, T>::iterator, typename QMultiMap<Key, T>::iterator> QMultiMap<Key, T>::equal_range(const Key &key)
+
+  Returns a pair of iterators delimiting the range of values \c{[first, second)}, that
+  are stored under \a key.
+*/
+
+/*!
+    \fn template <class Key, class T> QPair<typename QMultiMap<Key, T>::const_iterator, typename QMultiMap<Key, T>::const_iterator> QMultiMap<Key, T>::equal_range(const Key &key) const
+    \overload
+    \since 5.6
+*/
+
+/*!
+    \fn [qmultimap-unite] template <class Key, class T> QMultiMap<Key, T> &QMultiMap<Key, T>::unite(const QMultiMap<Key, T> &other)
+
+    Inserts all the items in the \a other map into this map. If a
+    key is common to both maps, the resulting map will contain the
+    key multiple times.
+*/
+
+/*! \fn template <class Key, class T> QMultiMap &QMultiMap<Key, T>::operator+=(const QMultiMap &other)
+
+    Inserts all the items in the \a other map into this map and
+    returns a reference to this map.
+
+    \sa insert(), operator+()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap QMultiMap<Key, T>::operator+(const QMultiMap &other) const
+
+    Returns a map that contains all the items in this map in
+    addition to all the items in \a other. If a key is common to both
+    maps, the resulting map will contain the key multiple times.
+
+    \sa operator+=()
+*/
+
+/*! \class QMultiMap::iterator
+    \inmodule QtCore
+    \brief The QMultiMap::iterator class provides an STL-style non-const iterator for QMultiMap.
+
+    QMultiMap features both \l{STL-style iterators} and \l{Java-style
+    iterators}. The STL-style iterators are more low-level and more
+    cumbersome to use; on the other hand, they are slightly faster
+    and, for developers who already know STL, have the advantage of
+    familiarity.
+
+    QMultiMap\<Key, T\>::iterator allows you to iterate over a QMultiMap
+    and to modify the value (but not the key) stored under
+    a particular key. If you want to iterate over a const QMultiMap, you
+    should use QMultiMap::const_iterator. It is generally good practice to
+    use QMultiMap::const_iterator on a non-const QMultiMap as well, unless you
+    need to change the QMultiMap through the iterator. Const iterators are
+    slightly faster, and can improve code readability.
+
+    The default QMultiMap::iterator constructor creates an uninitialized
+    iterator. You must initialize it using a QMultiMap function like
+    QMultiMap::begin(), QMultiMap::end(), or QMultiMap::find() before you can
+    start iterating. Here's a typical loop that prints all the (key,
+    value) pairs stored in a map:
+
+    \snippet code/src_corelib_tools_qmultimap.cpp 18
+
+    Unlike QMultiHash, which stores its items in an arbitrary order, QMultiMap
+    stores its items ordered by key. Items that share the same key
+    will appear consecutively,
+    from the most recently to the least recently inserted value.
+
+    Let's see a few examples of things we can do with a
+    QMultiMap::iterator that we cannot do with a QMultiMap::const_iterator.
+    Here's an example that increments every value stored in the QMultiMap
+    by 2:
+
+    \snippet code/src_corelib_tools_qmultimap.cpp 19
+
+    Here's an example that removes all the items whose key is a
+    string that starts with an underscore character:
+
+    \snippet code/src_corelib_tools_qmultimap.cpp 20
+
+    The call to QMultiMap::erase() removes the item pointed to by the
+    iterator from the map, and returns an iterator to the next item.
+    Here's another way of removing an item while iterating:
+
+    \snippet code/src_corelib_tools_qmultimap.cpp 21
+
+    It might be tempting to write code like this:
+
+    \snippet code/src_corelib_tools_qmultimap.cpp 22
+
+    However, this will potentially crash in \c{++i}, because \c i is
+    a dangling iterator after the call to erase().
+
+    Multiple iterators can be used on the same map. If you add items
+    to the map, existing iterators will remain valid. If you remove
+    items from the map, iterators that point to the removed items
+    will become dangling iterators.
+
+    \warning Iterators on implicitly shared containers do not work
+    exactly like STL-iterators. You should avoid copying a container
+    while iterators are active on that container. For more information,
+    read \l{Implicit sharing iterator problem}.
+
+    \sa QMultiMap::const_iterator, QMultiMap::key_iterator, QMutableMultiMapIterator
+*/
+
+/*! \typedef QMultiMap::iterator::difference_type
+
+    \internal
+*/
+
+/*! \typedef QMultiMap::iterator::iterator_category
+
+  A synonym for \e {std::bidirectional_iterator_tag} indicating
+  this iterator is a bidirectional iterator.
+*/
+
+/*! \typedef QMultiMap::iterator::pointer
+
+    \internal
+*/
+
+/*! \typedef QMultiMap::iterator::reference
+
+    \internal
+*/
+
+/*! \typedef QMultiMap::iterator::value_type
+
+    \internal
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator::iterator()
+
+    Constructs an uninitialized iterator.
+
+    Functions like key(), value(), and operator++() must not be
+    called on an uninitialized iterator. Use operator=() to assign a
+    value to it before using it.
+
+    \sa QMultiMap::begin(), QMultiMap::end()
+*/
+
+/*! \fn template <class Key, class T> const Key &QMultiMap<Key, T>::iterator::key() const
+
+    Returns the current item's key as a const reference.
+
+    There is no direct way of changing an item's key through an
+    iterator, although it can be done by calling QMultiMap::erase()
+    followed by QMultiMap::insert().
+
+    \sa value()
+*/
+
+/*! \fn template <class Key, class T> T &QMultiMap<Key, T>::iterator::value() const
+
+    Returns a modifiable reference to the current item's value.
+
+    You can change the value of an item by using value() on
+    the left side of an assignment, for example:
+
+    \snippet code/src_corelib_tools_qmultimap.cpp 23
+
+    \sa key(), operator*()
+*/
+
+/*! \fn template <class Key, class T> T &QMultiMap<Key, T>::iterator::operator*() const
+
+    Returns a modifiable reference to the current item's value.
+
+    Same as value().
+
+    \sa key()
+*/
+
+/*! \fn template <class Key, class T> T *QMultiMap<Key, T>::iterator::operator->() const
+
+    Returns a pointer to the current item's value.
+
+    \sa value()
+*/
+
+/*!
+    \fn template <class Key, class T> bool QMultiMap<Key, T>::iterator::operator==(const iterator &other) const
+    \fn template <class Key, class T> bool QMultiMap<Key, T>::iterator::operator==(const const_iterator &other) const
+
+    Returns \c true if \a other points to the same item as this
+    iterator; otherwise returns \c false.
+
+    \sa operator!=()
+*/
+
+/*!
+    \fn template <class Key, class T> bool QMultiMap<Key, T>::iterator::operator!=(const iterator &other) const
+    \fn template <class Key, class T> bool QMultiMap<Key, T>::iterator::operator!=(const const_iterator &other) const
+
+    Returns \c true if \a other points to a different item than this
+    iterator; otherwise returns \c false.
+
+    \sa operator==()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator &QMultiMap<Key, T>::iterator::operator++()
+
+    The prefix ++ operator (\c{++i}) advances the iterator to the
+    next item in the multi map and returns an iterator to the new current
+    item.
+
+    Calling this function on QMultiMap::end() leads to undefined results.
+
+    \sa operator--()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::iterator::operator++(int)
+
+    \overload
+
+    The postfix ++ operator (\c{i++}) advances the iterator to the
+    next item in the multi map and returns an iterator to the previously
+    current item.
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator &QMultiMap<Key, T>::iterator::operator--()
+
+    The prefix -- operator (\c{--i}) makes the preceding item
+    current and returns an iterator pointing to the new current item.
+
+    Calling this function on QMultiMap::begin() leads to undefined
+    results.
+
+    \sa operator++()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::iterator QMultiMap<Key, T>::iterator::operator--(int)
+
+    \overload
+
+    The postfix -- operator (\c{i--}) makes the preceding item
+    current and returns an iterator pointing to the previously
+    current item.
+*/
+
+/*! \class QMultiMap::const_iterator
+    \inmodule QtCore
+    \brief The QMultiMap::const_iterator class provides an STL-style const iterator for QMultiMap.
+
+    QMultiMap features both \l{STL-style iterators} and \l{Java-style
+    iterators}. The STL-style iterators are more low-level and more
+    cumbersome to use; on the other hand, they are slightly faster
+    and, for developers who already know STL, have the advantage of
+    familiarity.
+
+    QMultiMap\<Key, T\>::const_iterator allows you to iterate over a QMultiMap.
+    If you want to modify the QMultiMap as you iterate
+    over it, you must use QMultiMap::iterator instead. It is generally
+    good practice to use QMultiMap::const_iterator on a non-const QMultiMap as
+    well, unless you need to change the QMultiMap through the iterator.
+    Const iterators are slightly faster, and can improve code
+    readability.
+
+    The default QMultiMap::const_iterator constructor creates an
+    uninitialized iterator. You must initialize it using a QMultiMap
+    function like QMultiMap::constBegin(), QMultiMap::constEnd(), or
+    QMultiMap::find() before you can start iterating. Here's a typical
+    loop that prints all the (key, value) pairs stored in a map:
+
+    \snippet code/src_corelib_tools_qmultimap.cpp 24
+
+    Unlike QMultiHash, which stores its items in an arbitrary order, QMultiMap
+    stores its items ordered by key. Items that share the same key
+    will appear consecutively,
+    from the most recently to the least recently inserted value.
+
+    Multiple iterators can be used on the same multi map. If you add items
+    to the map, existing iterators will remain valid. If you remove
+    items from the map, iterators that point to the removed items
+    will become dangling iterators.
+
+    \warning Iterators on implicitly shared containers do not work
+    exactly like STL-iterators. You should avoid copying a container
+    while iterators are active on that container. For more information,
+    read \l{Implicit sharing iterator problem}.
+
+    \sa QMultiMap::iterator, QMultiMap::key_iterator, QMultiMapIterator
+*/
+
+/*! \typedef QMultiMap::const_iterator::difference_type
+
+    \internal
+*/
+
+/*! \typedef QMultiMap::const_iterator::iterator_category
+
+  A synonym for \e {std::bidirectional_iterator_tag} indicating
+  this iterator is a bidirectional iterator.
+*/
+
+/*! \typedef QMultiMap::const_iterator::pointer
+
+    \internal
+*/
+
+/*! \typedef QMultiMap::const_iterator::reference
+
+    \internal
+*/
+
+/*! \typedef QMultiMap::const_iterator::value_type
+
+    \internal
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator::const_iterator()
+
+    Constructs an uninitialized iterator.
+
+    Functions like key(), value(), and operator++() must not be
+    called on an uninitialized iterator. Use operator=() to assign a
+    value to it before using it.
+
+    \sa QMultiMap::constBegin(), QMultiMap::constEnd()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator::const_iterator(const iterator &other)
+
+    Constructs a copy of \a other.
+*/
+
+/*! \fn template <class Key, class T> const Key &QMultiMap<Key, T>::const_iterator::key() const
+
+    Returns the current item's key.
+
+    \sa value()
+*/
+
+/*! \fn template <class Key, class T> const T &QMultiMap<Key, T>::const_iterator::value() const
+
+    Returns the current item's value.
+
+    \sa key(), operator*()
+*/
+
+/*! \fn template <class Key, class T> const T &QMultiMap<Key, T>::const_iterator::operator*() const
+
+    Returns the current item's value.
+
+    Same as value().
+
+    \sa key()
+*/
+
+/*! \fn template <class Key, class T> const T *QMultiMap<Key, T>::const_iterator::operator->() const
+
+    Returns a pointer to the current item's value.
+
+    \sa value()
+*/
+
+/*! \fn template <class Key, class T> bool QMultiMap<Key, T>::const_iterator::operator==(const const_iterator &other) const
+
+    Returns \c true if \a other points to the same item as this
+    iterator; otherwise returns \c false.
+
+    \sa operator!=()
+*/
+
+/*! \fn template <class Key, class T> bool QMultiMap<Key, T>::const_iterator::operator!=(const const_iterator &other) const
+
+    Returns \c true if \a other points to a different item than this
+    iterator; otherwise returns \c false.
+
+    \sa operator==()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator &QMultiMap<Key, T>::const_iterator::operator++()
+
+    The prefix ++ operator (\c{++i}) advances the iterator to the
+    next item in the map and returns an iterator to the new current
+    item.
+
+    Calling this function on QMultiMap::end() leads to undefined results.
+
+    \sa operator--()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::const_iterator::operator++(int)
+
+    \overload
+
+    The postfix ++ operator (\c{i++}) advances the iterator to the
+    next item in the map and returns an iterator to the previously
+    current item.
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator &QMultiMap<Key, T>::const_iterator::operator--()
+
+    The prefix -- operator (\c{--i}) makes the preceding item
+    current and returns an iterator pointing to the new current item.
+
+    Calling this function on QMultiMap::begin() leads to undefined
+    results.
+
+    \sa operator++()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::const_iterator QMultiMap<Key, T>::const_iterator::operator--(int)
+
+    \overload
+
+    The postfix -- operator (\c{i--}) makes the preceding item
+    current and returns an iterator pointing to the previously
+    current item.
+*/
+
+/*! \class QMultiMap::key_iterator
+    \inmodule QtCore
+    \since 5.6
+    \brief The QMultiMap::key_iterator class provides an STL-style const iterator for QMultiMap keys.
+
+    QMultiMap::key_iterator is essentially the same as QMultiMap::const_iterator
+    with the difference that operator*() and operator->() return a key
+    instead of a value.
+
+    For most uses QMultiMap::iterator and QMultiMap::const_iterator should be used,
+    you can easily access the key by calling QMultiMap::iterator::key():
+
+    \snippet code/src_corelib_tools_qmultimap.cpp keyiterator1
+
+    However, to have interoperability between QMultiMap's keys and STL-style
+    algorithms we need an iterator that dereferences to a key instead
+    of a value. With QMultiMap::key_iterator we can apply an algorithm to a
+    range of keys without having to call QMultiMap::keys(), which is inefficient
+    as it costs one QMultiMap iteration and memory allocation to create a temporary
+    QList.
+
+    \snippet code/src_corelib_tools_qmultimap.cpp keyiterator2
+
+    QMultiMap::key_iterator is const, it's not possible to modify the key.
+
+    The default QMultiMap::key_iterator constructor creates an uninitialized
+    iterator. You must initialize it using a QMultiMap function like
+    QMultiMap::keyBegin() or QMultiMap::keyEnd().
+
+    \warning Iterators on implicitly shared containers do not work
+    exactly like STL-iterators. You should avoid copying a container
+    while iterators are active on that container. For more information,
+    read \l{Implicit sharing iterator problem}.
+
+    \sa QMultiMap::const_iterator, QMultiMap::iterator
+*/
+
+/*! \typedef QMultiMap::key_iterator::difference_type
+    \internal
+*/
+
+/*! \typedef QMultiMap::key_iterator::iterator_category
+    \internal
+*/
+
+/*! \typedef QMultiMap::key_iterator::pointer
+    \internal
+*/
+
+/*! \typedef QMultiMap::key_iterator::reference
+    \internal
+*/
+
+/*! \typedef QMultiMap::key_iterator::value_type
+    \internal
+*/
+
+/*! \fn template <class Key, class T> const T &QMultiMap<Key, T>::key_iterator::operator*() const
+
+    Returns the current item's key.
+*/
+
+/*! \fn template <class Key, class T> const T *QMultiMap<Key, T>::key_iterator::operator->() const
+
+    Returns a pointer to the current item's key.
+*/
+
+/*! \fn template <class Key, class T> bool QMultiMap<Key, T>::key_iterator::operator==(key_iterator other) const
+
+    Returns \c true if \a other points to the same item as this
+    iterator; otherwise returns \c false.
+
+    \sa operator!=()
+*/
+
+/*! \fn template <class Key, class T> bool QMultiMap<Key, T>::key_iterator::operator!=(key_iterator other) const
+
+    Returns \c true if \a other points to a different item than this
+    iterator; otherwise returns \c false.
+
+    \sa operator==()
+*/
+
+/*!
+    \fn template <class Key, class T> QMultiMap<Key, T>::key_iterator &QMultiMap<Key, T>::key_iterator::operator++()
+
+    The prefix ++ operator (\c{++i}) advances the iterator to the
+    next item in the hash and returns an iterator to the new current
+    item.
+
+    Calling this function on QMultiMap::keyEnd() leads to undefined results.
+
+    \sa operator--()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::key_iterator QMultiMap<Key, T>::key_iterator::operator++(int)
+
+    \overload
+
+    The postfix ++ operator (\c{i++}) advances the iterator to the
+    next item in the hash and returns an iterator to the previous
+    item.
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::key_iterator &QMultiMap<Key, T>::key_iterator::operator--()
+
+    The prefix -- operator (\c{--i}) makes the preceding item
+    current and returns an iterator pointing to the new current item.
+
+    Calling this function on QMultiMap::keyBegin() leads to undefined
+    results.
+
+    \sa operator++()
+*/
+
+/*! \fn template <class Key, class T> QMultiMap<Key, T>::key_iterator QMultiMap<Key, T>::key_iterator::operator--(int)
+
+    \overload
+
+    The postfix -- operator (\c{i--}) makes the preceding item
+    current and returns an iterator pointing to the previous
+    item.
+*/
+
+/*! \fn template <class Key, class T> const_iterator QMultiMap<Key, T>::key_iterator::base() const
+    Returns the underlying const_iterator this key_iterator is based on.
+*/
+
+/*! \typedef QMultiMap::const_key_value_iterator
+    \inmodule QtCore
+    \since 5.10
+    \brief The QMultiMap::const_key_value_iterator typedef provides an STL-style iterator for QMultiMap.
+
+    QMultiMap::const_key_value_iterator is essentially the same as QMultiMap::const_iterator
+    with the difference that operator*() returns a key/value pair instead of a
+    value.
+
+    \sa QKeyValueIterator
+*/
+
+/*! \typedef QMultiMap::key_value_iterator
+    \inmodule QtCore
+    \since 5.10
+    \brief The QMultiMap::key_value_iterator typedef provides an STL-style iterator for QMultiMap.
+
+    QMultiMap::key_value_iterator is essentially the same as QMultiMap::iterator
+    with the difference that operator*() returns a key/value pair instead of a
+    value.
+
+    \sa QKeyValueIterator
+*/
+
+/*! \fn template <class Key, class T> QDataStream &operator<<(QDataStream &out, const QMultiMap<Key, T> &map)
+    \relates QMultiMap
+
+    Writes the multi map \a map to stream \a out.
+
+    This function requires the key and value types to implement \c
+    operator<<().
+
+    \sa{Serializing Qt Data Types}{Format of the QDataStream operators}
+*/
+
+/*! \fn template <class Key, class T> QDataStream &operator>>(QDataStream &in, QMultiMap<Key, T> &map)
+    \relates QMultiMap
+
+    Reads a map from stream \a in into \a map.
+
+    This function requires the key and value types to implement \c
+    operator>>().
+
+    \sa{Serializing Qt Data Types}{Format of the QDataStream operators}
+*/
diff --git a/src/corelib/tools/tools.pri b/src/corelib/tools/tools.pri
index c8ce79ce36..9380b8bd5a 100644
--- a/src/corelib/tools/tools.pri
+++ b/src/corelib/tools/tools.pri
@@ -58,7 +58,6 @@ SOURCES += \
         tools/qline.cpp \
         tools/qlist.cpp \
         tools/qpoint.cpp \
-        tools/qmap.cpp \
         tools/qmargins.cpp \
         tools/qmessageauthenticationcode.cpp \
         tools/qcontiguouscache.cpp \