diff options
author | Sérgio Martins <sergio.martins@kdab.com> | 2016-02-07 02:49:33 +0000 |
---|---|---|
committer | Marc Mutz <marc.mutz@kdab.com> | 2016-02-14 06:43:52 +0000 |
commit | 6139fbeb5f41843e524ec40ce5be57f0df23e922 (patch) | |
tree | aef02a79ced348171b165830d653b26fef7cc89a /src | |
parent | 26dca142a75e71baad26583cd467d07e3b116e59 (diff) |
Introduce QHash::equal_range()
Similar to QMap::equal_range().
Will allow to easily fix inefficient code such as:
foreach (auto value, hash.values(key)) { ... }
[ChangeLog][QtCore][QHash] Added QHash::equal_range()
Change-Id: I6e19e25de632e897ad83d3141d9d07f0313f7200
Reviewed-by: Marc Mutz <marc.mutz@kdab.com>
Diffstat (limited to 'src')
-rw-r--r-- | src/corelib/tools/qhash.cpp | 13 | ||||
-rw-r--r-- | src/corelib/tools/qhash.h | 35 |
2 files changed, 48 insertions, 0 deletions
diff --git a/src/corelib/tools/qhash.cpp b/src/corelib/tools/qhash.cpp index c1a1b9715f..b49c9d683a 100644 --- a/src/corelib/tools/qhash.cpp +++ b/src/corelib/tools/qhash.cpp @@ -1803,6 +1803,19 @@ uint qHash(long double key, uint seed) Q_DECL_NOTHROW returns \c false. */ +/*! \fn QPair<iterator, iterator> QHash::equal_range(const Key &key) + \since 5.7 + + Returns a pair of iterators delimiting the range of values \c{[first, second)}, that + are stored under \a key. If the range is empty then both iterators will be equal to end(). +*/ + +/*! + \fn QPair<const_iterator, const_iterator> QHash::equal_range(const Key &key) const + \overload + \since 5.7 +*/ + /*! \typedef QHash::ConstIterator Qt-style synonym for QHash::const_iterator. diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h index 819631932b..5e3016d313 100644 --- a/src/corelib/tools/qhash.h +++ b/src/corelib/tools/qhash.h @@ -458,6 +458,8 @@ public: inline key_iterator keyBegin() const { return key_iterator(begin()); } inline key_iterator keyEnd() const { return key_iterator(end()); } + QPair<iterator, iterator> equal_range(const Key &key); + QPair<const_iterator, const_iterator> equal_range(const Key &key) const Q_DECL_NOTHROW; iterator erase(iterator it) { return erase(const_iterator(it.i)); } iterator erase(const_iterator it); @@ -945,6 +947,39 @@ Q_OUTOFLINE_TEMPLATE bool QHash<Key, T>::operator==(const QHash &other) const } template <class Key, class T> +QPair<typename QHash<Key, T>::iterator, typename QHash<Key, T>::iterator> QHash<Key, T>::equal_range(const Key &akey) +{ + detach(); + auto pair = qAsConst(*this).equal_range(akey); + return qMakePair(iterator(pair.first.i), iterator(pair.second.i)); +} + +template <class Key, class T> +QPair<typename QHash<Key, T>::const_iterator, typename QHash<Key, T>::const_iterator> QHash<Key, T>::equal_range(const Key &akey) const Q_DECL_NOTHROW +{ + uint h; + Node *node = *findNode(akey, &h); + const_iterator firstIt = const_iterator(node); + + if (node != e) { + // equal keys must hash to the same value and so they all + // end up in the same bucket. So we can use node->next, + // which only works within a bucket, instead of (out-of-line) + // QHashData::nextNode() + while (node->next != e && node->next->key == akey) + node = node->next; + + // 'node' may be the last node in the bucket. To produce the end iterator, we'd + // need to enter the next bucket in this case, so we need to use + // QHashData::nextNode() here, which, unlike node->next above, can move between + // buckets. + node = concrete(QHashData::nextNode(reinterpret_cast<QHashData::Node *>(node))); + } + + return qMakePair(firstIt, const_iterator(node)); +} + +template <class Key, class T> class QMultiHash : public QHash<Key, T> { public: |