summaryrefslogtreecommitdiffstats
path: root/src/corelib/tools/qmap.h
diff options
context:
space:
mode:
authorMathias Hasselmann <mathias.hasselmann@kdab.com>2013-07-04 13:27:15 +0200
committerThe Qt Project <gerrit-noreply@qt-project.org>2013-09-08 16:13:16 +0200
commit50e2db6a752b5d8b3af3023ff4cebb13ef2b9a2a (patch)
tree7c20be51f02606d8c9e2269a3d37da1bea6d49cc /src/corelib/tools/qmap.h
parent69e21f1a86c201b817611d0bb237999e809cde0f (diff)
Add first/last accessors to QMap
QMap explicitly sorts its entries by key value. For an ordered container it's (often?) useful to access the first or last entry, for instance to quickly compute the next key of the mapping. The first entry is easily accessible by the STL begin() method, but for accessing the last entry pretty ugly iterator arithmetics must be applied: *(end() - 1). With their first() and last() accessors the container classes QList and QVector provide a much nicer method of accessing extrema, so for consistency this syntactical sugar also should be applied to QMap. Change-Id: Ibd544acbad8c3ac16f12a1e74362207ea1694375 Reviewed-by: Thiago Macieira <thiago.macieira@intel.com> Reviewed-by: Thorbjørn Lund Martsum <tmartsum@gmail.com>
Diffstat (limited to 'src/corelib/tools/qmap.h')
-rw-r--r--src/corelib/tools/qmap.h62
1 files changed, 35 insertions, 27 deletions
diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h
index c030a76666..29e8f9b140 100644
--- a/src/corelib/tools/qmap.h
+++ b/src/corelib/tools/qmap.h
@@ -140,32 +140,32 @@ template <class Key, class T>
inline QMapNode<Key, T> *QMapNode<Key, T>::lowerBound(const Key &akey)
{
QMapNode<Key, T> *n = this;
- QMapNode<Key, T> *last = 0;
+ QMapNode<Key, T> *lastNode = 0;
while (n) {
if (!qMapLessThanKey(n->key, akey)) {
- last = n;
+ lastNode = n;
n = n->leftNode();
} else {
n = n->rightNode();
}
}
- return last;
+ return lastNode;
}
template <class Key, class T>
inline QMapNode<Key, T> *QMapNode<Key, T>::upperBound(const Key &akey)
{
QMapNode<Key, T> *n = this;
- QMapNode<Key, T> *last = 0;
+ QMapNode<Key, T> *lastNode = 0;
while (n) {
if (qMapLessThanKey(akey, n->key)) {
- last = n;
+ lastNode = n;
n = n->leftNode();
} else {
n = n->rightNode();
}
}
- return last;
+ return lastNode;
}
@@ -206,7 +206,7 @@ struct QMapData : public QMapDataBase
void deleteNode(Node *z);
Node *findNode(const Key &akey) const;
- void nodeRange(const Key &akey, Node **first, Node **last);
+ void nodeRange(const Key &akey, Node **firstNode, Node **lastNode);
Node *createNode(const Key &k, const T &v, Node *parent = 0, bool left = false)
{
@@ -296,7 +296,7 @@ QMapNode<Key, T> *QMapData<Key, T>::findNode(const Key &akey) const
template <class Key, class T>
-void QMapData<Key, T>::nodeRange(const Key &akey, QMapNode<Key, T> **first, QMapNode<Key, T> **last)
+void QMapData<Key, T>::nodeRange(const Key &akey, QMapNode<Key, T> **firstNode, QMapNode<Key, T> **lastNode)
{
Node *n = root();
Node *l = end();
@@ -307,16 +307,16 @@ void QMapData<Key, T>::nodeRange(const Key &akey, QMapNode<Key, T> **first, QMap
} else if (qMapLessThanKey(n->key, akey)) {
n = n->rightNode();
} else {
- *first = n->leftNode()->lowerBound(akey);
- if (!*first)
- *first = n;
- *last = n->rightNode()->upperBound(akey);
- if (!*last)
- *last = l;
+ *firstNode = n->leftNode()->lowerBound(akey);
+ if (!*firstNode)
+ *firstNode = n;
+ *lastNode = n->rightNode()->upperBound(akey);
+ if (!*lastNode)
+ *lastNode = l;
return;
}
}
- *first = *last = l;
+ *firstNode = *lastNode = l;
}
@@ -395,6 +395,14 @@ public:
QList<T> values(const Key &key) const;
int count(const Key &key) const;
+ inline const Key &firstKey() const { Q_ASSERT(!isEmpty()); return constBegin().key(); }
+ inline const Key &lastKey() const { Q_ASSERT(!isEmpty()); return (constEnd() - 1).key(); }
+
+ inline T &first() { Q_ASSERT(!isEmpty()); return *begin(); }
+ inline const T &first() const { Q_ASSERT(!isEmpty()); return *constBegin(); }
+ inline T &last() { Q_ASSERT(!isEmpty()); return *(end() - 1); }
+ inline const T &last() const { Q_ASSERT(!isEmpty()); return *(constEnd() - 1); }
+
class const_iterator;
class iterator
@@ -633,12 +641,12 @@ Q_INLINE_TEMPLATE int QMap<Key, T>::count(const Key &akey) const
Node *lastNode;
d->nodeRange(akey, &firstNode, &lastNode);
- const_iterator first(firstNode);
- const const_iterator last(lastNode);
+ const_iterator ci_first(firstNode);
+ const const_iterator ci_last(lastNode);
int cnt = 0;
- while (first != last) {
+ while (ci_first != ci_last) {
++cnt;
- ++first;
+ ++ci_first;
}
return cnt;
}
@@ -655,12 +663,12 @@ Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key
detach();
Node *n = d->root();
Node *y = d->end();
- Node *last = 0;
+ Node *lastNode = 0;
bool left = true;
while (n) {
y = n;
if (!qMapLessThanKey(n->key, akey)) {
- last = n;
+ lastNode = n;
left = true;
n = n->leftNode();
} else {
@@ -668,9 +676,9 @@ Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key
n = n->rightNode();
}
}
- if (last && !qMapLessThanKey(akey, last->key)) {
- last->value = avalue;
- return iterator(last);
+ if (lastNode && !qMapLessThanKey(akey, lastNode->key)) {
+ lastNode->value = avalue;
+ return iterator(lastNode);
}
Node *z = d->createNode(akey, avalue, y, left);
return iterator(z);
@@ -852,9 +860,9 @@ template <class Key, class T>
QPair<typename QMap<Key, T>::iterator, typename QMap<Key, T>::iterator> QMap<Key, T>::equal_range(const Key &akey)
{
detach();
- Node *first, *last;
- d->nodeRange(akey, &first, &last);
- return QPair<iterator, iterator>(iterator(first), iterator(last));
+ Node *firstNode, *lastNode;
+ d->nodeRange(akey, &firstNode, &lastNode);
+ return QPair<iterator, iterator>(iterator(firstNode), iterator(lastNode));
}
#ifdef Q_MAP_DEBUG