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 /src/corelib/tools/qmap.h | |
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 'src/corelib/tools/qmap.h')
-rw-r--r-- | src/corelib/tools/qmap.h | 8 |
1 files changed, 6 insertions, 2 deletions
diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h index 0e726e8394..e0b267ce20 100644 --- a/src/corelib/tools/qmap.h +++ b/src/corelib/tools/qmap.h @@ -173,11 +173,13 @@ struct Q_CORE_EXPORT QMapDataBase QtPrivate::RefCount ref; int size; QMapNodeBase header; + QMapNodeBase *mostLeftNode; void rotateLeft(QMapNodeBase *x); void rotateRight(QMapNodeBase *x); void rebalance(QMapNodeBase *x); void freeNodeAndRebalance(QMapNodeBase *z); + void recalcMostLeftNode(); QMapNodeBase *createNode(int size, int alignment, QMapNodeBase *parent, bool left); void freeTree(QMapNodeBase *root, int alignment); @@ -197,8 +199,8 @@ struct QMapData : public QMapDataBase const Node *end() const { return static_cast<const Node *>(&header); } Node *end() { return static_cast<Node *>(&header); } - const Node *begin() const { if (root()) return root()->minimumNode(); return end(); } - Node *begin() { if (root()) return root()->minimumNode(); return end(); } + const Node *begin() const { if (root()) return static_cast<const Node*>(mostLeftNode); return end(); } + Node *begin() { if (root()) return static_cast<Node*>(mostLeftNode); return end(); } void deleteNode(Node *z); Node *findNode(const Key &akey) const; @@ -555,6 +557,7 @@ inline QMap<Key, T>::QMap(const QMap<Key, T> &other) if (other.d->header.left) { d->header.left = static_cast<Node *>(other.d->header.left)->copy(d); d->header.left->setParent(&d->header); + d->recalcMostLeftNode(); } } } @@ -780,6 +783,7 @@ Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::detach_helper() if (!d->ref.deref()) d->destroy(); d = x; + d->recalcMostLeftNode(); } template <class Key, class T> |