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>

2 files changed, 74 insertions, 70 deletions

diff --git a/tests/auto/corelib/tools/collections/tst_collections.cpp b/tests/auto/corelib/tools/collections/tst_collections.cpp
index 2cab6312aa..e5cfb0fbad 100644
--- a/tests/auto/corelib/tools/collections/tst_collections.cpp
+++ b/tests/auto/corelib/tools/collections/tst_collections.cpp
@@ -2609,6 +2609,7 @@ class LessThanComparable
 {
 public:
     bool operator<(const LessThanComparable &) const { return true; }
+    bool operator==(const LessThanComparable &) const { return true; }
 };
 
 class EqualsComparable
@@ -2937,20 +2938,6 @@ void tst_Collections::forwardDeclared()
     }
 }
 
-class alignas(4) Aligned4
-{
-    char i;
-public:
-    Aligned4(int i = 0) : i(i) {}
-
-    enum { PreferredAlignment = 4 };
-
-    inline bool operator==(const Aligned4 &other) const { return i == other.i; }
-    inline bool operator<(const Aligned4 &other) const { return i < other.i; }
-    friend inline size_t qHash(const Aligned4 &a) { return qHash(a.i); }
-};
-static_assert(alignof(Aligned4) % 4 == 0);
-
 #if defined(Q_PROCESSOR_ARM)
 #  if defined(Q_COMPILER_ALIGNAS) && defined(__BIGGEST_ALIGNMENT__)
      // On ARM __BIGGEST_ALIGNMENT__ must be multiplied by 8 to
@@ -2963,18 +2950,29 @@ static_assert(alignof(Aligned4) % 4 == 0);
 #  define BIGGEST_ALIGNMENT_TO_TEST 128
 #endif
 
-class alignas(BIGGEST_ALIGNMENT_TO_TEST) AlignedBiggest
+template <size_t Alignment>
+class alignas(Alignment) AlignedClass
 {
     char i;
+
 public:
-    AlignedBiggest(int i = 0) : i(i) {}
+    AlignedClass(int i = 0) : i(i) {}
 
-    enum { PreferredAlignment = BIGGEST_ALIGNMENT_TO_TEST };
+    enum { PreferredAlignment = Alignment };
 
-    inline bool operator==(const AlignedBiggest &other) const { return i == other.i; }
-    inline bool operator<(const AlignedBiggest &other) const { return i < other.i; }
-    friend inline int qHash(const AlignedBiggest &a) { return qHash(a.i); }
+    inline bool operator==(const AlignedClass &other) const { return i == other.i; }
+    inline bool operator<(const AlignedClass &other) const { return i < other.i; }
+    friend inline int qHash(const AlignedClass &a) { return qHash(a.i); }
 };
+
+using Aligned4 = AlignedClass<4>;
+static_assert(alignof(Aligned4) % 4 == 0);
+
+using AlignedStdMax = AlignedClass<alignof(std::max_align_t)>;
+static_assert(alignof(AlignedStdMax) % alignof(std::max_align_t) == 0);
+
+using AlignedBiggest = AlignedClass<BIGGEST_ALIGNMENT_TO_TEST>;
+static_assert(BIGGEST_ALIGNMENT_TO_TEST > alignof(std::max_align_t), "Not overly aligned");
 static_assert(alignof(AlignedBiggest) % BIGGEST_ALIGNMENT_TO_TEST == 0);
 
 template<typename C>
