From 0f923a8ce45a0b9379bf0a43e68897a3a8333fda Mon Sep 17 00:00:00 2001 From: Marc Mutz Date: Thu, 3 Dec 2015 12:56:56 +0100 Subject: QHash/QSet: add erase(const_iterator) This is the signature the functions have in C++11. For the std containers, this is just convenience, but for Qt containers with their implicit sharing problem, the combination of erase() with constFind() can delay a detach until absolutely necessary. [ChangeLog][QtCore][QHash/QSet] Added erase(const_iterator). Change-Id: I2fc841c664cd7515b0f56fd7210fcd17c37f9014 Reviewed-by: David Faure --- src/corelib/tools/qhash.cpp | 7 ++++++- src/corelib/tools/qhash.h | 27 +++++++++++++++++---------- src/corelib/tools/qset.h | 13 ++++++++++++- src/corelib/tools/qset.qdoc | 10 ++++++++-- 4 files changed, 43 insertions(+), 14 deletions(-) diff --git a/src/corelib/tools/qhash.cpp b/src/corelib/tools/qhash.cpp index 7724516a5d..75f1e6a1bc 100644 --- a/src/corelib/tools/qhash.cpp +++ b/src/corelib/tools/qhash.cpp @@ -1632,7 +1632,8 @@ uint qHash(long double key, uint seed) Q_DECL_NOTHROW \sa keyBegin() */ -/*! \fn QHash::iterator QHash::erase(iterator pos) +/*! \fn QHash::iterator QHash::erase(const_iterator pos) + \since 5.7 Removes the (key, value) pair associated with the iterator \a pos from the hash, and returns an iterator to the next item in the @@ -1648,6 +1649,10 @@ uint qHash(long double key, uint seed) Q_DECL_NOTHROW \sa remove(), take(), find() */ +/*! \fn QHash::iterator QHash::erase(iterator pos) + \overload +*/ + /*! \fn QHash::iterator QHash::find(const Key &key) Returns an iterator pointing to the item with the \a key in the diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h index a18dd74706..1098bb6203 100644 --- a/src/corelib/tools/qhash.h +++ b/src/corelib/tools/qhash.h @@ -297,6 +297,7 @@ public: { friend class const_iterator; friend class QHash; + friend class QSet; QHashData::Node *i; public: @@ -353,6 +354,7 @@ public: class const_iterator { friend class iterator; + friend class QHash; friend class QSet; QHashData::Node *i; @@ -450,7 +452,8 @@ public: inline key_iterator keyBegin() const { return key_iterator(begin()); } inline key_iterator keyEnd() const { return key_iterator(end()); } - iterator erase(iterator it); + iterator erase(iterator it) { return erase(const_iterator(it.i)); } + iterator erase(const_iterator it); // more Qt typedef iterator Iterator; @@ -487,15 +490,18 @@ private: static void duplicateNode(QHashData::Node *originalNode, void *newNode); - bool isValidIterator(const iterator &it) const + bool isValidIterator(const iterator &it) const Q_DECL_NOTHROW + { return isValidNode(it.i); } + bool isValidIterator(const const_iterator &it) const Q_DECL_NOTHROW + { return isValidNode(it.i); } + bool isValidNode(QHashData::Node *node) const Q_DECL_NOTHROW { #if defined(QT_DEBUG) && !defined(Q_HASH_NO_ITERATOR_DEBUG) - QHashData::Node *node = it.i; while (node->next) node = node->next; return (static_cast(node) == d); #else - Q_UNUSED(it); + Q_UNUSED(node); return true; #endif } @@ -807,30 +813,31 @@ Q_OUTOFLINE_TEMPLATE T QHash::take(const Key &akey) } template -Q_OUTOFLINE_TEMPLATE typename QHash::iterator QHash::erase(iterator it) +Q_OUTOFLINE_TEMPLATE typename QHash::iterator QHash::erase(const_iterator it) { Q_ASSERT_X(isValidIterator(it), "QHash::erase", "The specified iterator argument 'it' is invalid"); - if (it == iterator(e)) - return it; + if (it == const_iterator(e)) + return iterator(it.i); if (d->ref.isShared()) { + // save 'it' across the detach: int bucketNum = (it.i->h % d->numBuckets); - iterator bucketIterator(*(d->buckets + bucketNum)); + const_iterator bucketIterator(*(d->buckets + bucketNum)); int stepsFromBucketStartToIte = 0; while (bucketIterator != it) { ++stepsFromBucketStartToIte; ++bucketIterator; } detach(); - it = iterator(*(d->buckets + bucketNum)); + it = const_iterator(*(d->buckets + bucketNum)); while (stepsFromBucketStartToIte > 0) { --stepsFromBucketStartToIte; ++it; } } - iterator ret = it; + iterator ret(it.i); ++ret; Node *node = concrete(it.i); diff --git a/src/corelib/tools/qset.h b/src/corelib/tools/qset.h index 3f4208e8b3..7c894706a9 100644 --- a/src/corelib/tools/qset.h +++ b/src/corelib/tools/qset.h @@ -98,6 +98,7 @@ public: typedef QHash Hash; typename Hash::iterator i; friend class const_iterator; + friend class QSet; public: typedef std::bidirectional_iterator_tag iterator_category; @@ -183,9 +184,11 @@ public: const_reverse_iterator crend() const Q_DECL_NOTHROW { return const_reverse_iterator(begin()); } iterator erase(iterator i) + { return erase(m2c(i)); } + iterator erase(const_iterator i) { Q_ASSERT_X(isValidIterator(i), "QSet::erase", "The specified const_iterator argument 'i' is invalid"); - return q_hash.erase(reinterpret_cast(i)); + return q_hash.erase(reinterpret_cast(i)); } // more Qt @@ -240,10 +243,18 @@ public: private: Hash q_hash; + + static const_iterator m2c(iterator it) Q_DECL_NOTHROW + { return const_iterator(typename Hash::const_iterator(it.i.i)); } + bool isValidIterator(const iterator &i) const { return q_hash.isValidIterator(reinterpret_cast(i)); } + bool isValidIterator(const const_iterator &i) const Q_DECL_NOTHROW + { + return q_hash.isValidIterator(reinterpret_cast(i)); + } }; template diff --git a/src/corelib/tools/qset.qdoc b/src/corelib/tools/qset.qdoc index 542def4651..df33f716e9 100644 --- a/src/corelib/tools/qset.qdoc +++ b/src/corelib/tools/qset.qdoc @@ -257,8 +257,8 @@ */ /*! - \fn QSet::iterator QSet::erase(iterator pos) - \since 4.2 + \fn QSet::iterator QSet::erase(const_iterator pos) + \since 5.7 Removes the item at the iterator position \a pos from the set, and returns an iterator positioned at the next item in the set. @@ -270,6 +270,12 @@ \sa remove(), find() */ +/*! + \fn QSet::iterator QSet::erase(iterator pos) + \since 4.2 + \overload +*/ + /*! \fn QSet::const_iterator QSet::find(const T &value) const \since 4.2 -- cgit v1.2.3