Non-associative containers: add range constructors

Something nice we'd like to detect for array-backed containers
is if the iterator passed is a Contiguous one; if the type is also
trivially copyable / Q_PRIMITIVE_TYPE, we could memcpy() the whole
range.

However, there's no trait in the Standard to detect contiguous
iterators (the best approximation would be detecting if the iterator
is actually a pointer). Also, it's probably not smart to do the work
now for QVector since QVector needs refactoring anyhow, and this work
will be lost.

QString and QByteArray are left in another commit.

[ChangeLog][QtCore][QVector] Added range constructor.

[ChangeLog][QtCore][QVarLengthArray] Added range constructor.

[ChangeLog][QtCore][QList] Added range constructor.

[ChangeLog][QtCore][QStringList] Added range constructor.

[ChangeLog][QtCore][QLinkedList] Added range constructor.

[ChangeLog][QtCore][QSet] Added range constructor.

Change-Id: I220edb796053c9c4d31a6dbdc7efc5fc0f6678f9
Reviewed-by: Milian Wolff <milian.wolff@kdab.com>

14 files changed, 201 insertions, 12 deletions

diff --git a/src/corelib/tools/qcontainertools_impl.h b/src/corelib/tools/qcontainertools_impl.h
new file mode 100644
index 0000000000..c2de50b145
--- /dev/null
+++ b/src/corelib/tools/qcontainertools_impl.h
@@ -0,0 +1,93 @@
+/****************************************************************************
+**
+** Copyright (C) 2018 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Marc Mutz <marc.mutz@kdab.com>
+** Copyright (C) 2018 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Giuseppe D'Angelo <giuseppe.dangelo@kdab.com>
+** Contact: https://www.qt.io/licensing/
+**
+** This file is part of the QtCore module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and The Qt Company. For licensing terms
+** and conditions see https://www.qt.io/terms-conditions. For further
+** information use the contact form at https://www.qt.io/contact-us.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 3 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL3 included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 3 requirements
+** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 2.0 or (at your option) the GNU General
+** Public license version 3 or any later version approved by the KDE Free
+** Qt Foundation. The licenses are as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
+** included in the packaging of this file. Please review the following
+** information to ensure the GNU General Public License requirements will
+** be met: https://www.gnu.org/licenses/gpl-2.0.html and
+** https://www.gnu.org/licenses/gpl-3.0.html.
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#if 0
+#pragma qt_sync_skip_header_check
+#pragma qt_sync_stop_processing
+#endif
+
+#ifndef QCONTAINERTOOLS_IMPL_H
+#define QCONTAINERTOOLS_IMPL_H
+
+#include <QtCore/qglobal.h>
+#include <iterator>
+
+#ifndef Q_QDOC
+
+QT_BEGIN_NAMESPACE
+
+namespace QtPrivate
+{
+template <typename Iterator>
+using IfIsInputIterator = typename std::enable_if<
+    std::is_convertible<typename std::iterator_traits<Iterator>::iterator_category, std::input_iterator_tag>::value,
+    bool>::type;
+
+template <typename Iterator>
+using IfIsForwardIterator = typename std::enable_if<
+    std::is_convertible<typename std::iterator_traits<Iterator>::iterator_category, std::forward_iterator_tag>::value,
+    bool>::type;
+
+template <typename Iterator>
+using IfIsNotForwardIterator = typename std::enable_if<
+    !std::is_convertible<typename std::iterator_traits<Iterator>::iterator_category, std::forward_iterator_tag>::value,
+    bool>::type;
+
+template <typename Container,
+          typename InputIterator,
+          IfIsNotForwardIterator<InputIterator> = true>
+void reserveIfForwardIterator(Container *, InputIterator, InputIterator)
+{
+}
+
+template <typename Container,
+          typename ForwardIterator,
+          IfIsForwardIterator<ForwardIterator> = true>
+void reserveIfForwardIterator(Container *c, ForwardIterator f, ForwardIterator l)
+{
+    c->reserve(static_cast<typename Container::size_type>(std::distance(f, l)));
+}
+} // namespace QtPrivate
+
+QT_END_NAMESPACE
+
+#endif // Q_QDOC
+
+#endif // QCONTAINERTOOLS_IMPL_H
diff --git a/src/corelib/tools/qlinkedlist.cpp b/src/corelib/tools/qlinkedlist.cpp
index d9d93862e5..c0450f5cd8 100644
--- a/src/corelib/tools/qlinkedlist.cpp
+++ b/src/corelib/tools/qlinkedlist.cpp
@@ -153,6 +153,14 @@ const QLinkedListData QLinkedListData::shared_null = {
     initializer lists.
 */
 
