QFlatMap: make insertion STL-compatible

That is, insert() doesn't overwrite an existing entry, and range
insert inserts the first of equivalent keys' values, not the last.

This allowed this author to optimize the implementation of
makeUnique() to a O(N) algorithm (was: O(N²)). Said optimization would
have been possible with the old semantics, too, but I wrote the
algorithm first and only then noticed the broken insert() behavior is
present on QFlatMap, too, so I decided not to let good code go to
waste and to fix both problems at the same time.

In order to give users a hint of the changed semantics, make the new
API opt-in until Qt 6.5, so Qt 6.4 ships with the both the old and the
new semantics disabled, where they contradict.

Fixes: QTBUG-100092
Change-Id: Ic96d8bfe6bed9068dbe8c0d7171bd8921050fd95
Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org>
Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>
Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>

1 files changed, 3 insertions, 16 deletions

diff --git a/tests/auto/corelib/tools/qflatmap/tst_qflatmap.cpp b/tests/auto/corelib/tools/qflatmap/tst_qflatmap.cpp
index 2dd6c16f13..ed46a4546a 100644
--- a/tests/auto/corelib/tools/qflatmap/tst_qflatmap.cpp
+++ b/tests/auto/corelib/tools/qflatmap/tst_qflatmap.cpp
@@ -27,6 +27,7 @@
 ****************************************************************************/
 
 #define QT_USE_QSTRINGBUILDER
+#define QFLATMAP_ENABLE_STL_COMPATIBLE_INSERT
 
 #include <QTest>
 
@@ -58,11 +59,9 @@ class tst_QFlatMap : public QObject
 {
     Q_OBJECT
 private slots:
-#ifdef QFLATMAP_TEMPORARILY_REMOVED
     void constructing();
     void constAccess();
     void insertion();
-#endif
     void insertRValuesAndLValues();
     void removal();
     void extraction();
@@ -84,7 +83,6 @@ private:
     void remove_if_impl(Predicate p, bool removeNonEmptyValues = false);
 };
 
-#ifdef QFLATMAP_TEMPORARILY_REMOVED
 void tst_QFlatMap::constructing()
 {
     using Map = QFlatMap<int, QByteArray>;
@@ -169,7 +167,7 @@ void tst_QFlatMap::insertion()
     QCOMPARE(m.value("foo").data(), "FOO");
     QCOMPARE(m.value("bar").data(), "BAR");
     QCOMPARE(m.value("baz").data(), "BAZ");
-    QCOMPARE(m.value("oof").data(), "OOF");
+    QCOMPARE(m.value("oof").data(), "eek");
     QCOMPARE(m.value("bla").data(), "BLA");
     QCOMPARE(m.value("blubb").data(), "BLUBB");
 
@@ -183,14 +181,12 @@ void tst_QFlatMap::insertion()
     m.insert(std::begin(a1), std::end(a1));
     m.insert(Qt::OrderedUniqueRange, std::begin(a2), std::end(a2));
     QCOMPARE(m.size(), 10);
-    QCOMPARE(m.value("narf").data(), "NARFFFFFF");
+    QCOMPARE(m.value("narf").data(), "NARF");
     QCOMPARE(m.value("gnampf").data(), "GNAMPF");
 }
-#endif
 
 void tst_QFlatMap::insertRValuesAndLValues()
 {
-#ifdef QFLATMAP_TEMPORARILY_REMOVED
     using Map = QFlatMap<QByteArray, QByteArray>;
     const QByteArray foo = QByteArrayLiteral("foo");
     const QByteArray bar = QByteArrayLiteral("bar");
@@ -223,7 +219,6 @@ void tst_QFlatMap::insertRValuesAndLValues()
     }
 
 #undef lvalue
-#endif
 }
 
 void tst_QFlatMap::extraction()
@@ -458,7 +453,6 @@ void tst_QFlatMap::remove_if_impl(Pred p, bool removeNonEmptyValues)
 
 void tst_QFlatMap::removal()
 {
-#ifdef QFLATMAP_TEMPORARILY_REMOVED
     using Map = QFlatMap<int, QByteArray>;
     Map m({ { 2, "bar" }, { 3, "baz" }, { 1, "foo" } });
     QCOMPARE(m.value(2).data(), "bar");
@@ -481,12 +475,10 @@ void tst_QFlatMap::removal()
     it = m.erase(it);
     QCOMPARE(it.key(), 2);
     QVERIFY(!m.contains(1));
-#endif
 }
 
 void tst_QFlatMap::statefulComparator()
 {
-#ifdef QFLATMAP_TEMPORARILY_REMOVED
     struct CountingCompare {
         mutable int count = 0;
 
@@ -504,7 +496,6 @@ void tst_QFlatMap::statefulComparator()
     QCOMPARE(m2.key_comp().count, m1.key_comp().count);
     m2.insert(m1.begin(), m1.end());
     QVERIFY(m2.key_comp().count > m1.key_comp().count);
-#endif
 }
 
 void tst_QFlatMap::transparency_using()
@@ -536,7 +527,6 @@ void tst_QFlatMap::transparency_struct()
 template <typename StringViewCompare>
 void tst_QFlatMap::transparency_impl()
 {
-#ifdef QFLATMAP_TEMPORARILY_REMOVED
     using Map = QFlatMap<QString, QString, StringViewCompare>;
     auto m = Map{ { "one", "een" }, { "two", "twee" }, { "three", "dree" } };
 
@@ -560,7 +550,6 @@ void tst_QFlatMap::transparency_impl()
     QVERIFY(m.contains(QLatin1String("one")));
     QVERIFY(m.remove(QAnyStringView(u8"one")));
     QVERIFY(!m.contains(QLatin1String("one")));
-#endif
 }
 
 void tst_QFlatMap::try_emplace_and_insert_or_assign()
@@ -707,7 +696,6 @@ void tst_QFlatMap::try_emplace_and_insert_or_assign()
 
 void tst_QFlatMap::viewIterators()
 {
-#ifdef QFLATMAP_TEMPORARILY_REMOVED
     using Map = QFlatMap<QByteArray, QByteArray>;
     Map m({ { "yksi", "een"}, { "kaksi", "twee" }, { "kolme", "dree" } });
     {
@@ -752,7 +740,6 @@ void tst_QFlatMap::viewIterators()
         it--;
         QCOMPARE(*it, "dree");
     }
-#endif
 }
 
 void tst_QFlatMap::varLengthArray()