@@ -3032,18 +3030,29 @@ void testAssociativeContainerAlignment()
 
 void tst_Collections::alignment()
 {
-    testVectorAlignment<QList<Aligned4>>();
-    testVectorAlignment<QList<AlignedBiggest>>();
-    testContiguousCacheAlignment<QContiguousCache<Aligned4>>();
-    testContiguousCacheAlignment<QContiguousCache<AlignedBiggest>>();
-    testAssociativeContainerAlignment<QMap<Aligned4, Aligned4>>();
-    testAssociativeContainerAlignment<QMap<Aligned4, AlignedBiggest>>();
-    testAssociativeContainerAlignment<QMap<AlignedBiggest, Aligned4>>();
-    testAssociativeContainerAlignment<QMap<AlignedBiggest, AlignedBiggest>>();
-    testAssociativeContainerAlignment<QHash<Aligned4, Aligned4>>();
-    testAssociativeContainerAlignment<QHash<Aligned4, AlignedBiggest>>();
-    testAssociativeContainerAlignment<QHash<AlignedBiggest, Aligned4>>();
-    testAssociativeContainerAlignment<QHash<AlignedBiggest, AlignedBiggest>>();
+    testVectorAlignment<QList<Aligned4> >();
+    testVectorAlignment<QList<AlignedStdMax> >();
+    testVectorAlignment<QList<AlignedBiggest> >();
+
+    testContiguousCacheAlignment<QContiguousCache<Aligned4> >();
+    testContiguousCacheAlignment<QContiguousCache<AlignedStdMax> >();
+    testContiguousCacheAlignment<QContiguousCache<AlignedBiggest> >();
+
+    // there's no guarentee that std::map supports over-aligned types
+    testAssociativeContainerAlignment<QMap<Aligned4, Aligned4> >();
+    testAssociativeContainerAlignment<QMap<Aligned4, AlignedStdMax> >();
+    testAssociativeContainerAlignment<QMap<AlignedStdMax, Aligned4> >();
+    testAssociativeContainerAlignment<QMap<AlignedStdMax, AlignedStdMax> >();
+
+    testAssociativeContainerAlignment<QHash<Aligned4, Aligned4> >();
+    testAssociativeContainerAlignment<QHash<Aligned4, AlignedStdMax> >();
+    testAssociativeContainerAlignment<QHash<Aligned4, AlignedBiggest> >();
+    testAssociativeContainerAlignment<QHash<AlignedStdMax, Aligned4> >();
+    testAssociativeContainerAlignment<QHash<AlignedStdMax, AlignedStdMax> >();
+    testAssociativeContainerAlignment<QHash<AlignedStdMax, AlignedBiggest> >();
+    testAssociativeContainerAlignment<QHash<AlignedBiggest, Aligned4> >();
+    testAssociativeContainerAlignment<QHash<AlignedBiggest, AlignedStdMax> >();
+    testAssociativeContainerAlignment<QHash<AlignedBiggest, AlignedBiggest> >();
 }
 
 #ifndef QT_NO_TEMPLATE_TEMPLATE_PARAMETERS
