QVector: implement methods for adding new elements constructed in place

Fixes: QTBUG-80293
Change-Id: I687dc05a9ad2bad7bab3dc2b1173edf75550d57e
Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org>
Reviewed-by: Lars Knoll <lars.knoll@qt.io>

5 files changed, 328 insertions, 51 deletions

diff --git a/src/corelib/doc/snippets/code/src_corelib_tools_qvector.cpp b/src/corelib/doc/snippets/code/src_corelib_tools_qvector.cpp
index a05233049f..76a8d68f64 100644
--- a/src/corelib/doc/snippets/code/src_corelib_tools_qvector.cpp
+++ b/src/corelib/doc/snippets/code/src_corelib_tools_qvector.cpp
@@ -115,6 +115,29 @@ vector.append(std::move(three));
 //! [move-append]
 
 
+//! [emplace]
+QVector<QString> vector{"a", "ccc"};
+vector.emplace(1, 2, 'b');
+// vector: ["a", "bb", "ccc"]
+//! [emplace]
+
+
+//! [emplace-back]
+QVector<QString> vector{"one", "two"};
+vector.emplaceBack(3, 'a');
+qDebug() << vector;
+// vector: ["one", "two", "aaa"]
+//! [emplace-back]
+
+
+//! [emplace-back-ref]
+QVector<QString> vector;
+auto &ref = vector.emplaceBack();
+ref = "one";
+// vector: ["one"]
+//! [emplace-back-ref]
+
+
 //! [8]
 QVector<QString> vector;
 vector.prepend("one");
diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h
index 0d2be5d51c..1d74f49993 100644
--- a/src/corelib/tools/qarraydataops.h
+++ b/src/corelib/tools/qarraydataops.h
@@ -117,6 +117,9 @@ struct QPodArrayOps
         this->size += int(n);
     }
 
+    template <typename ...Args>
+    void emplaceBack(Args&&... args) { this->emplace(this->end(), T(std::forward<Args>(args)...)); }
+
     void truncate(size_t newSize)
     {
         Q_ASSERT(this->isMutable());
@@ -163,16 +166,28 @@ struct QPodArrayOps
             *where++ = t;
     }
 
-    void insert(T *where, T &&t)
+    template <typename ...Args>
+    void createInPlace(T *where, Args&&... args) { new (where) T(std::forward<Args>(args)...); }
+
+    template <typename ...Args>
+    void emplace(T *where, Args&&... args)
     {
         Q_ASSERT(!this->isShared());
         Q_ASSERT(where >= this->begin() && where <= this->end());
         Q_ASSERT(this->allocatedCapacity() - this->size >= 1);
 
-        ::memmove(static_cast<void *>(where + 1), static_cast<void *>(where),
-                  (static_cast<const T*>(this->end()) - where) * sizeof(T));
-        this->size += 1;
-        new (where) T(std::move(t));
+        if (where == this->end()) {
+            new (this->end()) T(std::forward<Args>(args)...);
+        } else {
+            // Preserve the value, because it might be a reference to some part of the moved chunk
+            T t(std::forward<Args>(args)...);
+
+            ::memmove(static_cast<void *>(where + 1), static_cast<void *>(where),
+                      (static_cast<const T*>(this->end()) - where) * sizeof(T));
+            *where = t;
+        }
+
+        ++this->size;
     }
 
 
@@ -289,6 +304,12 @@ struct QGenericArrayOps
         }
     }
 
+    template <typename ...Args>
+    void emplaceBack(Args&&... args)
+    {
+        this->emplace(this->end(), std::forward<Args>(args)...);
+    }
+
     void truncate(size_t newSize)
     {
         Q_ASSERT(this->isMutable());
@@ -444,31 +465,20 @@ struct QGenericArrayOps
         }
     }
 
