Implement key-value iterator

This patch implements an iterator that returns a pair containing both the
key and the value of an entry in QHash/QMap.

[ChangeLog][QtCore][Containers] Added an stl-like iterator to go through
QHash/QMap returning both the key and the value of the element pointed to.
That lets QHash/QMap interoperate better with stl's algorithms like
std::set_union.

Change-Id: Idbf8a8581510b3493648c34ab04c556de9fa4aa7
Reviewed-by: Edward Welbourne <edward.welbourne@qt.io>

5 files changed, 301 insertions, 0 deletions

diff --git a/src/corelib/tools/qhash.cpp b/src/corelib/tools/qhash.cpp
index 09f3fd8e83..353dc834aa 100644
--- a/src/corelib/tools/qhash.cpp
+++ b/src/corelib/tools/qhash.cpp
@@ -1722,6 +1722,60 @@ uint qHash(long double key, uint seed) Q_DECL_NOTHROW
     \sa keyBegin()
 */
 
+/*! \fn QHash::key_value_iterator QHash::keyValueBegin()
+    \since 5.10
+
+    Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first entry
+    in the hash.
+
+    \sa keyValueEnd()
+*/
+
+/*! \fn QHash::key_value_iterator QHash::keyValueEnd()
+    \since 5.10
+
+    Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
+    entry after the last entry in the hash.
+
+    \sa keyValueBegin()
+*/
+
+/*! \fn QHash::const_key_value_iterator QHash::keyValueBegin() const
+    \since 5.10
+
+    Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
+    in the hash.
+
+    \sa keyValueEnd()
+*/
+
+/*! \fn QHash::const_key_value_iterator QHash::constKeyValueBegin() const
+    \since 5.10
+
+    Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
+    in the hash.
+
+    \sa keyValueBegin()
+*/
+
+/*! \fn QHash::const_key_value_iterator QHash::keyValueEnd() const
+    \since 5.10
+
+    Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
+    entry after the last entry in the hash.
+
+    \sa keyValueBegin()
+*/
+
+/*! \fn QHash::const_key_value_iterator QHash::constKeyValueEnd() const
+    \since 5.10
+
+    Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
+    entry after the last entry in the hash.
+
+    \sa constKeyValueBegin()
+*/
+
 /*! \fn QHash::iterator QHash::erase(const_iterator pos)
     \since 5.7
 
@@ -2457,6 +2511,18 @@ uint qHash(long double key, uint seed) Q_DECL_NOTHROW
     Returns the underlying const_iterator this key_iterator is based on.
 */
 
