summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMårten Nordheim <marten.nordheim@qt.io>2019-11-06 18:04:45 +0100
committerMårten Nordheim <marten.nordheim@qt.io>2019-12-12 15:25:30 +0100
commitd98a1ef902527ca2351ec6bf18872a4226953487 (patch)
tree6594fdbdb40f75f4b87d9fd23d04f3e68dbff8f5
parent9c124b1b0a3730978699b8a6420308b5e5ab4e4e (diff)
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 <lars.knoll@qt.io>
-rw-r--r--src/corelib/tools/qmap.cpp14
-rw-r--r--src/corelib/tools/qmap.h44
-rw-r--r--tests/auto/corelib/tools/qmap/tst_qmap.cpp96
-rw-r--r--tests/benchmarks/corelib/tools/qmap/main.cpp15
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"