diff options
-rw-r--r-- | src/corelib/tools/qmap.cpp | 14 | ||||
-rw-r--r-- | src/corelib/tools/qmap.h | 44 | ||||
-rw-r--r-- | tests/auto/corelib/tools/qmap/tst_qmap.cpp | 96 | ||||
-rw-r--r-- | tests/benchmarks/corelib/tools/qmap/main.cpp | 15 |
4 files changed, 169 insertions, 0 deletions
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 <class Key, class T> void QMap<Key, T>::insert(const QMap<Key, T> &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 <class Key, class T> QMap<Key, T>::iterator QMap<Key, T>::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<Key, T> &map); iterator insertMulti(const Key &key, const T &value); iterator insertMulti(const_iterator pos, const Key &akey, const T &avalue); QMap<Key, T> &unite(const QMap<Key, T> &other); @@ -789,6 +790,49 @@ typename QMap<Key, T>::iterator QMap<Key, T>::insert(const_iterator pos, const K } 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()); + } + } +} + +template <class Key, class T> Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::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<int, int> map; + map.insert(1, 1); + map.insert(2, 2); + map.insert(0, -1); + + QMap<int, int> 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<int, int> map; + for (int i = 0; i < 10; ++i) + map.insert(i * 3, i); + + QMap<int, int> 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<int, int> map; + map.insert(1, 1); + + QMap<int, int> map2; + + map.insert(map2); + QCOMPARE(map.count(), 1); + QCOMPARE(map[1], 1); + } + { + QMap<int, int> map; + QMap<int, int> map2; + map2.insert(1, 1); + + map.insert(map2); + QCOMPARE(map.count(), 1); + QCOMPARE(map[1], 1); + } + { + QMap<int, int> 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<int, int> map; + QMultiMap<int, int> 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<int, int> 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<int, int> map; + for (int i = 0; i < 100000; ++i) + map.insert(i * 4, 0); + QMap<int, int> 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" |