+/*! \fn template <class T> template<typename InputIterator> QLinkedList<T>::QLinkedList(InputIterator first, InputIterator last)
+    \since 5.14
+
+    Constructs a list with the contents in the iterator range [\a first, \a last).
+
+    The value type of \c InputIterator must be convertible to \c T.
+*/
+
 /*! \fn template <class T> QLinkedList<T>::~QLinkedList()
 
     Destroys the list. References to the values in the list, and all
diff --git a/src/corelib/tools/qlinkedlist.h b/src/corelib/tools/qlinkedlist.h
index 91367a74b3..83f70deceb 100644
--- a/src/corelib/tools/qlinkedlist.h
+++ b/src/corelib/tools/qlinkedlist.h
@@ -42,6 +42,7 @@
 
 #include <QtCore/qiterator.h>
 #include <QtCore/qrefcount.h>
+#include <QtCore/qcontainertools_impl.h>
 
 #include <iterator>
 #include <list>
@@ -84,11 +85,14 @@ public:
     inline QLinkedList(const QLinkedList<T> &l) : d(l.d) { d->ref.ref(); if (!d->sharable) detach(); }
 #if defined(Q_COMPILER_INITIALIZER_LISTS)
     inline QLinkedList(std::initializer_list<T> list)
-        : d(const_cast<QLinkedListData *>(&QLinkedListData::shared_null))
+        : QLinkedList(list.begin(), list.end()) {}
+#endif
+    template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator> = true>
+    inline QLinkedList(InputIterator first, InputIterator last)
+        : QLinkedList()
     {
-        std::copy(list.begin(), list.end(), std::back_inserter(*this));
+        std::copy(first, last, std::back_inserter(*this));
     }
-#endif
     ~QLinkedList();
     QLinkedList<T> &operator=(const QLinkedList<T> &);
 #ifdef Q_COMPILER_RVALUE_REFS
diff --git a/src/corelib/tools/qlist.cpp b/src/corelib/tools/qlist.cpp
index 6f8084c676..48617f0539 100644
--- a/src/corelib/tools/qlist.cpp
+++ b/src/corelib/tools/qlist.cpp
@@ -545,6 +545,14 @@ void **QListData::erase(void **xi)
     \since 5.2
 */
 
+/*! \fn template <class T> template<typename InputIterator> QList<T>::QList(InputIterator first, InputIterator last)
+    \since 5.14
+
+    Constructs a QList with the contents in the iterator range [\a first, \a last).
+
+    The value type of \c InputIterator must be convertible to \c T.
+*/
+
 /*!
     \fn template <class T> QList<T> QList<T>::mid(int pos, int length) const
 
diff --git a/src/corelib/tools/qlist.h b/src/corelib/tools/qlist.h
index 77d8df4a88..dfb8a8a4ab 100644
--- a/src/corelib/tools/qlist.h
+++ b/src/corelib/tools/qlist.h
@@ -46,6 +46,7 @@
 #include <QtCore/qarraydata.h>
 #include <QtCore/qhashfunctions.h>
 #include <QtCore/qvector.h>
+#include <QtCore/qcontainertools_impl.h>
 
 #include <iterator>
 #include <list>
@@ -169,9 +170,11 @@ public:
     inline void swap(QList<T> &other) noexcept { qSwap(d, other.d); }
 #ifdef Q_COMPILER_INITIALIZER_LISTS
     inline QList(std::initializer_list<T> args)
-        : d(const_cast<QListData::Data *>(&QListData::shared_null))
-    { reserve(int(args.size())); std::copy(args.begin(), args.end(), std::back_inserter(*this)); }
+        : QList(args.begin(), args.end()) {}
 #endif
+    template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator> = true>
+    QList(InputIterator first, InputIterator last);
+
     bool operator==(const QList<T> &l) const;
     inline bool operator!=(const QList<T> &l) const { return !(*this == l); }
 
@@ -843,6 +846,15 @@ Q_OUTOFLINE_TEMPLATE QList<T>::~QList()
 }
 
 template <typename T>
+template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator>>
+QList<T>::QList(InputIterator first, InputIterator last)
+    : QList()
+{
+    QtPrivate::reserveIfForwardIterator(this, first, last);
+    std::copy(first, last, std::back_inserter(*this));
+}
+
+template <typename T>
 Q_OUTOFLINE_TEMPLATE bool QList<T>::operator==(const QList<T> &l) const
 {
     if (d == l.d)
diff --git a/src/corelib/tools/qset.h b/src/corelib/tools/qset.h
index aa915f7ed1..7ae715d247 100644
--- a/src/corelib/tools/qset.h
+++ b/src/corelib/tools/qset.h
@@ -41,6 +41,8 @@
 #define QSET_H
 
 #include <QtCore/qhash.h>
+#include <QtCore/qcontainertools_impl.h>
+
 #ifdef Q_COMPILER_INITIALIZER_LISTS
 #include <initializer_list>
 #endif
@@ -59,12 +61,16 @@ public:
     inline QSet() noexcept {}
 #ifdef Q_COMPILER_INITIALIZER_LISTS
     inline QSet(std::initializer_list<T> list)
+        : QSet(list.begin(), list.end()) {}
+#endif
+    template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator> = true>
+    inline QSet(InputIterator first, InputIterator last)
     {
-        reserve(int(list.size()));
-        for (typename std::initializer_list<T>::const_iterator it = list.begin(); it != list.end(); ++it)
-            insert(*it);
+        QtPrivate::reserveIfForwardIterator(this, first, last);
+        for (; first != last; ++first)
+            insert(*first);
     }
-#endif
+
     // compiler-generated copy/move ctor/assignment operators are fine!
     // compiler-generated destructor is fine!
 
diff --git a/src/corelib/tools/qset.qdoc b/src/corelib/tools/qset.qdoc
index 48863f2399..2e7a5a29ce 100644
--- a/src/corelib/tools/qset.qdoc
+++ b/src/corelib/tools/qset.qdoc
@@ -113,6 +113,17 @@
     compiled in C++11 mode.
 */
 
