QMap 5.0 - keep track of leftmost node (BIC)
authorThorbjørn Lund Martsum <tmartsum@gmail.com>
Thu, 27 Sep 2012 12:56:43 +0000 (14:56 +0200)
committerThe Qt Project <gerrit-noreply@qt-project.org>
Sat, 27 Oct 2012 05:35:57 +0000 (07:35 +0200)
commit6e4d7bbb0baeff2362e3d25be6aedcb68e7909b0
tree40c0cc4ecaaa9db45205d83bfbfac93f99f993b0
parentcfc3eeea1b3fbf31998deef65fb01214d44d36fd
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>
src/corelib/tools/qmap.cpp
src/corelib/tools/qmap.h
tests/auto/corelib/tools/qmap/tst_qmap.cpp
tests/benchmarks/corelib/tools/qmap/main.cpp