summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/corelib/tools/qmap.cpp26
-rw-r--r--src/corelib/tools/qmap.h67
-rw-r--r--tests/auto/corelib/tools/qmap/tst_qmap.cpp65
-rw-r--r--tests/benchmarks/corelib/tools/qmap/main.cpp78
4 files changed, 236 insertions, 0 deletions
diff --git a/src/corelib/tools/qmap.cpp b/src/corelib/tools/qmap.cpp
index a4c28b5bd4..21ac059a01 100644
--- a/src/corelib/tools/qmap.cpp
+++ b/src/corelib/tools/qmap.cpp
@@ -981,6 +981,32 @@ void QMapDataBase::freeData(QMapDataBase *d)
\sa insertMulti()
*/
+/*! \fn QMap::iterator QMap::insert(const_iterator pos, const Key &key, const T &value)
+ \overload
+ \since 5.1
+ Inserts a new item with the key \a key and value \a value and with hint \a pos
+ suggesting where to do the insert.
+
+ If constBegin() is used as hint it indicates that the \a key is less than any key in the map
+ while constEnd() suggests that the \a key is (strictly) larger than any key in the map.
+ Otherwise the hint should meet the condition (\a pos - 1).key() < \a key <= pos.key().
+ If the hint \a pos is wrong it is ignored and a regular insert is done.
+
+ If there is already an item with the key \a key, that item's value
+ is replaced with \a value.
+
+ If there are multiple items with the key \a key, then exactly one of them
+ is replaced with \a value.
+
+ When creating a map from sorted data inserting the largest key first with constBegin()
+ is faster than inserting in sorted order with constEnd()
+
+ \b {Note:} Be careful with the hint. Providing an iterator from an older shared instance might
+ crash but there is also a risk that it will silently corrupt both the map and the \a pos map.
+
+ \sa insertMulti()
+*/
+
/*! \fn 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 280696c534..31a891b0c2 100644
--- a/src/corelib/tools/qmap.h
+++ b/src/corelib/tools/qmap.h
@@ -538,6 +538,7 @@ public:
iterator upperBound(const Key &key);
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);
iterator insertMulti(const Key &key, const T &value);
QMap<Key, T> &unite(const QMap<Key, T> &other);
@@ -663,6 +664,72 @@ Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key
}
template <class Key, class T>
+typename QMap<Key, T>::iterator QMap<Key, T>::insert(const_iterator pos, const Key &akey, const T &avalue)
+{
+ if (d->ref.isShared())
+ return this->insert(akey, avalue);
+
+ if (pos == constEnd()) {
+ // Hint is that the Node is larger than (or equal to) the largest value.
+ Node *n = static_cast<Node *>(pos.i->left);
+ if (n) {
+ while (n->right)
+ n = static_cast<Node *>(n->right);
+
+ if (!qMapLessThanKey(n->key, akey))
+ return this->insert(akey, avalue); // ignore hint
+ // This can be optimized by checking equal too.
+ // we can overwrite if previous node key is strictly smaller
+ // (or there is no previous node)
+
+ Node *z = d->createNode(akey, avalue, n, false); // insert right most
+ return iterator(z);
+ }
+ return this->insert(akey, avalue);
+ } else {
+ // Hint indicates that the node should be less (or equal to) the hint given
+ // but larger than the previous value.
+ Node *next = const_cast<Node*>(pos.i);
+ if (qMapLessThanKey(next->key, akey))
+ return this->insert(akey, avalue); // ignore hint
+
+ if (pos == constBegin()) {
+ // There is no previous value
+ // Maybe overwrite left most value
+ if (!qMapLessThanKey(akey, next->key)) {
+ next->value = avalue; // overwrite current iterator
+ return iterator(next);
+ }
+ // insert left most.
+ Node *z = d->createNode(akey, avalue, begin().i, true);
+ return iterator(z);
+ } else {
+ Node *prev = const_cast<Node*>(pos.i->previousNode());
+ if (!qMapLessThanKey(prev->key, akey)) {
+ return this->insert(akey, avalue); // ignore hint
+ }
+ // Hint is ok
+ if (!qMapLessThanKey(akey, next->key)) {
+ next->value = avalue; // overwrite current iterator
+ return iterator(next);
+ }
+
+ // we need to insert (not overwrite)
+ if (prev->right == 0) {
+ Node *z = d->createNode(akey, avalue, prev, false);
+ return iterator(z);
+ }
+ if (next->left == 0) {
+ Node *z = d->createNode(akey, avalue, next, true);
+ return iterator(z);
+ }
+ Q_ASSERT(false); // We should have prev->right == 0 or next->left == 0.
+ return this->insert(akey, avalue);
+ }
+ }
+}
+
+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 801656e1c3..66063d0262 100644
--- a/tests/auto/corelib/tools/qmap/tst_qmap.cpp
+++ b/tests/auto/corelib/tools/qmap/tst_qmap.cpp
@@ -85,6 +85,7 @@ private slots:
void insert();
void checkMostLeftNode();
void initializerList();
+ void testInsertWithHint();
};
typedef QMap<QString, QString> StringMap;
@@ -1159,5 +1160,69 @@ void tst_QMap::initializerList()
#endif
}
+void tst_QMap::testInsertWithHint()
+{
+ QMap<int, int> map;
+ map.setSharable(false);
+
+ // Check with end hint();
+ map.insert(map.constEnd(), 3, 1); // size == 1
+ sanityCheckTree(map, __LINE__);
+ map.insert(map.constEnd(), 5, 1); // size = 2
+ sanityCheckTree(map, __LINE__);
+ map.insert(map.constEnd(), 50, 1); // size = 3
+ sanityCheckTree(map, __LINE__);
+ QMap<int, int>::const_iterator key75(map.insert(map.constEnd(), 75, 1)); // size = 4
+ sanityCheckTree(map, __LINE__);
+ map.insert(map.constEnd(), 100, 1); // size = 5
+ sanityCheckTree(map, __LINE__);
+ map.insert(map.constEnd(), 105, 1); // size = 6
+ sanityCheckTree(map, __LINE__);
+ map.insert(map.constEnd(), 10, 5); // invalid hint and size = 7
+ sanityCheckTree(map, __LINE__);
+ QMap<int, int>::iterator lastkey = map.insert(map.constEnd(), 105, 12); // overwrite
+ sanityCheckTree(map, __LINE__);
+ QCOMPARE(lastkey.value(), 12);
+ QCOMPARE(lastkey.key(), 105);
+ QCOMPARE(map.size(), 7);
+
+ // With regular hint
+ map.insert(key75, 75, 100); // overwrite current key
+ sanityCheckTree(map, __LINE__);
+ QCOMPARE(map.size(), 7);
+ QCOMPARE(key75.key(), 75);
+ QCOMPARE(key75.value(), 100);
+
+ map.insert(key75, 50, 101); // overwrite previous value
+ QMap<int, int>::const_iterator key50(key75);
+ --key50;
+ QCOMPARE(map.size(), 7);
+ QCOMPARE(key50.key(), 50);
+ QCOMPARE(key50.value(), 101);
+
+ map.insert(key75, 17, 125); // invalid hint - size 8
+ sanityCheckTree(map, __LINE__);
+ QCOMPARE(map.size(), 8);
+
+ // begin
+ map.insert(map.constBegin(), 1, 1); // size 9
+ sanityCheckTree(map, __LINE__);
+ QCOMPARE(map.size(), 9);
+
+ map.insert(map.constBegin(), 1, 10); // overwrite existing (leftmost) value
+ QCOMPARE(map.constBegin().value(), 10);
+
+ map.insert(map.constBegin(), 47, 47); // wrong hint - size 10
+ sanityCheckTree(map, __LINE__);
+ QCOMPARE(map.size(), 10);
+
+ // insert with right == 0
+ QMap<int, int>::const_iterator i1 (map.insert(key75, 70, 12)); // overwrite
+ map.insert(i1, 69, 12); // size 12
+
+ sanityCheckTree(map, __LINE__);
+ QCOMPARE(map.size(), 12);
+}
+
QTEST_APPLESS_MAIN(tst_QMap)
#include "tst_qmap.moc"
diff --git a/tests/benchmarks/corelib/tools/qmap/main.cpp b/tests/benchmarks/corelib/tools/qmap/main.cpp
index e0bd994967..53b2a90fab 100644
--- a/tests/benchmarks/corelib/tools/qmap/main.cpp
+++ b/tests/benchmarks/corelib/tools/qmap/main.cpp
@@ -64,6 +64,14 @@ private slots:
void iterator_begin();
void ctorStdMap();
+
+ void insertion_int_intx();
+ void insertion_int_int_with_hint1();
+ void insertion_int_int2();
+ void insertion_int_int_with_hint2();
+
+ void insertion_string_int2();
+ void insertion_string_int2_hint();
};
@@ -76,6 +84,44 @@ void tst_QMap::insertion_int_int()
}
}
+void tst_QMap::insertion_int_intx()
+{
+ // This is the same test - but executed later.
+ // The results in the beginning of the test seems to be a somewhat inaccurate.
+ QMap<int, int> map;
+ QBENCHMARK {
+ for (int i = 0; i < 100000; ++i)
+ map.insert(i, i);
+ }
+}
+
+void tst_QMap::insertion_int_int_with_hint1()
+{
+ QMap<int, int> map;
+ QBENCHMARK {
+ for (int i = 0; i < 100000; ++i)
+ map.insert(map.constEnd(), i, i);
+ }
+}
+
+void tst_QMap::insertion_int_int2()
+{
+ QMap<int, int> map;
+ QBENCHMARK {
+ for (int i = 100000; i >= 0; --i)
+ map.insert(i, i);
+ }
+}
+
+void tst_QMap::insertion_int_int_with_hint2()
+{
+ QMap<int, int> map;
+ QBENCHMARK {
+ for (int i = 100000; i >= 0; --i)
+ map.insert(map.constBegin(), i, i);
+ }
+}
+
void tst_QMap::insertion_int_string()
{
QMap<int, QString> map;
@@ -203,6 +249,38 @@ void tst_QMap::ctorStdMap()
}
}
+class XString : public QString
+{
+public:
+ bool operator < (const XString& x) const // an expensive operator <
+ {
+ return toInt() < x.toInt();
+ }
+};
+
+void tst_QMap::insertion_string_int2()
+{
+ QMap<XString, int> map;
+ QBENCHMARK {
+ for (int i = 1; i < 5000; ++i) {
+ XString str;
+ str.setNum(i);
+ map.insert(str, i);
+ }
+ }
+}
+
+void tst_QMap::insertion_string_int2_hint()
+{
+ QMap<XString, int> map;
+ QBENCHMARK {
+ for (int i = 1; i < 5000; ++i) {
+ XString str;
+ str.setNum(i);
+ map.insert(map.end(), str, i);
+ }
+ }
+}
QTEST_MAIN(tst_QMap)
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-25 17:18:26 +0000