QLinkedList/QSet: add {const_,}reverse_iterator, {c,}r{begin,end}()

Now all Qt sequential containers consistently provide reverse iterators.

The associative ones, by way of not returning std::pair from op*, can't
just use std::reverse_iterator. They would miss .key() and .value() methods.
So that has to wait for 5.7.

The reverse versions of the new key_iterators can also just use
std::reverse_iterator, but I'm afraid that after bikeshedding over
keyRBegin() vs. rKeyBegin() vs. reverseKeyBegin() vs. rkbegin()
vs. krbegin() (<-- of course, what else?), it would anyway be too
late for 5.6, so defer, too.

[ChangeLog][QtCore][QLinkedList/QSet] Added rbegin(), crbegin(), rend(), crend(),
and reverse_iterator and const_reverse_iterator typedefs.

Task-number: QTBUG-25919
Change-Id: I58316fffade469e9a42c61d7aa1455ae3443fd94
Reviewed-by: Sérgio Martins <sergio.martins@kdab.com>
Reviewed-by: Olivier Goffart (Woboq GmbH) <ogoffart@woboq.com>

6 files changed, 224 insertions, 12 deletions

diff --git a/src/corelib/tools/qlinkedlist.cpp b/src/corelib/tools/qlinkedlist.cpp
index fbd263e88b..5d91bfe924 100644
--- a/src/corelib/tools/qlinkedlist.cpp
+++ b/src/corelib/tools/qlinkedlist.cpp
@@ -388,6 +388,52 @@ const QLinkedListData QLinkedListData::shared_null = {
     \sa constBegin(), end()
 */
 
+/*! \fn QLinkedList::reverse_iterator QLinkedList::rbegin()
+    \since 5.6
+
+    Returns a \l{STL-style iterators}{STL-style} reverse iterator pointing to the first
+    item in the list, in reverse order.
+
+    \sa begin(), crbegin(), rend()
+*/
+
+/*! \fn QLinkedList::const_reverse_iterator QLinkedList::rbegin() const
+    \since 5.6
+    \overload
+*/
+
+/*! \fn QLinkedList::const_reverse_iterator QLinkedList::crbegin() const
+    \since 5.6
+
+    Returns a const \l{STL-style iterators}{STL-style} reverse iterator pointing to the first
+    item in the list, in reverse order.
+
+    \sa begin(), rbegin(), rend()
+*/
+
+/*! \fn QLinkedList::reverse_iterator QLinkedList::rend()
+    \since 5.6
+
+    Returns a \l{STL-style iterators}{STL-style} reverse iterator pointing to one past
+    the last item in the list, in reverse order.
+
+    \sa end(), crend(), rbegin()
+*/
+
+/*! \fn QLinkedList::const_reverse_iterator QLinkedList::rend() const
+    \since 5.6
+    \overload
+*/
+
+/*! \fn QLinkedList::const_reverse_iterator QLinkedList::crend() const
+    \since 5.6
+
+    Returns a const \l{STL-style iterators}{STL-style} reverse iterator pointing to one
+    past the last item in the list, in reverse order.
+
+    \sa end(), rend(), rbegin()
+*/
+
 /*! \fn QLinkedList::iterator QLinkedList::insert(iterator before, const T &value)
 
     Inserts \a value in front of the item pointed to by the iterator
@@ -423,6 +469,38 @@ const QLinkedListData QLinkedListData::shared_null = {
     Qt-style synonym for QLinkedList::const_iterator.
 */
 
+/*! \typedef QLinkedList::reverse_iterator
+    \since 5.6
+
+    The QLinkedList::reverse_iterator typedef provides an STL-style non-const
+    reverse iterator for QLinkedList.
+
+    It is simply a typedef for \c{std::reverse_iterator<QLinkedList::iterator>}.
+
+    \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}.
+
+    \sa QLinkedList::rbegin(), QLinkedList::rend(), QLinkedList::const_reverse_iterator, QLinkedList::iterator
+*/
+
+/*! \typedef QLinkedList::const_reverse_iterator
+    \since 5.6
+
+    The QLinkedList::const_reverse_iterator typedef provides an STL-style const
+    reverse iterator for QLinkedList.
+
+    It is simply a typedef for \c{std::reverse_iterator<QLinkedList::const_iterator>}.
+
+    \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}.
+
+    \sa QLinkedList::rbegin(), QLinkedList::rend(), QLinkedList::reverse_iterator, QLinkedList::const_iterator
+*/
+
 /*!
     \typedef QLinkedList::size_type
 
diff --git a/src/corelib/tools/qlinkedlist.h b/src/corelib/tools/qlinkedlist.h
index 2854885d60..110529d843 100644
--- a/src/corelib/tools/qlinkedlist.h
+++ b/src/corelib/tools/qlinkedlist.h
@@ -183,14 +183,25 @@ public:
     friend class const_iterator;
 
     // stl style
+    typedef std::reverse_iterator<iterator> reverse_iterator;
+    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+
     inline iterator begin() { detach(); return e->n; }
-    inline const_iterator begin() const { return e->n; }
-    inline const_iterator cbegin() const { return e->n; }
-    inline const_iterator constBegin() const { return e->n; }
+    inline const_iterator begin() const Q_DECL_NOTHROW { return e->n; }
+    inline const_iterator cbegin() const Q_DECL_NOTHROW { return e->n; }
+    inline const_iterator constBegin() const Q_DECL_NOTHROW { return e->n; }
     inline iterator end() { detach(); return e; }
-    inline const_iterator end() const { return e; }
-    inline const_iterator cend() const { return e; }
-    inline const_iterator constEnd() const { return e; }
+    inline const_iterator end() const Q_DECL_NOTHROW { return e; }
+    inline const_iterator cend() const Q_DECL_NOTHROW { return e; }
+    inline const_iterator constEnd() const Q_DECL_NOTHROW { return e; }
+
+    reverse_iterator rbegin() { return reverse_iterator(end()); }
+    reverse_iterator rend() { return reverse_iterator(begin()); }
+    const_reverse_iterator rbegin() const Q_DECL_NOTHROW { return const_reverse_iterator(end()); }
+    const_reverse_iterator rend() const Q_DECL_NOTHROW { return const_reverse_iterator(begin()); }
+    const_reverse_iterator crbegin() const Q_DECL_NOTHROW { return const_reverse_iterator(end()); }
+    const_reverse_iterator crend() const Q_DECL_NOTHROW { return const_reverse_iterator(begin()); }
+
     iterator insert(iterator before, const T &t);
     iterator erase(iterator pos);
     iterator erase(iterator first, iterator last);
diff --git a/src/corelib/tools/qset.h b/src/corelib/tools/qset.h
index ed89617cd6..3f4208e8b3 100644
--- a/src/corelib/tools/qset.h
+++ b/src/corelib/tools/qset.h
@@ -39,6 +39,8 @@
 #include <initializer_list>
 #endif
 
+#include <iterator>
+
 QT_BEGIN_NAMESPACE
 
 
@@ -161,14 +163,25 @@ public:
     };
 
     // STL style
+    typedef std::reverse_iterator<iterator> reverse_iterator;
+    typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
+
     inline iterator begin() { return q_hash.begin(); }
-    inline const_iterator begin() const { return q_hash.begin(); }
-    inline const_iterator cbegin() const { return q_hash.begin(); }
-    inline const_iterator constBegin() const { return q_hash.constBegin(); }
+    inline const_iterator begin() const Q_DECL_NOTHROW { return q_hash.begin(); }
+    inline const_iterator cbegin() const Q_DECL_NOTHROW { return q_hash.begin(); }
+    inline const_iterator constBegin() const Q_DECL_NOTHROW { return q_hash.constBegin(); }
     inline iterator end() { return q_hash.end(); }
-    inline const_iterator end() const { return q_hash.end(); }
-    inline const_iterator cend() const { return q_hash.end(); }
-    inline const_iterator constEnd() const { return q_hash.constEnd(); }
+    inline const_iterator end() const Q_DECL_NOTHROW { return q_hash.end(); }
+    inline const_iterator cend() const Q_DECL_NOTHROW { return q_hash.end(); }
+    inline const_iterator constEnd() const Q_DECL_NOTHROW { return q_hash.constEnd(); }
+
+    reverse_iterator rbegin() { return reverse_iterator(end()); }
+    reverse_iterator rend() { return reverse_iterator(begin()); }
+    const_reverse_iterator rbegin() const Q_DECL_NOTHROW { return const_reverse_iterator(end()); }
+    const_reverse_iterator rend() const Q_DECL_NOTHROW { return const_reverse_iterator(begin()); }
+    const_reverse_iterator crbegin() const Q_DECL_NOTHROW { return const_reverse_iterator(end()); }
+    const_reverse_iterator crend() const Q_DECL_NOTHROW { return const_reverse_iterator(begin()); }
+
     iterator erase(iterator i)
     {
         Q_ASSERT_X(isValidIterator(i), "QSet::erase", "The specified const_iterator argument 'i' is invalid");
diff --git a/src/corelib/tools/qset.qdoc b/src/corelib/tools/qset.qdoc
index d91a589aa1..542def4651 100644
--- a/src/corelib/tools/qset.qdoc
+++ b/src/corelib/tools/qset.qdoc
@@ -384,6 +384,52 @@
     \sa constBegin(), end()
 */
 
+/*! \fn QSet::reverse_iterator QSet::rbegin()
+    \since 5.6
+
+    Returns a \l{STL-style iterators}{STL-style} reverse iterator pointing to the first
+    item in the set, in reverse order.
+
+    \sa begin(), crbegin(), rend()
+*/
+
+/*! \fn QSet::const_reverse_iterator QSet::rbegin() const
+    \since 5.6
+    \overload
+*/
+
+/*! \fn QSet::const_reverse_iterator QSet::crbegin() const
+    \since 5.6
+
+    Returns a const \l{STL-style iterators}{STL-style} reverse iterator pointing to the first
+    item in the set, in reverse order.
+
+    \sa begin(), rbegin(), rend()
+*/
+
+/*! \fn QSet::reverse_iterator QSet::rend()
+    \since 5.6
+
+    Returns a \l{STL-style iterators}{STL-style} reverse iterator pointing to one past
+    the last item in the set, in reverse order.
+
+    \sa end(), crend(), rbegin()
+*/
+
+/*! \fn QSet::const_reverse_iterator QSet::rend() const
+    \since 5.6
+    \overload
+*/
+
+/*! \fn QSet::const_reverse_iterator QSet::crend() const
+    \since 5.6
+
+    Returns a const \l{STL-style iterators}{STL-style} reverse iterator pointing to one
+    past the last item in the set, in reverse order.
+
+    \sa end(), rend(), rbegin()
+*/
+
 /*!
     \typedef QSet::Iterator
     \since 4.2
@@ -445,6 +491,38 @@
     Typedef for T. Provided for STL compatibility.
 */
 
+/*! \typedef QSet::reverse_iterator
+    \since 5.6
+
+    The QSet::reverse_iterator typedef provides an STL-style non-const
+    reverse iterator for QSet.
+
+    It is simply a typedef for \c{std::reverse_iterator<QSet::iterator>}.
+
+    \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}.
+
+    \sa QSet::rbegin(), QSet::rend(), QSet::const_reverse_iterator, QSet::iterator
+*/
+
+/*! \typedef QSet::const_reverse_iterator
+    \since 5.6
+
+    The QSet::const_reverse_iterator typedef provides an STL-style const
+    reverse iterator for QSet.
+
+    It is simply a typedef for \c{std::reverse_iterator<QSet::const_iterator>}.
+
+    \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}.
+
+    \sa QSet::rbegin(), QSet::rend(), QSet::reverse_iterator, QSet::const_iterator
+*/
+
 /*!
     \fn QSet::const_iterator QSet::insert(const T &value)
 
diff --git a/tests/auto/corelib/tools/qlinkedlist/tst_qlinkedlist.cpp b/tests/auto/corelib/tools/qlinkedlist/tst_qlinkedlist.cpp
index 2e829bb05e..d3ace40164 100644
--- a/tests/auto/corelib/tools/qlinkedlist/tst_qlinkedlist.cpp
+++ b/tests/auto/corelib/tools/qlinkedlist/tst_qlinkedlist.cpp
@@ -204,6 +204,7 @@ private slots:
     void removeOneInt() const;
     void removeOneMovable() const;
     void removeOneComplex() const;
+    void reverseIterators() const;
     void startsWithInt() const;
     void startsWithMovable() const;
     void startsWithComplex() const;
@@ -754,6 +755,21 @@ void tst_QLinkedList::removeOneComplex() const
     QCOMPARE(liveCount, Complex::getLiveCount());
 }
 
+void tst_QLinkedList::reverseIterators() const
+{
+    QLinkedList<int> l;
+    l << 1 << 2 << 3 << 4;
+    QLinkedList<int> lr = l;
+    std::reverse(lr.begin(), lr.end());
+    const QLinkedList<int> &clr = lr;
+    QVERIFY(std::equal(l.begin(), l.end(), lr.rbegin()));
+    QVERIFY(std::equal(l.begin(), l.end(), lr.crbegin()));
+    QVERIFY(std::equal(l.begin(), l.end(), clr.rbegin()));
+    QVERIFY(std::equal(lr.rbegin(), lr.rend(), l.begin()));
+    QVERIFY(std::equal(lr.crbegin(), lr.crend(), l.begin()));
+    QVERIFY(std::equal(clr.rbegin(), clr.rend(), l.begin()));
+}
+
 template<typename T>
 void tst_QLinkedList::startsWith() const
 {
diff --git a/tests/auto/corelib/tools/qset/tst_qset.cpp b/tests/auto/corelib/tools/qset/tst_qset.cpp
index 134d257d64..fe4d81085c 100644
--- a/tests/auto/corelib/tools/qset/tst_qset.cpp
+++ b/tests/auto/corelib/tools/qset/tst_qset.cpp
@@ -65,6 +65,7 @@ private slots:
     void begin();
     void end();
     void insert();
+    void reverseIterators();
     void setOperations();
     void stlIterator();
     void stlMutableIterator();
@@ -555,6 +556,21 @@ void tst_QSet::insert()
     }
 }
 
+void tst_QSet::reverseIterators()
+{
+    QSet<int> s;
+    s << 1 << 17 << 61 << 127 << 911;
+    std::vector<int> v(s.begin(), s.end());
+    std::reverse(v.begin(), v.end());
+    const QSet<int> &cs = s;
+    QVERIFY(std::equal(v.begin(), v.end(), s.rbegin()));
+    QVERIFY(std::equal(v.begin(), v.end(), s.crbegin()));
+    QVERIFY(std::equal(v.begin(), v.end(), cs.rbegin()));
+    QVERIFY(std::equal(s.rbegin(), s.rend(), v.begin()));
+    QVERIFY(std::equal(s.crbegin(), s.crend(), v.begin()));
+    QVERIFY(std::equal(cs.rbegin(), cs.rend(), v.begin()));
+}
+
 void tst_QSet::setOperations()
 {
     QSet<QString> set1, set2;