diff options
author | Dennis Oberst <dennis.oberst@qt.io> | 2023-04-03 17:16:18 +0200 |
---|---|---|
committer | Marc Mutz <marc.mutz@qt.io> | 2023-05-16 20:09:39 +0200 |
commit | bbbe5f45c4d354ef977d4e09459ef5ae4d6db0da (patch) | |
tree | 510a79687d3b5201465b65a1129d4238147f9775 | |
parent | d8bdb66e82b0a248d4bbc9f3898f3d8b61620dbd (diff) | |
download | qtbase-bbbe5f45c4d354ef977d4e09459ef5ae4d6db0da.tar.gz |
QList: add STL-style assign()
Implemented assign() methods for QList to align with the criteria of
std::vector, addressing the previously missing functionality.
Reference:
https://en.cppreference.com/w/cpp/container/vector/assign
[ChangeLog][QtCore][QList] Added assign().
Fixes: QTBUG-106196
Change-Id: I5df8689c020dafde68d2cd7d09c769744fa8f137
Reviewed-by: Marc Mutz <marc.mutz@qt.io>
Reviewed-by: MÃ¥rten Nordheim <marten.nordheim@qt.io>
-rw-r--r-- | src/corelib/tools/qarraydatapointer.h | 47 | ||||
-rw-r--r-- | src/corelib/tools/qlist.h | 23 | ||||
-rw-r--r-- | src/corelib/tools/qlist.qdoc | 50 | ||||
-rw-r--r-- | tests/auto/corelib/tools/containerapisymmetry/tst_containerapisymmetry.cpp | 5 | ||||
-rw-r--r-- | tests/auto/corelib/tools/qlist/tst_qlist.cpp | 64 |
5 files changed, 187 insertions, 2 deletions
diff --git a/src/corelib/tools/qarraydatapointer.h b/src/corelib/tools/qarraydatapointer.h index 5e89fd0026..b458dc3626 100644 --- a/src/corelib/tools/qarraydatapointer.h +++ b/src/corelib/tools/qarraydatapointer.h @@ -305,6 +305,53 @@ public: this->ptr = res; } + template <typename InputIterator> + void assign(InputIterator first, InputIterator last) + { + // This function only provides the basic exception guarantee. + constexpr bool IsFwdIt = std::is_convertible_v< + typename std::iterator_traits<InputIterator>::iterator_category, + std::forward_iterator_tag>; + + if constexpr (IsFwdIt) { + const qsizetype n = std::distance(first, last); + // Use of freeSpaceAtBegin() isn't, yet, implemented. + const auto usableCapacity = constAllocatedCapacity() - freeSpaceAtBegin(); + if (needsDetach() || n > usableCapacity) { + QArrayDataPointer allocated(Data::allocate(detachCapacity(n))); + swap(allocated); + } + } else if (needsDetach()) { + QArrayDataPointer allocated(Data::allocate(allocatedCapacity())); + swap(allocated); + // We don't want to copy data that we know we'll overwrite + } + + auto dst = begin(); + const auto dend = end(); + while (true) { + if (first == last) { // ran out of elements to assign + std::destroy(dst, dend); + break; + } + if (dst == dend) { // ran out of existing elements to overwrite + if constexpr (IsFwdIt) { + dst = std::uninitialized_copy(first, last, dst); + break; + } else { + do { + (*this)->emplace(size, *first); + } while (++first != last); + return; // size() is already correct (and dst invalidated)! + } + } + *dst = *first; // overwrite existing element + ++dst; + ++first; + } + size = dst - begin(); + } + // forwards from QArrayData qsizetype allocatedCapacity() noexcept { return d ? d->allocatedCapacity() : 0; } qsizetype constAllocatedCapacity() const noexcept { return d ? d->constAllocatedCapacity() : 0; } diff --git a/src/corelib/tools/qlist.h b/src/corelib/tools/qlist.h index d61b90503a..5f5dad583e 100644 --- a/src/corelib/tools/qlist.h +++ b/src/corelib/tools/qlist.h @@ -16,6 +16,8 @@ #include <initializer_list> #include <type_traits> +class tst_QList; + QT_BEGIN_NAMESPACE namespace QtPrivate { @@ -75,10 +77,15 @@ class QList using DataPointer = QArrayDataPointer<T>; class DisableRValueRefs {}; + friend class ::tst_QList; + DataPointer d; template <typename V, typename U> friend qsizetype QtPrivate::indexOf(const QList<V> &list, const U &u, qsizetype from) noexcept; template <typename V, typename U> friend qsizetype QtPrivate::lastIndexOf(const QList<V> &list, const U &u, qsizetype from) noexcept; + // This alias prevents the QtPrivate namespace from being exposed into the docs. + template <typename InputIterator> + using if_input_iterator = QtPrivate::IfIsInputIterator<InputIterator>; public: using Type = T; @@ -287,7 +294,8 @@ public: d->copyAppend(args.begin(), args.end()); return *this; } - template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator> = true> + + template <typename InputIterator, if_input_iterator<InputIterator> = true> QList(InputIterator i1, InputIterator i2) { if constexpr (!std::is_convertible_v<typename std::iterator_traits<InputIterator>::iterator_category, std::forward_iterator_tag>) { @@ -488,6 +496,19 @@ public: } } + void assign(qsizetype n, parameter_type t) + { + Q_ASSERT(n >= 0); + fill(t, n); + } + + template <typename InputIterator, if_input_iterator<InputIterator> = true> + void assign(InputIterator first, InputIterator last) + { d.assign(first, last); } + + void assign(std::initializer_list<T> l) + { assign(l.begin(), l.end()); } + template <typename ...Args> iterator emplace(const_iterator before, Args&&... args) { diff --git a/src/corelib/tools/qlist.qdoc b/src/corelib/tools/qlist.qdoc index a500d2fe60..a23e7d73fb 100644 --- a/src/corelib/tools/qlist.qdoc +++ b/src/corelib/tools/qlist.qdoc @@ -274,11 +274,15 @@ Constructs a list from the std::initializer_list given by \a args. */ -/*! \fn template <typename T> template<typename InputIterator> QList<T>::QList(InputIterator first, InputIterator last) +/*! \fn template <typename T> template<typename InputIterator, if_input_iterator<InputIterator>> QList<T>::QList(InputIterator first, InputIterator last) \since 5.14 Constructs a list with the contents in the iterator range [\a first, \a last). + \note This constructor only participates in overload resolution if + \c InputIterator meets the requirements of a + \l {https://en.cppreference.com/w/cpp/named_req/InputIterator} {LegacyInputIterator}. + The value type of \c InputIterator must be convertible to \c T. */ @@ -1533,3 +1537,47 @@ \sa erase */ + +/*! \fn template <typename T> void QList<T>::assign(qsizetype n, parameter_type t) + \since 6.6 + + Replaces the contents of this list with \a n copies of \a t. + + The size of this list will be equal to \a n. + + This function will only allocate memory if \a n exceeds the capacity of the + list or this list is shared. +*/ + +/*! \fn template <typename T> template <typename InputIterator, if_input_iterator<InputIterator>> void QList<T>::assign(InputIterator first, InputIterator last) + \since 6.6 + + Replaces the contents of this list with a copy of the elements in the + iterator range [\a first, \a last). + + The size of this list will be equal to the number of elements in the + range [\a first, \a last). + + This function will only allocate memory if the number of elements in the + range exceeds the capacity of this list or this list is shared. + + \note This function overload only participates in overload resolution if + \c InputIterator meets the requirements of a + \l {https://en.cppreference.com/w/cpp/named_req/InputIterator} {LegacyInputIterator}. + + \note The behavior is undefined if either argument is an iterator into + *this. +*/ + +/*! \fn template <typename T> void QList<T>::assign(std::initializer_list<T> l) + \since 6.6 + + Replaces the contents of this list with a copy of the elements of + \a l. + + The size of this list will be equal to the number of elements in + \a l. + + This function only allocates memory if the number of elements in \a l + exceeds the capacity of this list or this list is shared. +*/ diff --git a/tests/auto/corelib/tools/containerapisymmetry/tst_containerapisymmetry.cpp b/tests/auto/corelib/tools/containerapisymmetry/tst_containerapisymmetry.cpp index f3909cd4e8..24f5dba17e 100644 --- a/tests/auto/corelib/tools/containerapisymmetry/tst_containerapisymmetry.cpp +++ b/tests/auto/corelib/tools/containerapisymmetry/tst_containerapisymmetry.cpp @@ -338,6 +338,7 @@ private: private Q_SLOTS: void assign_std_vector() { assign_impl<std::vector<int>>(); }; void assign_QVarLengthArray() { assign_impl<QVarLengthArray<int, 4>>(); }; + void assign_QList() { assign_impl<QList<int>>(); } private: template <typename Container> @@ -802,6 +803,10 @@ void tst_ContainerApiSymmetry::assign_impl() const iter.assign(8, tData); c.assign(iter.begin(), iter.end()); CHECK(c, tData, c.size(), S(8), c.capacity(), std::max(oldCapacity, S(8))); + + c.assign(iter.begin(), iter.begin()); + QCOMPARE_EQ(c.size(), S(0)); + QCOMPARE_EQ(c.capacity(), std::max(oldCapacity, S(8))); } { // range version for input iterator diff --git a/tests/auto/corelib/tools/qlist/tst_qlist.cpp b/tests/auto/corelib/tools/qlist/tst_qlist.cpp index 482079b0fe..050bb80ab1 100644 --- a/tests/auto/corelib/tools/qlist/tst_qlist.cpp +++ b/tests/auto/corelib/tools/qlist/tst_qlist.cpp @@ -231,6 +231,9 @@ private slots: void appendCustom() const { append<Custom>(); } void appendRvalue() const; void appendList() const; + void assignInt() const { assign<int>(); } + void assignMovable() const { assign<Movable>(); } + void assignCustom() const { assign<Custom>(); } void at() const; void capacityInt() const { capacity<int>(); } void capacityMovable() const { capacity<Movable>(); } @@ -396,6 +399,7 @@ private: template<typename T> void testAssignment() const; template<typename T> void add() const; template<typename T> void append() const; + template<typename T> void assign() const; template<typename T> void assignFromInitializerList() const; template<typename T> void capacity() const; template<typename T> void clear() const; @@ -750,6 +754,66 @@ void tst_QList::append() const } } +template <typename T> +void tst_QList::assign() const +{ + TST_QLIST_CHECK_LEAKS(T) + { + QList<T> myvec; + myvec.assign(2, T_FOO); + QVERIFY(myvec.isDetached()); + QCOMPARE(myvec, QList<T>() << T_FOO << T_FOO); + + QList<T> myvecCopy = myvec; + QVERIFY(!myvec.isDetached()); + QVERIFY(!myvecCopy.isDetached()); + QVERIFY(myvec.isSharedWith(myvecCopy)); + QVERIFY(myvecCopy.isSharedWith(myvec)); + + myvec.assign(3, T_BAR); + QCOMPARE(myvec, QList<T>() << T_BAR << T_BAR << T_BAR); + QVERIFY(myvec.isDetached()); + QVERIFY(myvecCopy.isDetached()); + QVERIFY(!myvec.isSharedWith(myvecCopy)); + QVERIFY(!myvecCopy.isSharedWith(myvec)); + } + { + QList<T> myvec; + myvec.assign(4, T_FOO); + QVERIFY(myvec.isDetached()); + QCOMPARE(myvec, QList<T>() << T_FOO << T_FOO << T_FOO << T_FOO); + + QList<T> myvecCopy = myvec; + QVERIFY(!myvec.isDetached()); + QVERIFY(!myvecCopy.isDetached()); + QVERIFY(myvec.isSharedWith(myvecCopy)); + QVERIFY(myvecCopy.isSharedWith(myvec)); + + myvecCopy.assign(myvec.begin(), myvec.begin() + 2); + QVERIFY(myvec.isDetached()); + QVERIFY(myvecCopy.isDetached()); + QVERIFY(!myvec.isSharedWith(myvecCopy)); + QVERIFY(!myvecCopy.isSharedWith(myvec)); + QCOMPARE(myvecCopy, QList<T>() << T_FOO << T_FOO); + } + { + // Test the prepend optimization. + QList<T> withFreeSpaceAtBegin(16, T_FOO); + // try at most 100 times to create freeSpaceAtBegin(): + for (int i = 0; i < 100 && !withFreeSpaceAtBegin.d.freeSpaceAtBegin(); ++i) + withFreeSpaceAtBegin.prepend(T_FOO); + QCOMPARE_GT(withFreeSpaceAtBegin.d.freeSpaceAtBegin(), 0); + const auto oldData = withFreeSpaceAtBegin.constData(); + std::vector<T> v(withFreeSpaceAtBegin.capacity(), T_BAR); + withFreeSpaceAtBegin.assign(v.begin(), v.end()); + QCOMPARE_EQ(withFreeSpaceAtBegin.d.freeSpaceAtBegin(), 0); + // TODO: Check for equality after the prepend optimization + // the following test checks that we didn't reallocate, but re-used the prepend buffer + QEXPECT_FAIL("","Use of freeSpaceAtBegin() isn't, yet, implemented", Continue); + QVERIFY(QtPrivate::q_points_into_range(oldData, withFreeSpaceAtBegin)); + } +} + void tst_QList::appendRvalue() const { QList<QString> v; |