-    void insert(T *where, T &&t)
+    template <typename ...Args>
+    void createInPlace(T *where, Args&&... args) { new (where) T(std::forward<Args>(args)...); }
+
+    template <typename iterator, typename ...Args>
+    void emplace(iterator where, Args&&... args)
     {
         Q_ASSERT(!this->isShared());
         Q_ASSERT(where >= this->begin() && where <= this->end());
         Q_ASSERT(this->allocatedCapacity() - this->size >= 1);
 
-        // Array may be truncated at where in case of exceptions
-        T *const end = this->end();
-
-        if (where != end) {
-            // Move elements in array
-            T *readIter = end - 1;
-            T *writeIter = end;
-            new (writeIter) T(std::move(*readIter));
-            while (readIter > where) {
-                --readIter;
-                --writeIter;
-                *writeIter = std::move(*readIter);
-            }
-            *where = std::move(t);
-        } else {
-            new (where) T(std::move(t));
-        }
-
+        createInPlace(this->end(), std::forward<Args>(args)...);
         ++this->size;
+
+        std::rotate(where, this->end() - 1, this->end());
     }
 
     void erase(T *b, T *e)
diff --git a/src/corelib/tools/qvector.h b/src/corelib/tools/qvector.h
index 3e98de41f4..2cfcb2e5dc 100644
--- a/src/corelib/tools/qvector.h
+++ b/src/corelib/tools/qvector.h
@@ -242,10 +242,14 @@ public:
     void append(const_reference t)
     { append(const_iterator(std::addressof(t)), const_iterator(std::addressof(t)) + 1); }
     void append(const_iterator i1, const_iterator i2);
-    void append(value_type &&t);
+    void append(rvalue_ref t) { emplaceBack(std::move(t)); }
     void append(const QVector<T> &l) { append(l.constBegin(), l.constEnd()); }
     void prepend(rvalue_ref t);
     void prepend(const T &t);
+
+    template <typename ...Args>
+    reference emplaceBack(Args&&... args) { return *emplace(count(), std::forward<Args>(args)...); }
+
     iterator insert(int i, parameter_type t)
     { return insert(i, 1, t); }
     iterator insert(int i, int n, parameter_type t);
@@ -264,7 +268,17 @@ public:
         Q_ASSERT_X(isValidIterator(before),  "QVector::insert", "The specified iterator argument 'before' is invalid");
         return insert(std::distance(constBegin(), before), std::move(t));
     }
-    iterator insert(int i, rvalue_ref t);
+    iterator insert(int i, rvalue_ref t) { return emplace(i, std::move(t)); }
+
+    template <typename ...Args>
+    iterator emplace(const_iterator before, Args&&... args)
+    {
+        Q_ASSERT_X(isValidIterator(before),  "QVector::emplace", "The specified iterator argument 'before' is invalid");
+        return emplace(std::distance(constBegin(), before), std::forward<Args>(args)...);
+    }
+
+    template <typename ...Args>
+    iterator emplace(int i, Args&&... args);
 #if 0
     template< class InputIt >
     iterator insert( const_iterator pos, InputIt first, InputIt last );
@@ -388,6 +402,10 @@ public:
     inline void push_front(const T &t) { prepend(t); }
     void pop_back() { removeLast(); }
     void pop_front() { removeFirst(); }
+
+    template <typename ...Args>
+    reference emplace_back(Args&&... args) { return emplaceBack(std::forward<Args>(args)...); }
+
     inline bool empty() const
     { return d->size == 0; }
     inline reference front() { return first(); }
@@ -538,27 +556,6 @@ inline void QVector<T>::append(const_iterator i1, const_iterator i2)
 }
 
 template <typename T>
-inline void QVector<T>::append(value_type &&t)
-{
-    const size_t newSize = size() + 1;
-    const bool isTooSmall = newSize > d->allocatedCapacity();
-    const bool isOverlapping = std::addressof(*d->begin()) <= std::addressof(t)
-            && std::addressof(t) < std::addressof(*d->end());
-    if (isTooSmall || d->needsDetach() || Q_UNLIKELY(isOverlapping)) {
-        typename Data::ArrayOptions flags = d->detachFlags();
-        if (isTooSmall)
-            flags |= Data::GrowsForward;
-        DataPointer detached(Data::allocate(d->detachCapacity(newSize), flags));
-        detached->copyAppend(constBegin(), constEnd());
-        detached->moveAppend(std::addressof(t), std::addressof(t) + 1);
-        d.swap(detached);
-    } else {
-        // we're detached and we can just move data around
-        d->moveAppend(std::addressof(t), std::addressof(t) + 1);
-    }
-}
-
-template <typename T>
 inline typename QVector<T>::iterator
 QVector<T>::insert(int i, int n, parameter_type t)
 {
@@ -592,10 +589,11 @@ QVector<T>::insert(int i, int n, parameter_type t)
 }
 
 template <typename T>
