diff options
author | Thorbjørn Lund Martsum <tmartsum@gmail.com> | 2012-09-27 14:56:43 +0200 |
---|---|---|
committer | The Qt Project <gerrit-noreply@qt-project.org> | 2012-10-27 07:35:57 +0200 |
commit | 6e4d7bbb0baeff2362e3d25be6aedcb68e7909b0 (patch) | |
tree | 40c0cc4ecaaa9db45205d83bfbfac93f99f993b0 /tests/benchmarks/corelib | |
parent | cfc3eeea1b3fbf31998deef65fb01214d44d36fd (diff) |
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>
Diffstat (limited to 'tests/benchmarks/corelib')
-rw-r--r-- | tests/benchmarks/corelib/tools/qmap/main.cpp | 17 |
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" |