QMap 5.0 - keep track of leftmost node (BIC)

This suggestion keeps track of the most left node.
The point is that constBegin() becomes a lot faster.

That speeds up iteration a bit, and makes it O(1) to get the
first element. The penalty in insert and remove is very small.
On large trees it seems to be less than 1%.

It should be noticed that constBegin() is a very common hint
on my planned change to 5.1, and this opperation will without
this patch cost 2 x log N. One when the user calls the hint
with begin - and one where it is compared with begin.

Other std::maps has a very fast begin(). E.g
http://www.cplusplus.com/reference/stl/map/begin/
(begin with constant time)

Change-Id: I221f6755aa8bd16a5189771c5bc8ae56c8ee0fb4
Reviewed-by: Lars Knoll <lars.knoll@digia.com>

1 files changed, 17 insertions, 0 deletions

diff --git a/tests/benchmarks/corelib/tools/qmap/main.cpp b/tests/benchmarks/corelib/tools/qmap/main.cpp
index c3b9c18cd2..4d9833b7a1 100644
--- a/tests/benchmarks/corelib/tools/qmap/main.cpp
+++ b/tests/benchmarks/corelib/tools/qmap/main.cpp
@@ -61,6 +61,7 @@ private slots:
 
     void iteration();
     void toStdMap();
+    void iterator_begin();
 };
 
 
@@ -172,6 +173,22 @@ void tst_QMap::toStdMap()
     }
 }
 
+void tst_QMap::iterator_begin()
+{
+    QMap<int, int> map;
+    for (int i = 0; i < 100000; ++i)
+        map.insert(i, i);
+
+    QBENCHMARK {
+        for (int i = 0; i < 100000; ++i) {
+            QMap<int, int>::const_iterator it = map.constBegin();
+            QMap<int, int>::const_iterator end = map.constEnd();
+            if (it == end) // same as if (false)
+                ++it;
+        }
+    }
+}
+
 QTEST_MAIN(tst_QMap)
 
 #include "main.moc"