+/*! \fn template <class T> template<typename InputIterator> QSet<T>::QSet(InputIterator first, InputIterator last)
+    \since 5.14
+
+    Constructs a set with the contents in the iterator range [\a first, \a last).
+
+    The value type of \c InputIterator must be convertible to \c T.
+
+    \note If the range [\a first, \a last) contains duplicate elements,
+    the first one is retained.
+*/
+
 /*!
     \fn template <class T> void QSet<T>::swap(QSet<T> &other)
 
diff --git a/src/corelib/tools/qstringlist.cpp b/src/corelib/tools/qstringlist.cpp
index cc6eaf8ad2..49247d66b8 100644
--- a/src/corelib/tools/qstringlist.cpp
+++ b/src/corelib/tools/qstringlist.cpp
@@ -847,5 +847,12 @@ int QtPrivate::QStringList_removeDuplicates(QStringList *that)
     lists.
 */
 
+ /*! \fn template<typename InputIterator> QStringList::QStringList(InputIterator first, InputIterator last)
+     \since 5.14
+
+     Constructs a QStringList with the contents in the iterator range [\a first, \a last).
+
+     The value type of \c InputIterator must be convertible to \c QString.
+ */
 
 QT_END_NAMESPACE
diff --git a/src/corelib/tools/qstringlist.h b/src/corelib/tools/qstringlist.h
index 6387161269..5ad01a0658 100644
--- a/src/corelib/tools/qstringlist.h
+++ b/src/corelib/tools/qstringlist.h
@@ -44,6 +44,7 @@
 #define QSTRINGLIST_H
 
 #include <QtCore/qalgorithms.h>
+#include <QtCore/qcontainertools_impl.h>
 #include <QtCore/qregexp.h>
 #include <QtCore/qstring.h>
 #include <QtCore/qstringmatcher.h>
@@ -109,6 +110,9 @@ public:
 #ifdef Q_COMPILER_INITIALIZER_LISTS
     inline QStringList(std::initializer_list<QString> args) : QList<QString>(args) { }
 #endif
+    template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator> = true>
+    inline QStringList(InputIterator first, InputIterator last)
+        : QList<QString>(first, last) { }
 
     QStringList &operator=(const QList<QString> &other)
     { QList<QString>::operator=(other); return *this; }
diff --git a/src/corelib/tools/qvarlengtharray.h b/src/corelib/tools/qvarlengtharray.h
index c03fbb2218..c81af68593 100644
--- a/src/corelib/tools/qvarlengtharray.h
+++ b/src/corelib/tools/qvarlengtharray.h
@@ -43,6 +43,7 @@
 #include <QtCore/qcontainerfwd.h>
 #include <QtCore/qglobal.h>
 #include <QtCore/qalgorithms.h>
