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 /LICENSE.GPL | |
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 'LICENSE.GPL')
0 files changed, 0 insertions, 0 deletions