diff --git a/tests/auto/corelib/tools/qmap/tst_qmap.cpp b/tests/auto/corelib/tools/qmap/tst_qmap.cpp
index b812eb89a1..c8a228f8dd 100644
--- a/tests/auto/corelib/tools/qmap/tst_qmap.cpp
+++ b/tests/auto/corelib/tools/qmap/tst_qmap.cpp
@@ -36,8 +36,8 @@ class tst_QMap : public QObject
 {
     Q_OBJECT
 protected:
-    template <class KEY, class VALUE>
-    void sanityCheckTree(const QMap<KEY, VALUE> &m, int calledFromLine);
+    template <class Map>
+    void sanityCheckTree(const Map &m, int calledFromLine);
 public slots:
     void init();
 private slots:
@@ -119,15 +119,15 @@ QDebug operator << (QDebug d, const MyClass &c) {
     return d;
 }
 
-template <class KEY, class VALUE>
-void tst_QMap::sanityCheckTree(const QMap<KEY, VALUE> &m, int calledFromLine)
+template <class Map>
+void tst_QMap::sanityCheckTree(const Map &m, int calledFromLine)
 {
     QString possibleFrom;
     possibleFrom.setNum(calledFromLine);
     possibleFrom = "Called from line: " + possibleFrom;
     int count = 0;
-    typename QMap<KEY, VALUE>::const_iterator oldite = m.constBegin();
-    for (typename QMap<KEY, VALUE>::const_iterator i = m.constBegin(); i != m.constEnd(); ++i) {
+    typename Map::const_iterator oldite = m.constBegin();
+    for (typename Map::const_iterator i = m.constBegin(); i != m.constEnd(); ++i) {
         count++;
         bool oldIteratorIsLarger = i.key() < oldite.key();
         QVERIFY2(!oldIteratorIsLarger, possibleFrom.toUtf8());
@@ -594,7 +594,7 @@ void tst_QMap::contains()
 
 void tst_QMap::find()
 {
-    QMap<int, QString> map1;
+    QMultiMap<int, QString> map1;
     QString testString="Teststring %0";
     QString compareString;
     int i,count=0;
@@ -614,7 +614,7 @@ void tst_QMap::find()
         QCOMPARE(map1.count(4), i - 2);
     }
 
-    QMap<int, QString>::const_iterator it=map1.constFind(4);
+    QMultiMap<int, QString>::const_iterator it=map1.constFind(4);
 
     for(i = 9; i > 2 && it != map1.constEnd() && it.key() == 4; --i) {
         compareString = testString.arg(i);
@@ -627,7 +627,7 @@ void tst_QMap::find()
 
 void tst_QMap::constFind()
 {
-    QMap<int, QString> map1;
+    QMultiMap<int, QString> map1;
     QString testString="Teststring %0";
     QString compareString;
     int i,count=0;
@@ -648,7 +648,7 @@ void tst_QMap::constFind()
         map1.insertMulti(4, compareString);
     }
 
-    QMap<int, QString>::const_iterator it=map1.constFind(4);
+    QMultiMap<int, QString>::const_iterator it=map1.constFind(4);
 
     for(i = 9; i > 2 && it != map1.constEnd() && it.key() == 4; --i) {
         compareString = testString.arg(i);
@@ -661,7 +661,7 @@ void tst_QMap::constFind()
 
 void tst_QMap::lowerUpperBound()
 {
-    QMap<int, QString> map1;
+    QMultiMap<int, QString> map1;
 
     map1.insert(1, "one");
     map1.insert(5, "five");
@@ -712,7 +712,7 @@ void tst_QMap::lowerUpperBound()
 
 void tst_QMap::mergeCompare()
 {
-    QMap<int, QString> map1, map2, map3, map1b, map2b;
+    QMultiMap<int, QString> map1, map2, map3, map1b, map2b;
 
     map1.insert(1,"ett");
     map1.insert(3,"tre");
@@ -770,13 +770,13 @@ void tst_QMap::iterators()
     QMap<int, QString>::iterator stlIt = map.begin();
     QCOMPARE(stlIt.value(), QLatin1String("Teststring 1"));
 
-    stlIt+=5;
+    std::advance(stlIt, 5);
     QCOMPARE(stlIt.value(), QLatin1String("Teststring 6"));
 
     stlIt++;
     QCOMPARE(stlIt.value(), QLatin1String("Teststring 7"));
 
-    stlIt-=3;
+    std::advance(stlIt, -3);
     QCOMPARE(stlIt.value(), QLatin1String("Teststring 4"));
 
     stlIt--;
@@ -791,13 +791,13 @@ void tst_QMap::iterators()
     QMap<int, QString>::const_iterator cstlIt = map.constBegin();
     QCOMPARE(cstlIt.value(), QLatin1String("Teststring 1"));
 
-    cstlIt+=5;
+    std::advance(cstlIt, 5);
     QCOMPARE(cstlIt.value(), QLatin1String("Teststring 6"));
 
     cstlIt++;
     QCOMPARE(cstlIt.value(), QLatin1String("Teststring 7"));
 
-    cstlIt-=3;
+    std::advance(cstlIt, -3);
     QCOMPARE(cstlIt.value(), QLatin1String("Teststring 4"));
 
     cstlIt--;
@@ -926,28 +926,23 @@ void tst_QMap::keyValueIterator()
 
 void tst_QMap::keys_values_uniqueKeys()
 {
-    QMap<QString, int> map;
-    QVERIFY(map.uniqueKeys().isEmpty());
+    QMultiMap<QString, int> map;
     QVERIFY(map.keys().isEmpty());
     QVERIFY(map.values().isEmpty());
 
     map.insertMulti("alpha", 1);
     QVERIFY(map.keys() == (QList<QString>() << "alpha"));
-    QVERIFY(map.uniqueKeys() == map.keys());
     QVERIFY(map.values() == (QList<int>() << 1));
 
     map.insertMulti("beta", -2);
     QVERIFY(map.keys() == (QList<QString>() << "alpha" << "beta"));
-    QVERIFY(map.keys() == map.uniqueKeys());
     QVERIFY(map.values() == (QList<int>() << 1 << -2));
 
     map.insertMulti("alpha", 2);
-    QVERIFY(map.uniqueKeys() == (QList<QString>() << "alpha" << "beta"));
     QVERIFY(map.keys() == (QList<QString>() << "alpha" << "alpha" << "beta"));
     QVERIFY(map.values() == (QList<int>() << 2 << 1 << -2));
 
     map.insertMulti("beta", 4);
-    QVERIFY(map.uniqueKeys() == (QList<QString>() << "alpha" << "beta"));
     QVERIFY(map.keys() == (QList<QString>() << "alpha" << "alpha" << "beta" << "beta"));
     QVERIFY(map.values() == (QList<int>() << 2 << 1 << 4 << -2));
 }
@@ -1077,14 +1072,14 @@ void tst_QMap::const_shared_null()
 
 void tst_QMap::equal_range()
 {
-    QMap<int, QString> map;
-    const QMap<int, QString> &cmap = map;
+    QMultiMap<int, QString> map;
+    const QMultiMap<int, QString> &cmap = map;
 
-    QPair<QMap<int, QString>::iterator, QMap<int, QString>::iterator> result = map.equal_range(0);
+    QPair<QMultiMap<int, QString>::iterator, QMultiMap<int, QString>::iterator> result = map.equal_range(0);
     QCOMPARE(result.first, map.end());
     QCOMPARE(result.second, map.end());
 
-    QPair<QMap<int, QString>::const_iterator, QMap<int, QString>::const_iterator> cresult = cmap.equal_range(0);
+    QPair<QMultiMap<int, QString>::const_iterator, QMultiMap<int, QString>::const_iterator> cresult = cmap.equal_range(0);
     QCOMPARE(cresult.first, cmap.cend());
     QCOMPARE(cresult.second, cmap.cend());
 
@@ -1294,10 +1289,10 @@ void tst_QMap::insertMap()
         // make sure this isn't adding multiple entries with the
         // same key to the QMap.
         QMap<int, int> map;
-        QMultiMap<int, int> map2;
-        map2.insert(0, 0);
+        map.insert(0, 0);
+
+        QMap<int, int> map2;
         map2.insert(0, 1);
-        map2.insert(0, 2);
 
         map.insert(map2);
 
@@ -1452,11 +1447,11 @@ void tst_QMap::testInsertWithHint()
 
 void tst_QMap::testInsertMultiWithHint()
 {
-    QMap<int, int> map;
+    QMultiMap<int, int> map;
 
     map.insertMulti(map.end(), 64, 65);
-    map[128] = 129;
-    map[256] = 257;
+    map.insert(128, 129);
+    map.insert(256, 257);
     sanityCheckTree(map, __LINE__);
 
     map.insertMulti(map.end(), 512, 513);
@@ -1467,11 +1462,11 @@ void tst_QMap::testInsertMultiWithHint()
     sanityCheckTree(map, __LINE__);
     QCOMPARE(map.size(), 6);
 
-    QMap<int, int>::iterator i = map.insertMulti(map.constBegin(), 256, 259); // wrong hint
+    QMultiMap<int, int>::iterator i = map.insertMulti(map.constBegin(), 256, 259); // wrong hint
     sanityCheckTree(map, __LINE__);
     QCOMPARE(map.size(), 7);
 
-    QMap<int, int>::iterator j = map.insertMulti(map.constBegin(), 69, 66);
+    QMultiMap<int, int>::iterator j = map.insertMulti(map.constBegin(), 69, 66);
     sanityCheckTree(map, __LINE__);
     QCOMPARE(map.size(), 8);
 
@@ -1502,14 +1497,14 @@ void tst_QMap::testInsertMultiWithHint()
 
 void tst_QMap::eraseValidIteratorOnSharedMap()
 {
-    QMap<int, int> a, b;
+    QMultiMap<int, int> a, b;
     a.insert(10, 10);
     a.insertMulti(10, 40);
     a.insertMulti(10, 25);
     a.insertMulti(10, 30);
     a.insert(20, 20);
 
-    QMap<int, int>::iterator i = a.begin();
+    QMultiMap<int, int>::iterator i = a.begin();
     while (i.value() != 25)
         ++i;
 
@@ -1529,12 +1524,12 @@ void tst_QMap::eraseValidIteratorOnSharedMap()
     QCOMPARE(itemsWith10, 4);
 
     // Border cases
-    QMap <QString, QString> ms1, ms2, ms3;
+    QMultiMap <QString, QString> ms1, ms2, ms3;
     ms1.insert("foo", "bar");
     ms1.insertMulti("foo", "quux");
     ms1.insertMulti("foo", "bar");
 
-    QMap <QString, QString>::iterator si = ms1.begin();
+    QMultiMap <QString, QString>::iterator si = ms1.begin();
     ms2 = ms1;
     ms1.erase(si);
     si = ms1.begin();