+#include <QtCore/qcontainertools_impl.h>
 
 #include <new>
 #include <string.h>
@@ -71,13 +72,19 @@ public:
 
 #ifdef Q_COMPILER_INITIALIZER_LISTS
     QVarLengthArray(std::initializer_list<T> args)
-        : a(Prealloc), s(0), ptr(reinterpret_cast<T *>(array))
+        : QVarLengthArray(args.begin(), args.end())
     {
-        if (args.size())
-            append(args.begin(), int(args.size()));
     }
 #endif
 
+    template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator> = true>
+    inline QVarLengthArray(InputIterator first, InputIterator last)
+        : QVarLengthArray()
+    {
+        QtPrivate::reserveIfForwardIterator(this, first, last);
+        std::copy(first, last, std::back_inserter(*this));
+    }
+
     inline ~QVarLengthArray() {
         if (QTypeInfo<T>::isComplex) {
             T *i = ptr + s;
diff --git a/src/corelib/tools/qvarlengtharray.qdoc b/src/corelib/tools/qvarlengtharray.qdoc
index bc8df82517..80769e3769 100644
--- a/src/corelib/tools/qvarlengtharray.qdoc
+++ b/src/corelib/tools/qvarlengtharray.qdoc
@@ -110,6 +110,14 @@
     lists.
 */
 
+/*! \fn template<class T, int Prealloc> template<typename InputIterator> QVarLengthArray<T, Prealloc>::QVarLengthArray(InputIterator first, InputIterator last)
+    \since 5.14
+
+    Constructs an array with the contents in the iterator range [\a first, \a last).
+
+    The value type of \c InputIterator must be convertible to \c T.
+*/
+
 
 /*! \fn template<class T, int Prealloc> QVarLengthArray<T, Prealloc>::~QVarLengthArray()
 
diff --git a/src/corelib/tools/qvector.h b/src/corelib/tools/qvector.h
index 096c369e51..6cbf794c6c 100644
--- a/src/corelib/tools/qvector.h
+++ b/src/corelib/tools/qvector.h
@@ -45,6 +45,7 @@
 #include <QtCore/qrefcount.h>
 #include <QtCore/qarraydata.h>
 #include <QtCore/qhashfunctions.h>
+#include <QtCore/qcontainertools_impl.h>
 
 #include <iterator>
 #include <vector>
@@ -81,6 +82,9 @@ public:
     inline QVector(std::initializer_list<T> args);
     QVector<T> &operator=(std::initializer_list<T> args);
 #endif
+    template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator> = true>
+    inline QVector(InputIterator first, InputIterator last);
+
     bool operator==(const QVector<T> &v) const;
     inline bool operator!=(const QVector<T> &v) const { return !(*this == v); }
 
@@ -558,6 +562,15 @@ QT_WARNING_POP
 #endif // Q_COMPILER_INITIALIZER_LISTS
 
 template <typename T>
+template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator>>
+QVector<T>::QVector(InputIterator first, InputIterator last)
+    : QVector()
+{
+    QtPrivate::reserveIfForwardIterator(this, first, last);
+    std::copy(first, last, std::back_inserter(*this));
+}
+
+template <typename T>
 void QVector<T>::freeData(Data *x)
 {
     destruct(x->begin(), x->end());
diff --git a/src/corelib/tools/qvector.qdoc b/src/corelib/tools/qvector.qdoc
index 69bbb5f9a2..cb47d36356 100644
--- a/src/corelib/tools/qvector.qdoc
+++ b/src/corelib/tools/qvector.qdoc
@@ -243,6 +243,13 @@
     lists.
 */
 
+/*! \fn template <typename T> template<typename InputIterator> QVector<T>::QVector(InputIterator first, InputIterator last)
+    \since 5.14
+
+    Constructs a vector with the contents in the iterator range [\a first, \a last).
+
+    The value type of \c InputIterator must be convertible to \c T.
+*/
 
 /*! \fn template <typename T> QVector<T>::~QVector()
 
diff --git a/src/corelib/tools/tools.pri b/src/corelib/tools/tools.pri
index 995bab694e..5dcb6c9ee0 100644
--- a/src/corelib/tools/tools.pri
+++ b/src/corelib/tools/tools.pri
@@ -18,6 +18,7 @@ HEADERS +=  \
         tools/qcollator.h \
         tools/qcollator_p.h \
         tools/qcontainerfwd.h \
+        tools/qcontainertools_impl.h \
         tools/qcryptographichash.h \
         tools/qdatetime.h \
         tools/qdatetime_p.h \