+template <typename ...Args>
 typename QVector<T>::iterator
-QVector<T>::insert(int i, rvalue_ref t)
+QVector<T>::emplace(int i, Args&&... args)
 {
-    Q_ASSERT_X(size_t(i) <= size_t(d->size), "QVector<T>::insert", "index out of range");
+     Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert", "index out of range");
 
     const size_t newSize = size() + 1;
     if (d->needsDetach() || newSize > d->allocatedCapacity()) {
@@ -605,12 +603,24 @@ QVector<T>::insert(int i, rvalue_ref t)
 
         DataPointer detached(Data::allocate(d->detachCapacity(newSize), flags));
         const_iterator where = constBegin() + i;
+
+        // First, create an element to handle cases, when a user moves
+        // the element from a container to the same container
+        detached->createInPlace(detached.begin() + i, std::forward<Args>(args)...);
+
+        // Then, put the first part of the elements to the new location
         detached->copyAppend(constBegin(), where);
-        detached->moveAppend(std::addressof(t), std::addressof(t) + 1);
+
+        // After that, increase the actual size, because we created
+        // one extra element
+        ++detached.size;
+
+        // Finally, put the rest of the elements to the new location
         detached->copyAppend(where, constEnd());
+
         d.swap(detached);
     } else {
-        d->insert(d.begin() + i, std::move(t));
+        d->emplace(d.begin() + i, std::forward<Args>(args)...);
     }
     return d.begin() + i;
 }
diff --git a/src/corelib/tools/qvector.qdoc b/src/corelib/tools/qvector.qdoc
index 116d962411..a5ea4073f8 100644
--- a/src/corelib/tools/qvector.qdoc
+++ b/src/corelib/tools/qvector.qdoc
@@ -646,6 +646,28 @@
     \sa append(), insert()
 */
 
+/*!
+    \fn template <typename T> template <typename ...Args> T &QVector<T>::emplaceBack(Args&&... args)
+    \fn template <typename T> template <typename ...Args> T &QVector<T>::emplace_back(Args&&... args)
+
+    Adds a new element to the end for the container. This new element
+    is constructed in-place using \a args as the arguments for its
+    construction.
+
+    Returns a reference to the new element.
+
+    Example:
+    \snippet code/src_corelib_tools_qvector.cpp emplace-back
+
+    It is also possible to access a newly created object by using
+    returned reference:
+    \snippet code/src_corelib_tools_qvector.cpp emplace-back-ref
+
+    This is the same as vector.emplace(vector.size(), \a args).
+
+    \sa emplace
+*/
+
 /*! \fn template <typename T> void QVector<T>::insert(int i, const T &value)
     \fn template <typename T> void QVector<T>::insert(int i, T &&value)
 
@@ -693,6 +715,26 @@
     first of the inserted items.
 */
 
+/*!
+    \fn template <typename T> template <typename ...Args> QVector<T>::iterator QVector<T>::emplace(int i, Args&&... args)
+
+    Extends the container by inserting a new element at position \a i.
+    This new element is constructed in-place using \a args as the
+    arguments for its construction.
+
+    Returns an iterator to the new element.
+
+    Example:
+    \snippet code/src_corelib_tools_qvector.cpp emplace
+
+    \note It is garanteed that the element will be created in place
+          at the beginning, but after that it might be copied or
+          moved to the right position.
+
+    \sa emplaceBack
+*/
+
+
 /*! \fn template <typename T> void QVector<T>::replace(int i, const T &value)
 
     Replaces the item at index position \a i with \a value.
@@ -838,6 +880,17 @@
     \sa takeFirst(), removeLast()
 */
 
