Add rvalue overload of insert/prepend to QVarLengthArray and QVector

Improves performance and STL compatibility by adding rvalue versions
of prepend and insert.

[ChangeLog][QtCore][QVarLengthArray] Added rvalue overloads of
prepend and insert.

[ChangeLog][QtCore][QVector] Added rvalue overloads of prepend
and insert.

[ChangeLog][QtCore][QVarLengthArray] Can now contain movable but
non-copyable types, such as std::unique_ptr.

Change-Id: I6c946acc5b67502c91c52ac5dea67cedb1af93a5
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>

2 files changed, 105 insertions, 11 deletions

diff --git a/src/corelib/tools/qvarlengtharray.h b/src/corelib/tools/qvarlengtharray.h
index 90311ac55b..b2f05452ae 100644
--- a/src/corelib/tools/qvarlengtharray.h
+++ b/src/corelib/tools/qvarlengtharray.h
@@ -178,7 +178,9 @@ public:
     inline QVarLengthArray<T, Prealloc> &operator+=(const T &t)
     { append(t); return *this; }
 
+    void prepend(T &&t);
     void prepend(const T &t);
+    void insert(int i, T &&t);
     void insert(int i, const T &t);
     void insert(int i, int n, const T &t);
     void replace(int i, const T &t);
@@ -218,6 +220,7 @@ public:
     const_reverse_iterator crbegin() const { return const_reverse_iterator(end()); }
     const_reverse_iterator crend() const { return const_reverse_iterator(begin()); }
     iterator insert(const_iterator before, int n, const T &x);
+    iterator insert(const_iterator before, T &&x);
     inline iterator insert(const_iterator before, const T &x) { return insert(before, 1, x); }
     iterator erase(const_iterator begin, const_iterator end);
     inline iterator erase(const_iterator pos) { return erase(pos, pos+1); }