+/*! \typedef QHash::key_value_iterator
+    \inmodule QtCore
+    \since 5.10
+    \brief The QMap::key_value_iterator typedef provides an STL-style iterator for QHash and QMultiHash.
+
+    QHash::key_value_iterator is essentially the same as QHash::iterator
+    with the difference that operator*() returns a key/value pair instead of a
+    value.
+
+    \sa QKeyValueIterator
+*/
+
 /*! \fn QDataStream &operator<<(QDataStream &out, const QHash<Key, T>& hash)
     \relates QHash
 
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h
index c59f789cb2..bcaaec0ec6 100644
--- a/src/corelib/tools/qhash.h
+++ b/src/corelib/tools/qhash.h
@@ -447,6 +447,9 @@ public:
         const_iterator base() const { return i; }
     };
 
+    typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator;
+    typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator;
+
     // STL style
     inline iterator begin() { detach(); return iterator(d->firstNode()); }
     inline const_iterator begin() const { return const_iterator(d->firstNode()); }
@@ -458,6 +461,12 @@ public:
     inline const_iterator constEnd() const { return const_iterator(e); }
     inline key_iterator keyBegin() const { return key_iterator(begin()); }
     inline key_iterator keyEnd() const { return key_iterator(end()); }
+    inline key_value_iterator keyValueBegin() { return key_value_iterator(begin()); }
+    inline key_value_iterator keyValueEnd() { return key_value_iterator(end()); }
+    inline const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); }
+    inline const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); }
+    inline const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); }
+    inline const_key_value_iterator constKeyValueEnd() const { return const_key_value_iterator(end()); }
 
     QPair<iterator, iterator> equal_range(const Key &key);
     QPair<const_iterator, const_iterator> equal_range(const Key &key) const Q_DECL_NOTHROW;
diff --git a/src/corelib/tools/qiterator.h b/src/corelib/tools/qiterator.h
index 3953005242..9550c302bb 100644
--- a/src/corelib/tools/qiterator.h
+++ b/src/corelib/tools/qiterator.h
@@ -179,6 +179,157 @@ public: \
       n = c->end(); return false; } \
 };
 
+template<typename Key, typename T, class Iterator>
+class QKeyValueIterator
+{
+public:
+    typedef typename Iterator::iterator_category iterator_category;
+    typedef typename Iterator::difference_type difference_type;
+    typedef std::pair<Key, T> value_type;
+    typedef const value_type *pointer;
+    typedef const value_type &reference;
+
+    QKeyValueIterator() = default;
+    Q_DECL_CONSTEXPR explicit QKeyValueIterator(Iterator o) Q_DECL_NOEXCEPT_EXPR(std::is_nothrow_move_constructible<Iterator>::value)
+        : i(std::move(o)) {}
+
+    std::pair<Key, T> operator*() const {
+        return std::pair<Key, T>(i.key(), i.value());
+    }
+
+    friend Q_DECL_CONSTEXPR bool operator==(QKeyValueIterator lhs, QKeyValueIterator rhs) Q_DECL_NOEXCEPT { return lhs.i == rhs.i; }
+    friend Q_DECL_CONSTEXPR bool operator!=(QKeyValueIterator lhs, QKeyValueIterator rhs) Q_DECL_NOEXCEPT { return lhs.i != rhs.i; }
+
+    inline QKeyValueIterator &operator++() { ++i; return *this; }
+    inline QKeyValueIterator operator++(int) { return QKeyValueIterator(i++);}
+    inline QKeyValueIterator &operator--() { --i; return *this; }
+    inline QKeyValueIterator operator--(int) { return QKeyValueIterator(i--); }
+    Iterator base() const { return i; }
+
+private:
+    Iterator i;
+};
+
+/*! \class QKeyValueIterator
+    \inmodule QtCore
+    \since 5.10
+
+    \brief Iterator over the key/value pairs of an associative container.
+
+    The QKeyValueIterator class provides an STL-style iterator for returning
+    key/value pairs from associative containers like QHash and QMap. It
+    supports the same API as the STL associative containers, i.e. getting a
+    key/value pair when iterating through the container.
+
+    This will allow for better interoperability between QMap, QHash and friends
+    and STL-style algorithms.
+
+    \warning Iterators on implicitly shared containers do not work
+    exactly like STL-iterators. You should avoid copying a container
+    while iterators are active on that container. For more information,
+    read \l{Implicit sharing iterator problem}.
+*/
+
+/*! \typedef QKeyValueIterator::iterator_category
+    \internal
+*/
+
+/*! \typedef QKeyValueIterator::difference_type
+    \internal
+*/
+
+/*! \typedef QKeyValueIterator::value_type
+    \internal
+*/
+
+/*! \typedef QKeyValueIterator::pointer
+    \internal
+*/
+
+/*! \typedef QKeyValueIterator::reference
+    \internal
+*/
+
+/*! \fn QKeyValueIterator()
+
+    Constructs a default QKeyValueIterator.
+*/
+
+/*! \fn QKeyValueIterator(Iterator o)
+
+    Constructs a QKeyValueIterator on top of \a o.
+*/
+
+/*! \fn const T &QKeyValueIterator::operator*() const
+
+    Returns the current entry as a pair.
+*/
+
+/*! \fn bool QKeyValueIterator::operator==(QKeyValueIterator lhs, QKeyValueIterator rhs)
+
+    Returns \c true if \a rhs points to the same item as \a lhs otherwise returns
+    \c false.
+
+    \sa operator!=()
+*/
+
+/*! \fn bool QKeyValueIterator::operator!=(QKeyValueIterator lhs, QKeyValueIterator rhs) const
+
+    Returns \c true if \a rhs points to a different item than \a lhs otherwise
+    returns \c false.
+
+    \sa operator==()
+*/
+
+/*!
+    \fn QKeyValueIterator &QKeyValueIterator::operator++()
+
+    The prefix ++ operator (\c{++i}) advances the iterator to the
+    next item in the container and returns the iterator.
+
+    \note Advancing the iterator past its container's end() constitutes
+    undefined behavior.
+
+    \sa operator--()
+*/
+
+/*! \fn QKeyValueIterator QKeyValueIterator::operator++(int)
+
+    \overload
+
+    The postfix ++ operator (\c{i++}) advances the iterator to the
+    next item in the container and returns the iterator's prior value.
+
+    \note Advancing the iterator past its container's end() constitutes
+    undefined behavior.
+*/
+
+/*! \fn QKeyValueIterator &QKeyValueIterator::operator--()
+
+    The prefix -- operator (\c{--i}) backs the iterator up to the previous item
+    in the container and returns the iterator.
+
+    \note Backing up an iterator to before its container's begin() constitutes
+    undefined behavior.
+
+    \sa operator++()
+*/
+
+/*! \fn QKeyValueIterator QKeyValueIterator::operator--(int)
+
+    \overload
+
+    The postfix -- operator (\c{i--}) backs the iterator up to the previous item
+    in the container and returns the iterator's prior value.
+
+    \note Backing up an iterator to before its container's begin() constitutes
+    undefined behavior.
+*/
+
+/*! \fn Iterator QKeyValueIterator::base() const
+    Returns the underlying iterator this QKeyValueIterator is based on.
+*/
+
 QT_END_NAMESPACE
 
 #endif // QITERATOR_H