+/*!
+    \fn template <typename T> template <typename ...Args> QVector<T>::iterator QVector<T>::emplace(QVector<T>::iterator before, Args&&... args)
+
+    \overload
+
+    Creates a new element in front of the item pointed to by the
+    iterator \a before. This new element is constructed in-place
+    using \a args as the arguments for its construction.
+
+    Returns an iterator to the new element.
+*/
 
 /*! \fn template <typename T> QVector<T> &QVector<T>::fill(const T &value, int size = -1)
 
diff --git a/tests/auto/corelib/tools/qvector/tst_qvector.cpp b/tests/auto/corelib/tools/qvector/tst_qvector.cpp
index 7a69e844d4..6ae312fb8d 100644
--- a/tests/auto/corelib/tools/qvector/tst_qvector.cpp
+++ b/tests/auto/corelib/tools/qvector/tst_qvector.cpp
@@ -324,6 +324,18 @@ private slots:
 
     void swapItemsAt() const;
 
+    void emplaceInt();
+    void emplaceCustom();
+    void emplaceMovable();
+    void emplaceConsistentWithStdVectorInt();
+    void emplaceConsistentWithStdVectorCustom();
+    void emplaceConsistentWithStdVectorMovable();
+    void emplaceReturnsIterator();
+    void emplaceBack();
+    void emplaceBackReturnsRef();
+    void emplaceWithElementFromTheSameContainer();
+    void emplaceWithElementFromTheSameContainer_data();
+
 private:
     template<typename T> void copyConstructor() const;
     template<typename T> void add() const;
@@ -349,6 +361,8 @@ private:
     template<typename T> void initializeList();
     template<typename T> void detach() const;
     template<typename T> void detachThreadSafety() const;
+    template<typename T> void emplaceImpl() const;
+    template<typename T> void emplaceConsistentWithStdVectorImpl() const;
 };
 
 
@@ -2645,5 +2659,172 @@ void tst_QVector::swapItemsAt() const
     QCOMPARE(copy.at(2), 2);
 }
 
+void tst_QVector::emplaceInt()
+{
+    emplaceImpl<int>();
+}
+
+void tst_QVector::emplaceCustom()
+{
+    emplaceImpl<Custom>();
+}
+
+void tst_QVector::emplaceMovable()
+{
+    emplaceImpl<Movable>();
+}
+
+void tst_QVector::emplaceConsistentWithStdVectorInt()
+{
+    emplaceConsistentWithStdVectorImpl<int>();
+}
+
+void tst_QVector::emplaceConsistentWithStdVectorCustom()
+{
+    emplaceConsistentWithStdVectorImpl<Custom>();
+}
+
+void tst_QVector::emplaceConsistentWithStdVectorMovable()
+{
+    emplaceConsistentWithStdVectorImpl<Movable>();
+}
+
+void tst_QVector::emplaceReturnsIterator()
+{
+    QVector<Movable> vec;
+
+    vec.emplace(0, 'k')->i = 'p';
+
+    QCOMPARE(vec[0].i, 'p');
+}
+
+void tst_QVector::emplaceBack()
+{
+    QScopedValueRollback<QAtomicInt> rollback(Movable::counter, 0);
+
+    QVector<Movable> vec;
+
+    vec.emplaceBack('k');
+
+    QCOMPARE(Movable::counter, 1);
+}
+
+void tst_QVector::emplaceBackReturnsRef()
+{
+    QVector<Movable> vec;
+
+    vec.emplaceBack('k').i = 'p';
+
+    QCOMPARE(vec.at(0).i, 'p');
+}
+
+void tst_QVector::emplaceWithElementFromTheSameContainer()
+{
+    QFETCH(int, elementPos);
+    QFETCH(int, insertPos);
+    QFETCH(bool, doCopy);
+
+    QVector<QString> vec {"a", "b", "c", "d", "e"};
+    const QString e = vec[elementPos];
+
+    if (doCopy)
+        vec.emplace(insertPos, vec[elementPos]);
+    else
+        vec.emplace(insertPos, std::move(vec[elementPos]));
+
+    QCOMPARE(vec[insertPos], e);
+}
+
+void tst_QVector::emplaceWithElementFromTheSameContainer_data()
+{
+    QTest::addColumn<int>("elementPos");
+    QTest::addColumn<int>("insertPos");
+    QTest::addColumn<bool>("doCopy");
+
+    for (int i = 0; i < 2; ++i) {
+        const bool doCopy = i == 0;
+        const char *opName = doCopy ? "copy" : "move";
+
+        QTest::addRow("%s: begin  -> end"   , opName) << 0 << 5 << doCopy;
+        QTest::addRow("%s: begin  -> middle", opName) << 0 << 2 << doCopy;
+        QTest::addRow("%s: middle -> begin" , opName) << 2 << 0 << doCopy;
+        QTest::addRow("%s: middle -> end"   , opName) << 2 << 5 << doCopy;
+        QTest::addRow("%s: end    -> middle", opName) << 4 << 2 << doCopy;
+        QTest::addRow("%s: end    -> begin" , opName) << 4 << 0 << doCopy;
+    }
+}
+
+template<typename T>
+void tst_QVector::emplaceImpl() const
+{
+    QVector<T> vec {'a', 'b', 'c', 'd'};
+
+    vec.emplace(2, 'k');
+
+    QCOMPARE(vec[2], T('k'));
+}
+
+template <class T>
+static void vecEq(const QVector<T> &qVec, const std::vector<T> &stdVec)
+{
+    QCOMPARE(std::size_t(qVec.size()), stdVec.size());
+    QVERIFY(std::equal(qVec.begin(), qVec.end(), stdVec.begin(), stdVec.end()));
+}
+
+template <class T>
+static void squeezeVec(QVector<T> &qVec, std::vector<T> &stdVec)
+{
+    qVec.squeeze();
+    stdVec.shrink_to_fit();
+}
+
+template<typename T>
+void tst_QVector::emplaceConsistentWithStdVectorImpl() const
+{
+    QVector<T> qVec {'a', 'b', 'c', 'd', 'e'};
+    std::vector<T> stdVec {'a', 'b', 'c', 'd', 'e'};
+    vecEq(qVec, stdVec);
+
+    qVec.emplaceBack('f');
+    stdVec.emplace_back('f');
+    vecEq(qVec, stdVec);
+
+    qVec.emplace(3, 'g');
+    stdVec.emplace(stdVec.begin() + 3, 'g');
+    vecEq(qVec, stdVec);
+
+    qVec.emplaceBack(std::move(qVec[0]));
+    stdVec.emplace_back(std::move(stdVec[0]));
+    vecEq(qVec, stdVec);
+
+    squeezeVec(qVec, stdVec);
+
+    qVec.emplaceBack(std::move(qVec[1]));
+    stdVec.emplace_back(std::move(stdVec[1]));
+    vecEq(qVec, stdVec);
+
+    squeezeVec(qVec, stdVec);
+
+    qVec.emplace(3, std::move(qVec[5]));
+    stdVec.emplace(stdVec.begin() + 3, std::move(stdVec[5]));
+    vecEq(qVec, stdVec);
+
+    qVec.emplaceBack(qVec[3]);
+    stdVec.emplace_back(stdVec[3]);
+    vecEq(qVec, stdVec);
+
+    squeezeVec(qVec, stdVec);
+
+    qVec.emplaceBack(qVec[4]);
+    stdVec.emplace_back(stdVec[4]);
+    vecEq(qVec, stdVec);
+
+    squeezeVec(qVec, stdVec);
+
+    qVec.emplace(5, qVec[7]);
+    stdVec.emplace(stdVec.begin() + 5, stdVec[7]);
+    vecEq(qVec, stdVec);
+}
+
 QTEST_MAIN(tst_QVector)
 #include "tst_qvector.moc"