From d98a1ef902527ca2351ec6bf18872a4226953487 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?M=C3=A5rten=20Nordheim?= Date: Wed, 6 Nov 2019 18:04:45 +0100 Subject: Add QMap::insert(const QMap &map) As opposed to unite(), this inserts one map into the other without duplicating elements. Task-number: QTBUG-35544 Change-Id: Ie8ab350b29148851a3176cef1007e8a4ca82c273 Reviewed-by: Lars Knoll --- src/corelib/tools/qmap.cpp | 14 ++++ src/corelib/tools/qmap.h | 44 +++++++++++++ tests/auto/corelib/tools/qmap/tst_qmap.cpp | 96 ++++++++++++++++++++++++++++ tests/benchmarks/corelib/tools/qmap/main.cpp | 15 +++++ 4 files changed, 169 insertions(+) diff --git a/src/corelib/tools/qmap.cpp b/src/corelib/tools/qmap.cpp index a0ec372f9a..970373101f 100644 --- a/src/corelib/tools/qmap.cpp +++ b/src/corelib/tools/qmap.cpp @@ -1150,6 +1150,20 @@ void QMapDataBase::freeData(QMapDataBase *d) \sa insertMulti() */ +/*! \fn template void QMap::insert(const QMap &map) + \since 5.15 + + Inserts all the items in \a map into this map. + + If a key is common to both maps, its value will be replaced with + the value stored in \a map. + + \note If \a map contains multiple entries with the same key then the + final value of the key is undefined. + + \sa insertMulti() +*/ + /*! \fn template QMap::iterator QMap::insertMulti(const Key &key, const T &value) Inserts a new item with the key \a key and a value of \a value. diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h index 18c681581f..fa736e8413 100644 --- a/src/corelib/tools/qmap.h +++ b/src/corelib/tools/qmap.h @@ -578,6 +578,7 @@ public: 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 &map); iterator insertMulti(const Key &key, const T &value); iterator insertMulti(const_iterator pos, const Key &akey, const T &avalue); QMap &unite(const QMap &other); @@ -788,6 +789,49 @@ typename QMap::iterator QMap::insert(const_iterator pos, const K } } +template +Q_INLINE_TEMPLATE void QMap::insert(const QMap &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(n->parent()); + } + } +} + template Q_INLINE_TEMPLATE typename QMap::iterator QMap::insertMulti(const Key &akey, const T &avalue) diff --git a/tests/auto/corelib/tools/qmap/tst_qmap.cpp b/tests/auto/corelib/tools/qmap/tst_qmap.cpp index d66fd28779..c3a8a88f0c 100644 --- a/tests/auto/corelib/tools/qmap/tst_qmap.cpp +++ b/tests/auto/corelib/tools/qmap/tst_qmap.cpp @@ -71,6 +71,7 @@ private slots: void setSharable(); void insert(); + void insertMap(); void checkMostLeftNode(); void initializerList(); void testInsertWithHint(); @@ -1265,6 +1266,101 @@ void tst_QMap::insert() } } +void tst_QMap::insertMap() +{ + { + QMap map; + map.insert(1, 1); + map.insert(2, 2); + map.insert(0, -1); + + QMap map2; + map2.insert(0, 0); + map2.insert(3, 3); + map2.insert(4, 4); + + map.insert(map2); + + QCOMPARE(map.count(), 5); + for (int i = 0; i < 5; ++i) + QCOMPARE(map[i], i); + } + { + QMap map; + for (int i = 0; i < 10; ++i) + map.insert(i * 3, i); + + QMap map2; + for (int i = 0; i < 10; ++i) + map2.insert(i * 4, i); + + map.insert(map2); + + QCOMPARE(map.count(), 17); + for (int i = 0; i < 10; ++i) { + // i * 3 == i except for i = 4, 8 + QCOMPARE(map[i * 3], (i && i % 4 == 0) ? i - (i / 4) : i); + QCOMPARE(map[i * 4], i); + } + + auto it = map.cbegin(); + int prev = it.key(); + ++it; + for (auto end = map.cend(); it != end; ++it) { + QVERIFY(prev < it.key()); + prev = it.key(); + } + } + { + QMap map; + map.insert(1, 1); + + QMap map2; + + map.insert(map2); + QCOMPARE(map.count(), 1); + QCOMPARE(map[1], 1); + } + { + QMap map; + QMap map2; + map2.insert(1, 1); + + map.insert(map2); + QCOMPARE(map.count(), 1); + QCOMPARE(map[1], 1); + } + { + QMap map; + map.insert(0, 0); + map.insert(1, 1); + map.insert(2, 2); + + // Test inserting into self, nothing should happen + map.insert(map); + + QCOMPARE(map.count(), 3); + for (int i = 0; i < 3; ++i) + QCOMPARE(map[i], i); + } + { + // Here we use a QMultiMap and insert that into QMap, + // since it has multiple values with the same key the + // ordering is undefined so we won't test that, but + // make sure this isn't adding multiple entries with the + // same key to the QMap. + QMap map; + QMultiMap map2; + map2.insert(0, 0); + map2.insert(0, 1); + map2.insert(0, 2); + + map.insert(map2); + + QCOMPARE(map.count(), 1); + } +} + void tst_QMap::checkMostLeftNode() { QMap map; diff --git a/tests/benchmarks/corelib/tools/qmap/main.cpp b/tests/benchmarks/corelib/tools/qmap/main.cpp index ce415212e4..50cc853df6 100644 --- a/tests/benchmarks/corelib/tools/qmap/main.cpp +++ b/tests/benchmarks/corelib/tools/qmap/main.cpp @@ -59,6 +59,8 @@ private slots: void insertion_string_int2(); void insertion_string_int2_hint(); + + void insertMap(); }; @@ -269,6 +271,19 @@ void tst_QMap::insertion_string_int2_hint() } } +void tst_QMap::insertMap() +{ + QMap map; + for (int i = 0; i < 100000; ++i) + map.insert(i * 4, 0); + QMap map2; + for (int i = 0; i < 50000; ++i) + map2.insert(i * 7, 0); + QBENCHMARK_ONCE { + map.insert(map2); + } +} + QTEST_MAIN(tst_QMap) #include "main.moc" -- cgit v1.2.3