diff --git a/src/corelib/tools/qmap.cpp b/src/corelib/tools/qmap.cpp
index 94ed47f898..9738e2ed18 100644
--- a/src/corelib/tools/qmap.cpp
+++ b/src/corelib/tools/qmap.cpp
@@ -908,6 +908,61 @@ void QMapDataBase::freeData(QMapDataBase *d)
     \sa keyBegin(), lastKey()
 */
 
+
+/*! \fn QMap::key_value_iterator QMap::keyValueBegin()
+    \since 5.10
+
+    Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first entry
+    in the map.
+
+    \sa keyValueEnd()
+*/
+
+/*! \fn QMap::key_value_iterator QMap::keyValueEnd()
+    \since 5.10
+
+    Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
+    entry after the last entry in the map.
+
+    \sa keyValueBegin()
+*/
+
+/*! \fn QMap::const_key_value_iterator QMap::keyValueBegin() const
+    \since 5.10
+
+    Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
+    in the map.
+
+    \sa keyValueEnd()
+*/
+
+/*! \fn QMap::const_key_value_iterator QMap::constKeyValueBegin() const
+    \since 5.10
+
+    Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first entry
+    in the map.
+
+    \sa keyValueBegin()
+*/
+
+/*! \fn QMap::const_key_value_iterator QMap::keyValueEnd() const
+    \since 5.10
+
+    Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
+    entry after the last entry in the map.
+
+    \sa keyValueBegin()
+*/
+
+/*! \fn QMap::const_key_value_iterator QMap::constKeyValueEnd() const
+    \since 5.10
+
+    Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
+    entry after the last entry in the map.
+
+    \sa constKeyValueBegin()
+*/
+
 /*! \fn const Key &QMap::firstKey() const
     \since 5.2
 
@@ -1782,6 +1837,18 @@ void QMapDataBase::freeData(QMapDataBase *d)
     Returns the underlying const_iterator this key_iterator is based on.
 */
 
+/*! \typedef QMap::key_value_iterator
+    \inmodule QtCore
+    \since 5.10
+    \brief The QMap::key_value_iterator typedef provides an STL-style iterator for QMap and QMultiMap.
+
+    QMap::key_value_iterator is essentially the same as QMap::iterator
+    with the difference that operator*() returns a key/value pair instead of a
+    value.
+
+    \sa QKeyValueIterator
+*/
+
 /*! \fn QDataStream &operator<<(QDataStream &out, const QMap<Key, T> &map)
     \relates QMap
 
diff --git a/src/corelib/tools/qmap.h b/src/corelib/tools/qmap.h
index a3b11eddcf..2c19ae969f 100644
--- a/src/corelib/tools/qmap.h
+++ b/src/corelib/tools/qmap.h
@@ -548,6 +548,8 @@ public:
         const_iterator base() const { return i; }
     };
 
+    typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator;
+    typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator;
 
     // STL style
     inline iterator begin() { detach(); return iterator(d->begin()); }
@@ -560,6 +562,12 @@ public:
     inline const_iterator cend() const { return const_iterator(d->end()); }
     inline key_iterator keyBegin() const { return key_iterator(begin()); }
     inline key_iterator keyEnd() const { return key_iterator(end()); }
+    inline key_value_iterator keyValueBegin() { return key_value_iterator(begin()); }
+    inline key_value_iterator keyValueEnd() { return key_value_iterator(end()); }
+    inline const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); }
+    inline const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); }
+    inline const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); }
+    inline const_key_value_iterator constKeyValueEnd() const { return const_key_value_iterator(end()); }
     iterator erase(iterator it);
 
     // more Qt