@@ -373,9 +376,9 @@ Q_OUTOFLINE_TEMPLATE void QVarLengthArray<T, Prealloc>::realloc(int asize, int a
         s = 0;
         if (!QTypeInfoQuery<T>::isRelocatable) {
             QT_TRY {
-                // copy all the old elements
+                // move all the old elements
                 while (s < copySize) {
-                    new (ptr+s) T(*(oldPtr+s));
+                    new (ptr+s) T(std::move(*(oldPtr+s)));
                     (oldPtr+s)->~T();
                     s++;
                 }
@@ -427,6 +430,10 @@ Q_OUTOFLINE_TEMPLATE T QVarLengthArray<T, Prealloc>::value(int i, const T &defau
 }
 
 template <class T, int Prealloc>
+inline void QVarLengthArray<T, Prealloc>::insert(int i, T &&t)
+{ Q_ASSERT_X(i >= 0 && i <= s, "QVarLengthArray::insert", "index out of range");
+  insert(cbegin() + i, std::move(t)); }
+template <class T, int Prealloc>
 inline void QVarLengthArray<T, Prealloc>::insert(int i, const T &t)
 { Q_ASSERT_X(i >= 0 && i <= s, "QVarLengthArray::insert", "index out of range");
   insert(begin() + i, 1, t); }
@@ -443,6 +450,9 @@ inline void QVarLengthArray<T, Prealloc>::remove(int i)
 { Q_ASSERT_X(i >= 0 && i < s, "QVarLengthArray::remove", "index out of range");
   erase(begin() + i, begin() + i + 1); }
 template <class T, int Prealloc>
+inline void QVarLengthArray<T, Prealloc>::prepend(T &&t)
+{ insert(cbegin(), std::move(t)); }
+template <class T, int Prealloc>
 inline void QVarLengthArray<T, Prealloc>::prepend(const T &t)
 { insert(begin(), 1, t); }
 
@@ -454,6 +464,34 @@ inline void QVarLengthArray<T, Prealloc>::replace(int i, const T &t)
     data()[i] = copy;
 }
 
+template <class T, int Prealloc>
+Q_OUTOFLINE_TEMPLATE typename QVarLengthArray<T, Prealloc>::iterator QVarLengthArray<T, Prealloc>::insert(const_iterator before, T &&t)
+{
+    Q_ASSERT_X(isValidIterator(before), "QVarLengthArray::insert", "The specified const_iterator argument 'before' is invalid");
+
+    int offset = int(before - ptr);
+    reserve(s + 1);
+    if (!QTypeInfo<T>::isRelocatable) {
+        T *b = ptr + offset;
+        T *i = ptr + s;
+        T *j = i + 1;
+        // The new end-element needs to be constructed, the rest must be move assigned
+        if (i != b) {
+            new (--j) T(std::move(*--i));
+            while (i != b)
+                *--j = std::move(*--i);
+            *b = std::move(t);
+        } else {
+            new (b) T(std::move(t));
+        }
+    } else {
+        T *b = ptr + offset;
+        memmove(b + 1, b, (s - offset) * sizeof(T));
+        new (b) T(std::move(t));
+    }
+    s += 1;
+    return ptr + offset;
+}
 
 template <class T, int Prealloc>
 Q_OUTOFLINE_TEMPLATE typename QVarLengthArray<T, Prealloc>::iterator QVarLengthArray<T, Prealloc>::insert(const_iterator before, size_type n, const T &t)
diff --git a/src/corelib/tools/qvector.h b/src/corelib/tools/qvector.h
index ce6e657be0..5ebf7f7435 100644
--- a/src/corelib/tools/qvector.h
+++ b/src/corelib/tools/qvector.h
@@ -137,7 +137,9 @@ public:
     void append(T &&t);
 #endif
     inline void append(const QVector<T> &l) { *this += l; }
+    void prepend(T &&t);
     void prepend(const T &t);
+    void insert(int i, T &&t);
     void insert(int i, const T &t);
     void insert(int i, int n, const T &t);
     void replace(int i, const T &t);
@@ -226,6 +228,7 @@ public:
     const_reverse_iterator crend() const Q_DECL_NOTHROW { return const_reverse_iterator(begin()); }
     iterator insert(iterator before, int n, const T &x);
     inline iterator insert(iterator before, const T &x) { return insert(before, 1, x); }
+    inline iterator insert(iterator before, T &&x);
     iterator erase(iterator begin, iterator end);
     inline iterator erase(iterator pos) { return erase(pos, pos+1); }
 
@@ -257,6 +260,7 @@ public:
     inline void push_back(const T &t) { append(t); }
 #ifdef Q_COMPILER_RVALUE_REFS
     void push_back(T &&t) { append(std::move(t)); }
+    void push_front(T &&t) { prepend(std::move(t)); }
 #endif
     inline void push_front(const T &t) { prepend(t); }
     void pop_back() { removeLast(); }
@@ -436,6 +440,10 @@ inline void QVector<T>::insert(int i, int n, const T &t)
 { Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert", "index out of range");
   insert(begin() + i, n, t); }
 template <typename T>
+inline void QVector<T>::insert(int i, T &&t)
+{ Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert", "index out of range");
+  insert(begin() + i, std::move(t)); }
+template <typename T>
 inline void QVector<T>::remove(int i, int n)
 { Q_ASSERT_X(i >= 0 && n >= 0 && i + n <= d->size, "QVector<T>::remove", "index out of range");
   erase(d->begin() + i, d->begin() + i + n); }
@@ -446,6 +454,9 @@ inline void QVector<T>::remove(int i)
 template <typename T>
 inline void QVector<T>::prepend(const T &t)
 { insert(begin(), 1, t); }
+template <typename T>
+inline void QVector<T>::prepend(T &&t)
+{ insert(begin(), std::move(t)); }
 
 template <typename T>
 inline void QVector<T>::replace(int i, const T &t)
@@ -558,9 +569,19 @@ void QVector<T>::reallocData(const int asize, const int aalloc, QArrayData::Allo
                 T *dst = x->begin();
 
                 if (!QTypeInfoQuery<T>::isRelocatable || (isShared && QTypeInfo<T>::isComplex)) {
-                    // we can not move the data, we need to copy construct it
-                    while (srcBegin != srcEnd) {
-                        new (dst++) T(*srcBegin++);
+                    QT_TRY {
+                        if (isShared || !std::is_nothrow_move_constructible<T>::value) {
+                            // we can not move the data, we need to copy construct it
+                            while (srcBegin != srcEnd)
+                                new (dst++) T(*srcBegin++);
+                        } else {
+                            while (srcBegin != srcEnd)
+                                new (dst++) T(std::move(*srcBegin++));
+                        }
+                    } QT_CATCH (...) {
+                        // destruct already copied objects
+                        destruct(x->begin(), dst);
+                        QT_RETHROW;
                     }
                 } else {
                     ::memcpy(static_cast<void *>(dst), static_cast<void *>(srcBegin), (srcEnd - srcBegin) * sizeof(T));
@@ -573,12 +594,17 @@ void QVector<T>::reallocData(const int asize, const int aalloc, QArrayData::Allo
 
                 if (asize > d->size) {
                     // construct all new objects when growing
-                    QT_TRY {
-                        defaultConstruct(dst, x->end());
-                    } QT_CATCH (...) {
-                        // destruct already copied objects
-                        destruct(x->begin(), dst);
-                        QT_RETHROW;
+                    if (!QTypeInfo<T>::isComplex) {
+                        ::memset(static_cast<void *>(dst), 0, (static_cast<T *>(x->end()) - dst) * sizeof(T));
+                    } else {
+                        QT_TRY {
+                            while (dst != x->end())
+                                new (dst++) T();
+                        } QT_CATCH (...) {
+                            // destruct already copied objects
+                            destruct(x->begin(), dst);
+                            QT_RETHROW;
+                        }
                     }
                 }
             } QT_CATCH (...) {
@@ -731,6 +757,36 @@ typename QVector<T>::iterator QVector<T>::insert(iterator before, size_type n, c
 }
 
 template <typename T>
+typename QVector<T>::iterator QVector<T>::insert(iterator before, T &&t)
+{
+    Q_ASSERT_X(isValidIterator(before),  "QVector::insert", "The specified iterator argument 'before' is invalid");
+
+    const auto offset = std::distance(d->begin(), before);
+    if (!isDetached() || d->size + 1 > int(d->alloc))
+        reallocData(d->size, d->size + 1, QArrayData::Grow);
+    if (!QTypeInfoQuery<T>::isRelocatable) {
+        T *i = d->end();
+        T *j = i + 1;
+        T *b = d->begin() + offset;
+        // The new end-element needs to be constructed, the rest must be move assigned
+        if (i != b) {
+            new (--j) T(std::move(*--i));
+            while (i != b)
+                *--j = std::move(*--i);
+            *b = std::move(t);
+        } else {
+            new (b) T(std::move(t));
+        }
+    } else {
+        T *b = d->begin() + offset;
+        memmove(b + 1, b, (d->size - offset) * sizeof(T));
+        new (b) T(std::move(t));
+    }
+    d->size += 1;
+    return d->begin() + offset;
+}
+
+template <typename T>
 typename QVector<T>::iterator QVector<T>::erase(iterator abegin, iterator aend)
 {
     Q_ASSERT_X(isValidIterator(abegin), "QVector::erase", "The specified iterator argument 'abegin' is invalid");