include/QtCore/qlist.h

0001 // Copyright (C) 2020 The Qt Company Ltd.
0002 // Copyright (C) 2019 Intel Corporation
0003 // SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
0004 // Qt-Security score:significant reason:default
0005
0006 #ifndef QLIST_H
0007 #define QLIST_H
0008
0009 #include <QtCore/qarraydatapointer.h>
0010 #include <QtCore/qcompare.h>
0011 #include <QtCore/qnamespace.h>
0012 #include <QtCore/qhashfunctions.h>
0013 #include <QtCore/qiterator.h>
0014 #include <QtCore/qcontainertools_impl.h>
0015 #include <QtCore/qnamespace.h>
0016 #include <QtCore/qttypetraits.h>
0017
0018 #include <functional>
0019 #include <limits>
0020 #include <initializer_list>
0021 #include <type_traits>
0022
0023 class tst_QList;
0024
0025 QT_BEGIN_NAMESPACE
0026
0027 namespace QtPrivate {
0028    template <typename V, typename U> qsizetype indexOf(const QList<V> &list, const U &u, qsizetype from) noexcept;
0029    template <typename V, typename U> qsizetype lastIndexOf(const QList<V> &list, const U &u, qsizetype from) noexcept;
0030 }
0031
0032 template <typename T> struct QListSpecialMethodsBase
0033 {
0034 protected:
0035     QListSpecialMethodsBase() = default;
0036     QT_DECLARE_RO5_SMF_AS_DEFAULTED(QListSpecialMethodsBase)
0037
0038     using Self = QList<T>;
0039     Self *self() { return static_cast<Self *>(this); }
0040     const Self *self() const { return static_cast<const Self *>(this); }
0041
0042 public:
0043     template <typename AT = T>
0044     qsizetype indexOf(const AT &t, qsizetype from = 0) const noexcept;
0045     template <typename AT = T>
0046     qsizetype lastIndexOf(const AT &t, qsizetype from = -1) const noexcept;
0047
0048     template <typename AT = T>
0049     bool contains(const AT &t) const noexcept
0050     {
0051         return self()->indexOf(t) != -1;
0052     }
0053 };
0054 template <typename T> struct QListSpecialMethods : QListSpecialMethodsBase<T>
0055 {
0056 protected:
0057     QListSpecialMethods() = default;
0058     QT_DECLARE_RO5_SMF_AS_DEFAULTED(QListSpecialMethods)
0059
0060 public:
0061     using QListSpecialMethodsBase<T>::indexOf;
0062     using QListSpecialMethodsBase<T>::lastIndexOf;
0063     using QListSpecialMethodsBase<T>::contains;
0064 };
0065 template <> struct QListSpecialMethods<QByteArray>;
0066 template <> struct QListSpecialMethods<QString>;
0067
0068 #if !defined(QT_STRICT_QLIST_ITERATORS) && (QT_VERSION >= QT_VERSION_CHECK(6, 6, 0)) && !defined(Q_OS_WIN)
0069 #define QT_STRICT_QLIST_ITERATORS
0070 #endif
0071
0072 #ifdef Q_QDOC // define QVector for QDoc
0073 template<typename T> class QVector : public QList<T> {};
0074 #endif
0075
0076 template <typename T>
0077 class QList
0078 #ifndef Q_QDOC
0079     : public QListSpecialMethods<T>
0080 #endif
0081 {
0082     using Data = QTypedArrayData<T>;
0083     using DataOps = QArrayDataOps<T>;
0084     using DataPointer = QArrayDataPointer<T>;
0085     class DisableRValueRefs {};
0086
0087     friend class ::tst_QList;
0088
0089     DataPointer d;
0090
0091     template <typename V, typename U> friend qsizetype QtPrivate::indexOf(const QList<V> &list, const U &u, qsizetype from) noexcept;
0092     template <typename V, typename U> friend qsizetype QtPrivate::lastIndexOf(const QList<V> &list, const U &u, qsizetype from) noexcept;
0093     // This alias prevents the QtPrivate namespace from being exposed into the docs.
0094     template <typename InputIterator>
0095     using if_input_iterator = QtPrivate::IfIsInputIterator<InputIterator>;
0096
0097 public:
0098     using Type = T;
0099     using value_type = T;
0100     using pointer = T *;
0101     using const_pointer = const T *;
0102     using reference = T &;
0103     using const_reference = const T &;
0104     using size_type = qsizetype;
0105     using difference_type = qptrdiff;
0106 #ifndef Q_QDOC
0107     using parameter_type = typename DataPointer::parameter_type;
0108     using rvalue_ref = typename std::conditional<DataPointer::pass_parameter_by_value, DisableRValueRefs, T &&>::type;
0109 #else  // simplified aliases for QDoc
0110     using parameter_type = const T &;
0111     using rvalue_ref = T &&;
0112 #endif
0113
0114     DataPointer &data_ptr() &             { return d; }
0115     const DataPointer &data_ptr() const & { return d; }
0116     DataPointer &&data_ptr() &&           { return std::move(d); }
0117     // No current use-case for a `const &&` overload
0118
0119     class const_iterator;
0120     class iterator {
0121         friend class QList<T>;
0122         friend class const_iterator;
0123         T *i = nullptr;
0124 #ifdef QT_STRICT_QLIST_ITERATORS
0125         inline constexpr explicit iterator(T *n) : i(n) {}
0126 #endif
0127
0128     public:
0129         using difference_type = qsizetype;
0130         using value_type = T;
0131 #ifdef QT_COMPILER_HAS_LWG3346
0132         using iterator_concept = std::contiguous_iterator_tag;
0133 #endif
0134         using element_type = value_type;
0135         using iterator_category = std::random_access_iterator_tag;
0136         using pointer = T *;
0137         using reference = T &;
0138
0139         inline constexpr iterator() = default;
0140 #ifndef QT_STRICT_QLIST_ITERATORS
0141         inline constexpr explicit iterator(T *n) : i(n) {}
0142 #endif
0143         inline T &operator*() const { return *i; }
0144         inline T *operator->() const { return i; }
0145         inline T &operator[](qsizetype j) const { return *(i + j); }
0146 #ifdef __cpp_lib_three_way_comparison
0147         friend constexpr auto operator<=>(iterator, iterator) noexcept = default;
0148         friend constexpr bool operator==(iterator, iterator) noexcept = default;
0149 #else
0150         inline constexpr bool operator==(iterator o) const { return i == o.i; }
0151         inline constexpr bool operator!=(iterator o) const { return i != o.i; }
0152         inline constexpr bool operator<(iterator other) const { return i < other.i; }
0153         inline constexpr bool operator<=(iterator other) const { return i <= other.i; }
0154         inline constexpr bool operator>(iterator other) const { return i > other.i; }
0155         inline constexpr bool operator>=(iterator other) const { return i >= other.i; }
0156         inline constexpr bool operator==(const_iterator o) const { return i == o.i; }
0157         inline constexpr bool operator!=(const_iterator o) const { return i != o.i; }
0158         inline constexpr bool operator<(const_iterator other) const { return i < other.i; }
0159         inline constexpr bool operator<=(const_iterator other) const { return i <= other.i; }
0160         inline constexpr bool operator>(const_iterator other) const { return i > other.i; }
0161         inline constexpr bool operator>=(const_iterator other) const { return i >= other.i; }
0162 #endif // __cpp_lib_three_way_comparison
0163         inline constexpr bool operator==(pointer p) const { return i == p; }
0164         inline constexpr bool operator!=(pointer p) const { return i != p; }
0165         inline iterator &operator++() { ++i; return *this; }
0166         inline iterator operator++(int) { auto copy = *this; ++*this; return copy; }
0167         inline iterator &operator--() { --i; return *this; }
0168         inline iterator operator--(int) { auto copy = *this; --*this; return copy; }
0169         inline qsizetype operator-(iterator j) const { return i - j.i; }
0170 #if QT_DEPRECATED_SINCE(6, 3) && !defined(QT_STRICT_QLIST_ITERATORS)
0171         QT_DEPRECATED_VERSION_X_6_3("Use operator* or operator-> rather than relying on "
0172                                     "the implicit conversion between a QList/QVector::iterator "
0173                                     "and a raw pointer")
0174         inline operator T*() const { return i; }
0175
0176         template <typename Int> std::enable_if_t<std::is_integral_v<Int>, iterator>
0177         &operator+=(Int j) { i+=j; return *this; }
0178         template <typename Int> std::enable_if_t<std::is_integral_v<Int>, iterator>
0179         &operator-=(Int j) { i-=j; return *this; }
0180         template <typename Int> std::enable_if_t<std::is_integral_v<Int>, iterator>
0181         operator+(Int j) const { return iterator(i+j); }
0182         template <typename Int> std::enable_if_t<std::is_integral_v<Int>, iterator>
0183         operator-(Int j) const { return iterator(i-j); }
0184         template <typename Int> friend std::enable_if_t<std::is_integral_v<Int>, iterator>
0185         operator+(Int j, iterator k) { return k + j; }
0186 #else
0187         inline iterator &operator+=(qsizetype j) { i += j; return *this; }
0188         inline iterator &operator-=(qsizetype j) { i -= j; return *this; }
0189         inline iterator operator+(qsizetype j) const { return iterator(i + j); }
0190         inline iterator operator-(qsizetype j) const { return iterator(i - j); }
0191         friend inline iterator operator+(qsizetype j, iterator k) { return k + j; }
0192 #endif
0193     };
0194
0195     class const_iterator {
0196         friend class QList<T>;
0197         friend class iterator;
0198         const T *i = nullptr;
0199 #ifdef QT_STRICT_QLIST_ITERATORS
0200         inline constexpr explicit const_iterator(const T *n) : i(n) {}
0201 #endif
0202
0203     public:
0204         using difference_type = qsizetype;
0205         using value_type = T;
0206 #ifdef QT_COMPILER_HAS_LWG3346
0207         using iterator_concept = std::contiguous_iterator_tag;
0208 #endif
0209         using element_type = const value_type;
0210         using iterator_category = std::random_access_iterator_tag;
0211         using pointer = const T *;
0212         using reference = const T &;
0213
0214         inline constexpr const_iterator() = default;
0215 #ifndef QT_STRICT_QLIST_ITERATORS
0216         inline constexpr explicit const_iterator(const T *n) : i(n) {}
0217 #endif
0218         inline constexpr const_iterator(iterator o): i(o.i) {}
0219         inline const T &operator*() const { return *i; }
0220         inline const T *operator->() const { return i; }
0221         inline const T &operator[](qsizetype j) const { return *(i + j); }
0222 #ifdef __cpp_lib_three_way_comparison
0223         friend constexpr auto operator<=>(const_iterator, const_iterator) noexcept = default;
0224         friend constexpr auto operator<=>(const_iterator a, iterator b) noexcept
0225         { return a <=> const_iterator(b); }
0226         friend constexpr bool operator==(const_iterator, const_iterator) noexcept = default;
0227         friend constexpr bool operator==(const_iterator a, iterator b) noexcept
0228         { return a == const_iterator(b); }
0229 #else
0230         inline constexpr bool operator==(const_iterator o) const { return i == o.i; }
0231         inline constexpr bool operator!=(const_iterator o) const { return i != o.i; }
0232         inline constexpr bool operator<(const_iterator other) const { return i < other.i; }
0233         inline constexpr bool operator<=(const_iterator other) const { return i <= other.i; }
0234         inline constexpr bool operator>(const_iterator other) const { return i > other.i; }
0235         inline constexpr bool operator>=(const_iterator other) const { return i >= other.i; }
0236         inline constexpr bool operator==(iterator o) const { return i == o.i; }
0237         inline constexpr bool operator!=(iterator o) const { return i != o.i; }
0238         inline constexpr bool operator<(iterator other) const { return i < other.i; }
0239         inline constexpr bool operator<=(iterator other) const { return i <= other.i; }
0240         inline constexpr bool operator>(iterator other) const { return i > other.i; }
0241         inline constexpr bool operator>=(iterator other) const { return i >= other.i; }
0242 #endif // __cpp_lib_three_way_comparison
0243         inline constexpr bool operator==(pointer p) const { return i == p; }
0244         inline constexpr bool operator!=(pointer p) const { return i != p; }
0245         inline const_iterator &operator++() { ++i; return *this; }
0246         inline const_iterator operator++(int) { auto copy = *this; ++*this; return copy; }
0247         inline const_iterator &operator--() { --i; return *this; }
0248         inline const_iterator operator--(int) { auto copy = *this; --*this; return copy; }
0249         inline qsizetype operator-(const_iterator j) const { return i - j.i; }
0250 #if QT_DEPRECATED_SINCE(6, 3) && !defined(QT_STRICT_QLIST_ITERATORS)
0251         QT_DEPRECATED_VERSION_X_6_3("Use operator* or operator-> rather than relying on "
0252                                     "the implicit conversion between a QList/QVector::const_iterator "
0253                                     "and a raw pointer")
0254         inline operator const T*() const { return i; }
0255
0256         template <typename Int> std::enable_if_t<std::is_integral_v<Int>, const_iterator>
0257         &operator+=(Int j) { i+=j; return *this; }
0258         template <typename Int> std::enable_if_t<std::is_integral_v<Int>, const_iterator>
0259         &operator-=(Int j) { i-=j; return *this; }
0260         template <typename Int> std::enable_if_t<std::is_integral_v<Int>, const_iterator>
0261         operator+(Int j) const { return const_iterator(i+j); }
0262         template <typename Int> std::enable_if_t<std::is_integral_v<Int>, const_iterator>
0263         operator-(Int j) const { return const_iterator(i-j); }
0264         template <typename Int> friend std::enable_if_t<std::is_integral_v<Int>, const_iterator>
0265         operator+(Int j, const_iterator k) { return k + j; }
0266 #else
0267         inline const_iterator &operator+=(qsizetype j) { i += j; return *this; }
0268         inline const_iterator &operator-=(qsizetype j) { i -= j; return *this; }
0269         inline const_iterator operator+(qsizetype j) const { return const_iterator(i + j); }
0270         inline const_iterator operator-(qsizetype j) const { return const_iterator(i - j); }
0271         friend inline const_iterator operator+(qsizetype j, const_iterator k) { return k + j; }
0272 #endif
0273     };
0274     using Iterator = iterator;
0275     using ConstIterator = const_iterator;
0276     using reverse_iterator = std::reverse_iterator<iterator>;
0277     using const_reverse_iterator = std::reverse_iterator<const_iterator>;
0278
0279 private:
0280     void resize_internal(qsizetype i);
0281     bool isValidIterator(const_iterator i) const
0282     {
0283         const std::less<const T*> less = {};
0284         return !less(d->end(), i.i) && !less(i.i, d->begin());
0285     }
0286
0287     void verify([[maybe_unused]] qsizetype pos = 0, [[maybe_unused]] qsizetype n = 1) const
0288     {
0289         Q_ASSERT(pos >= 0);
0290         Q_ASSERT(pos <= size());
0291         Q_ASSERT(n >= 0);
0292         Q_ASSERT(n <= size() - pos);
0293     }
0294 public:
0295     QList(DataPointer dd) noexcept
0296         : d(dd)
0297     {
0298     }
0299
0300 public:
0301     constexpr QList() noexcept = default;
0302     explicit QList(qsizetype size)
0303         : d(size)
0304     {
0305         if (size) {
0306             Q_CHECK_PTR(d.data());
0307             d->appendInitialize(size);
0308         }
0309     }
0310     QList(qsizetype size, parameter_type t)
0311         : d(size)
0312     {
0313         if (size) {
0314             Q_CHECK_PTR(d.data());
0315             d->copyAppend(size, t);
0316         }
0317     }
0318
0319     inline QList(std::initializer_list<T> args)
0320         : d(qsizetype(args.size()))
0321     {
0322         if (args.size()) {
0323             Q_CHECK_PTR(d.data());
0324             d->copyAppend(args.begin(), args.end());
0325         }
0326     }
0327
0328     QList<T> &operator=(std::initializer_list<T> args)
0329     {
0330         return assign(args);
0331     }
0332
0333     template <typename InputIterator, if_input_iterator<InputIterator> = true>
0334     QList(InputIterator i1, InputIterator i2)
0335     {
0336         if constexpr (!std::is_convertible_v<typename std::iterator_traits<InputIterator>::iterator_category, std::forward_iterator_tag>) {
0337             std::copy(i1, i2, std::back_inserter(*this));
0338         } else {
0339             const auto distance = std::distance(i1, i2);
0340             if (distance) {
0341                 d = DataPointer(qsizetype(distance));
0342                 Q_CHECK_PTR(d.data());
0343                 // appendIteratorRange can deal with contiguous iterators on its own,
0344                 // this is an optimization for C++17 code.
0345                 if constexpr (std::is_same_v<std::decay_t<InputIterator>, iterator> ||
0346                               std::is_same_v<std::decay_t<InputIterator>, const_iterator>) {
0347                     d->copyAppend(i1.i, i2.i);
0348                 } else {
0349                     d->appendIteratorRange(i1, i2);
0350                }
0351             }
0352         }
0353     }
0354
0355     // This constructor is here for compatibility with QStringList in Qt 5, that has a QStringList(const QString &) constructor
0356     template<typename String, typename = std::enable_if_t<std::is_same_v<T, QString> && std::is_convertible_v<String, QString>>>
0357     inline explicit QList(const String &str)
0358     { append(str); }
0359
0360     QList(qsizetype size, Qt::Initialization)
0361         : d(size)
0362     {
0363         if (size) {
0364             Q_CHECK_PTR(d.data());
0365             d->appendUninitialized(size);
0366         }
0367     }
0368
0369     // compiler-generated special member functions are fine!
0370
0371     void swap(QList &other) noexcept { d.swap(other.d); }
0372
0373 #ifndef Q_QDOC
0374 private:
0375     template <typename U = T,
0376               Qt::if_has_qt_compare_three_way<U, U> = true>
0377     friend auto compareThreeWay(const QList &lhs, const QList &rhs)
0378     {
0379         return QtOrderingPrivate::lexicographicalCompareThreeWay(lhs.begin(), lhs.end(),
0380                                                                  rhs.begin(), rhs.end());
0381     }
0382
0383 #if defined(__cpp_lib_three_way_comparison) && defined(__cpp_lib_concepts)
0384     template <typename U = T,
0385               QtOrderingPrivate::if_has_op_less_or_op_compare_three_way<QList, U> = true>
0386     friend auto operator<=>(const QList &lhs, const QList &rhs)
0387     {
0388         return std::lexicographical_compare_three_way(lhs.begin(), lhs.end(),
0389                                                       rhs.begin(), rhs.end(),
0390                                                       QtOrderingPrivate::synthThreeWay);
0391     }
0392 #endif // __cpp_lib_three_way_comparison && __cpp_lib_concepts
0393
0394 public:
0395     template <typename U = T>
0396     QTypeTraits::compare_eq_result_container<QList, U> operator==(const QList &other) const
0397     {
0398         if (size() != other.size())
0399             return false;
0400         if (begin() == other.begin())
0401             return true;
0402
0403         // do element-by-element comparison
0404         return std::equal(begin(), end(), other.begin(), other.end());
0405     }
0406
0407     template <typename U = T>
0408     QTypeTraits::compare_eq_result_container<QList, U> operator!=(const QList &other) const
0409     {
0410         return !(*this == other);
0411     }
0412
0413 #ifndef __cpp_lib_three_way_comparison
0414     template <typename U = T>
0415     QTypeTraits::compare_lt_result_container<QList, U> operator<(const QList &other) const
0416         noexcept(noexcept(std::lexicographical_compare<typename QList<U>::const_iterator,
0417                                                        typename QList::const_iterator>(
0418                             std::declval<QList<U>>().begin(), std::declval<QList<U>>().end(),
0419                             other.begin(), other.end())))
0420     {
0421         return std::lexicographical_compare(begin(), end(),
0422                                             other.begin(), other.end());
0423     }
0424
0425     template <typename U = T>
0426     QTypeTraits::compare_lt_result_container<QList, U> operator>(const QList &other) const
0427         noexcept(noexcept(other < std::declval<QList<U>>()))
0428     {
0429         return other < *this;
0430     }
0431
0432     template <typename U = T>
0433     QTypeTraits::compare_lt_result_container<QList, U> operator<=(const QList &other) const
0434         noexcept(noexcept(other < std::declval<QList<U>>()))
0435     {
0436         return !(other < *this);
0437     }
0438
0439     template <typename U = T>
0440     QTypeTraits::compare_lt_result_container<QList, U> operator>=(const QList &other) const
0441         noexcept(noexcept(std::declval<QList<U>>() < other))
0442     {
0443         return !(*this < other);
0444     }
0445 #endif // __cpp_lib_three_way_comparison
0446 #else
0447     bool operator==(const QList &other) const;
0448     bool operator!=(const QList &other) const;
0449     bool operator<(const QList &other) const;
0450     bool operator>(const QList &other) const;
0451     bool operator<=(const QList &other) const;
0452     bool operator>=(const QList &other) const;
0453     friend auto operator<=>(const QList &lhs, const QList &rhs);
0454 #endif // Q_QDOC
0455
0456     static constexpr qsizetype maxSize() { return Data::maxSize(); }
0457     constexpr qsizetype size() const noexcept
0458     {
0459         constexpr size_t MaxSize = maxSize();
0460         Q_PRESUME(size_t(d.size) <= MaxSize);
0461         return d.size;
0462     }
0463     constexpr qsizetype count() const noexcept { return size(); }
0464     constexpr qsizetype length() const noexcept { return size(); }
0465
0466     constexpr bool isEmpty() const noexcept { return size() == 0; }
0467
0468     void resize(qsizetype size)
0469     {
0470         resize_internal(size);
0471         if (size > this->size())
0472             d->appendInitialize(size);
0473     }
0474     void resize(qsizetype size, parameter_type c)
0475     {
0476         resize_internal(size);
0477         if (size > this->size())
0478             d->copyAppend(size - this->size(), c);
0479     }
0480     void resizeForOverwrite(qsizetype size)
0481     {
0482         resize_internal(size);
0483         if (size > this->size())
0484             d->appendUninitialized(size);
0485     }
0486
0487     inline qsizetype capacity() const { return qsizetype(d->constAllocatedCapacity()); }
0488     void reserve(qsizetype size);
0489     inline void squeeze();
0490
0491     void detach() { d.detach(); }
0492     bool isDetached() const noexcept { return !d->isShared(); }
0493
0494     inline bool isSharedWith(const QList<T> &other) const { return d == other.d; }
0495
0496     pointer data() { detach(); return d->data(); }
0497     const_pointer data() const noexcept { return d->data(); }
0498     const_pointer constData() const noexcept { return d->data(); }
0499     void clear() {
0500         if (!size())
0501             return;
0502         if (d->needsDetach()) {
0503             // must allocate memory
0504             DataPointer detached(d.allocatedCapacity());
0505             d.swap(detached);
0506         } else {
0507             d->truncate(0);
0508         }
0509     }
0510
0511     const_reference at(qsizetype i) const noexcept
0512     {
0513         Q_ASSERT_X(size_t(i) < size_t(d->size), "QList::at", "index out of range");
0514         return data()[i];
0515     }
0516     reference operator[](qsizetype i)
0517     {
0518         Q_ASSERT_X(size_t(i) < size_t(d->size), "QList::operator[]", "index out of range");
0519         // don't detach() here, we detach in data below:
0520         return data()[i];
0521     }
0522     const_reference operator[](qsizetype i) const noexcept { return at(i); }
0523     void append(parameter_type t) { emplaceBack(t); }
0524     void append(const_iterator i1, const_iterator i2);
0525     void append(rvalue_ref t)
0526     {
0527         if constexpr (DataPointer::pass_parameter_by_value) {
0528             Q_UNUSED(t);
0529         } else {
0530             emplaceBack(std::move(t));
0531         }
0532     }
0533     void append(const QList<T> &l)
0534     {
0535         append(l.constBegin(), l.constEnd());
0536     }
0537     void append(QList<T> &&l);
0538     void prepend(rvalue_ref t) {
0539         if constexpr (DataPointer::pass_parameter_by_value) {
0540             Q_UNUSED(t);
0541         } else {
0542             emplaceFront(std::move(t));
0543         }
0544     }
0545     void prepend(parameter_type t) { emplaceFront(t); }
0546
0547     template<typename... Args>
0548     inline reference emplaceBack(Args &&... args);
0549
0550     template <typename ...Args>
0551     inline reference emplaceFront(Args&&... args);
0552
0553     iterator insert(qsizetype i, parameter_type t)
0554     { return emplace(i, t); }
0555     iterator insert(qsizetype i, qsizetype n, parameter_type t);
0556     iterator insert(const_iterator before, parameter_type t)
0557     {
0558         Q_ASSERT_X(isValidIterator(before),  "QList::insert", "The specified iterator argument 'before' is invalid");
0559         return insert(before, 1, t);
0560     }
0561     iterator insert(const_iterator before, qsizetype n, parameter_type t)
0562     {
0563         Q_ASSERT_X(isValidIterator(before),  "QList::insert", "The specified iterator argument 'before' is invalid");
0564         return insert(std::distance(constBegin(), before), n, t);
0565     }
0566     iterator insert(const_iterator before, rvalue_ref t)
0567     {
0568         Q_ASSERT_X(isValidIterator(before),  "QList::insert", "The specified iterator argument 'before' is invalid");
0569         return insert(std::distance(constBegin(), before), std::move(t));
0570     }
0571     iterator insert(qsizetype i, rvalue_ref t) {
0572         if constexpr (DataPointer::pass_parameter_by_value) {
0573             Q_UNUSED(i);
0574             Q_UNUSED(t);
0575             return end();
0576         } else {
0577             return emplace(i, std::move(t));
0578         }
0579     }
0580
0581     QList &assign(qsizetype n, parameter_type t)
0582     {
0583         Q_ASSERT(n >= 0);
0584         return fill(t, n);
0585     }
0586
0587     template <typename InputIterator, if_input_iterator<InputIterator> = true>
0588     QList &assign(InputIterator first, InputIterator last)
0589     { d->assign(first, last); return *this; }
0590
0591     QList &assign(std::initializer_list<T> l)
0592     {
0593         if (l.size())
0594             return assign(l.begin(), l.end());
0595         clear();
0596         return *this;
0597     }
0598
0599     template <typename ...Args>
0600     iterator emplace(const_iterator before, Args&&... args)
0601     {
0602         Q_ASSERT_X(isValidIterator(before),  "QList::emplace", "The specified iterator argument 'before' is invalid");
0603         return emplace(std::distance(constBegin(), before), std::forward<Args>(args)...);
0604     }
0605
0606     template <typename ...Args>
0607     iterator emplace(qsizetype i, Args&&... args);
0608 #if 0
0609     template< class InputIt >
0610     iterator insert( const_iterator pos, InputIt first, InputIt last );
0611     iterator insert( const_iterator pos, std::initializer_list<T> ilist );
0612 #endif
0613     void replace(qsizetype i, parameter_type t)
0614     {
0615         Q_ASSERT_X(i >= 0 && i < d->size, "QList<T>::replace", "index out of range");
0616         DataPointer oldData;
0617         d.detach(&oldData);
0618         d.data()[i] = t;
0619     }
0620     void replace(qsizetype i, rvalue_ref t)
0621     {
0622         if constexpr (DataPointer::pass_parameter_by_value) {
0623             Q_UNUSED(i);
0624             Q_UNUSED(t);
0625         } else {
0626             Q_ASSERT_X(i >= 0 && i < d->size, "QList<T>::replace", "index out of range");
0627             DataPointer oldData;
0628             d.detach(&oldData);
0629             d.data()[i] = std::move(t);
0630         }
0631     }
0632
0633     void remove(qsizetype i, qsizetype n = 1);
0634     void removeFirst() noexcept;
0635     void removeLast() noexcept;
0636     value_type takeFirst() { Q_ASSERT(!isEmpty()); value_type v = std::move(first()); d->eraseFirst(); return v; }
0637     value_type takeLast() { Q_ASSERT(!isEmpty()); value_type v = std::move(last()); d->eraseLast(); return v; }
0638
0639     QList<T> &fill(parameter_type t, qsizetype size = -1);
0640
0641 #ifndef Q_QDOC
0642     using QListSpecialMethods<T>::contains;
0643     using QListSpecialMethods<T>::indexOf;
0644     using QListSpecialMethods<T>::lastIndexOf;
0645 #else
0646     template <typename AT>
0647     qsizetype indexOf(const AT &t, qsizetype from = 0) const noexcept;
0648     template <typename AT>
0649     qsizetype lastIndexOf(const AT &t, qsizetype from = -1) const noexcept;
0650     template <typename AT>
0651     bool contains(const AT &t) const noexcept;
0652 #endif
0653
0654     template <typename AT = T>
0655     qsizetype count(const AT &t) const noexcept
0656     {
0657         return qsizetype(std::count(data(), data() + size(), t));
0658     }
0659
0660     void removeAt(qsizetype i) { remove(i); }
0661     template <typename AT = T>
0662     qsizetype removeAll(const AT &t)
0663     {
0664         return QtPrivate::sequential_erase_with_copy(*this, t);
0665     }
0666
0667     template <typename AT = T>
0668     bool removeOne(const AT &t)
0669     {
0670         return QtPrivate::sequential_erase_one(*this, t);
0671     }
0672
0673     template <typename Predicate>
0674     qsizetype removeIf(Predicate pred)
0675     {
0676         return QtPrivate::sequential_erase_if(*this, pred);
0677     }
0678
0679     T takeAt(qsizetype i) { T t = std::move((*this)[i]); remove(i); return t; }
0680     void move(qsizetype from, qsizetype to)
0681     {
0682         Q_ASSERT_X(from >= 0 && from < size(), "QList::move(qsizetype, qsizetype)", "'from' is out-of-range");
0683         Q_ASSERT_X(to >= 0 && to < size(), "QList::move(qsizetype, qsizetype)", "'to' is out-of-range");
0684         if (from == to) // don't detach when no-op
0685             return;
0686         detach();
0687         T * const b = d->begin();
0688         if (from < to)
0689             std::rotate(b + from, b + from + 1, b + to + 1);
0690         else
0691             std::rotate(b + to, b + from, b + from + 1);
0692     }
0693
0694     // STL-style
0695     iterator begin() { detach(); return iterator(d->begin()); }
0696     iterator end() { detach(); return iterator(d->end()); }
0697
0698     const_iterator begin() const noexcept { return const_iterator(d->constBegin()); }
0699     const_iterator end() const noexcept { return const_iterator(d->constEnd()); }
0700     const_iterator cbegin() const noexcept { return const_iterator(d->constBegin()); }
0701     const_iterator cend() const noexcept { return const_iterator(d->constEnd()); }
0702     const_iterator constBegin() const noexcept { return const_iterator(d->constBegin()); }
0703     const_iterator constEnd() const noexcept { return const_iterator(d->constEnd()); }
0704     reverse_iterator rbegin() { return reverse_iterator(end()); }
0705     reverse_iterator rend() { return reverse_iterator(begin()); }
0706     const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
0707     const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }
0708     const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(end()); }
0709     const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); }
0710
0711     iterator erase(const_iterator begin, const_iterator end);
0712     inline iterator erase(const_iterator pos) { return erase(pos, pos+1); }
0713
0714     // more Qt
0715     inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); }
0716     inline const T &first() const noexcept { Q_ASSERT(!isEmpty()); return *begin(); }
0717     inline const T &constFirst() const noexcept { Q_ASSERT(!isEmpty()); return *begin(); }
0718     inline T& last() { Q_ASSERT(!isEmpty()); return *(end()-1); }
0719     inline const T &last() const noexcept { Q_ASSERT(!isEmpty()); return *(end()-1); }
0720     inline const T &constLast() const noexcept { Q_ASSERT(!isEmpty()); return *(end()-1); }
0721     inline bool startsWith(parameter_type t) const { return !isEmpty() && first() == t; }
0722     inline bool endsWith(parameter_type t) const { return !isEmpty() && last() == t; }
0723     QList<T> mid(qsizetype pos, qsizetype len = -1) const;
0724
0725     QList<T> first(qsizetype n) const
0726     { verify(0, n); return QList<T>(begin(), begin() + n); }
0727     QList<T> last(qsizetype n) const
0728     { verify(0, n); return QList<T>(end() - n, end()); }
0729     QList<T> sliced(qsizetype pos) const
0730     { verify(pos, 0); return QList<T>(begin() + pos, end()); }
0731     QList<T> sliced(qsizetype pos, qsizetype n) const
0732     { verify(pos, n); return QList<T>(begin() + pos, begin() + pos + n); }
0733
0734     T value(qsizetype i) const { return value(i, T()); }
0735     T value(qsizetype i, parameter_type defaultValue) const;
0736
0737     void swapItemsAt(qsizetype i, qsizetype j) {
0738         Q_ASSERT_X(i >= 0 && i < size() && j >= 0 && j < size(),
0739                     "QList<T>::swap", "index out of range");
0740         detach();
0741         qSwap(d->begin()[i], d->begin()[j]);
0742     }
0743
0744     // STL compatibility
0745     inline void push_back(parameter_type t) { append(t); }
0746     void push_back(rvalue_ref t) { append(std::move(t)); }
0747     void push_front(rvalue_ref t) { prepend(std::move(t)); }
0748     inline void push_front(parameter_type t) { prepend(t); }
0749     void pop_back() noexcept { removeLast(); }
0750     void pop_front() noexcept { removeFirst(); }
0751
0752     template <typename ...Args>
0753     reference emplace_back(Args&&... args) { return emplaceBack(std::forward<Args>(args)...); }
0754
0755     inline bool empty() const noexcept
0756     { return d->size == 0; }
0757     inline reference front() { return first(); }
0758     inline const_reference front() const noexcept { return first(); }
0759     inline reference back() { return last(); }
0760     inline const_reference back() const noexcept { return last(); }
0761     void shrink_to_fit() { squeeze(); }
0762     constexpr qsizetype max_size() const noexcept
0763     {
0764         return maxSize();
0765     }
0766
0767     // comfort
0768     QList<T> &operator+=(const QList<T> &l) { append(l); return *this; }
0769     QList<T> &operator+=(QList<T> &&l) { append(std::move(l)); return *this; }
0770     inline QList<T> operator+(const QList<T> &l) const &
0771     { QList n = *this; n += l; return n; }
0772     QList<T> operator+(const QList<T> &l) &&
0773     { return std::move(*this += l); }
0774     inline QList<T> operator+(QList<T> &&l) const &
0775     { QList n = *this; n += std::move(l); return n; }
0776     QList<T> operator+(QList<T> &&l) &&
0777     { return std::move(*this += std::move(l)); }
0778     inline QList<T> &operator+=(parameter_type t)
0779     { append(t); return *this; }
0780     inline QList<T> &operator<< (parameter_type t)
0781     { append(t); return *this; }
0782     inline QList<T> &operator<<(const QList<T> &l)
0783     { *this += l; return *this; }
0784     inline QList<T> &operator<<(QList<T> &&l)
0785     { *this += std::move(l); return *this; }
0786     inline QList<T> &operator+=(rvalue_ref t)
0787     { append(std::move(t)); return *this; }
0788     inline QList<T> &operator<<(rvalue_ref t)
0789     { append(std::move(t)); return *this; }
0790
0791     // Consider deprecating in 6.4 or later
0792     static QList<T> fromList(const QList<T> &list) noexcept { return list; }
0793     QList<T> toList() const noexcept { return *this; }
0794
0795     static inline QList<T> fromVector(const QList<T> &vector) noexcept { return vector; }
0796     inline QList<T> toVector() const noexcept { return *this; }
0797
0798     template<qsizetype N>
0799     static QList<T> fromReadOnlyData(const T (&t)[N]) noexcept
0800     {
0801         return QList<T>({ nullptr, const_cast<T *>(t), N });
0802     }
0803 };
0804
0805 template <typename InputIterator,
0806           typename ValueType = typename std::iterator_traits<InputIterator>::value_type,
0807           QtPrivate::IfIsInputIterator<InputIterator> = true>
0808 QList(InputIterator, InputIterator) -> QList<ValueType>;
0809
0810 template <typename T>
0811 inline void QList<T>::resize_internal(qsizetype newSize)
0812 {
0813     Q_ASSERT(newSize >= 0);
0814
0815     if (d->needsDetach() || newSize > capacity() - d.freeSpaceAtBegin()) {
0816         d.detachAndGrow(QArrayData::GrowsAtEnd, newSize - d.size, nullptr, nullptr);
0817     } else if (newSize < size()) {
0818         d->truncate(newSize);
0819     }
0820 }
0821
0822 template <typename T>
0823 void QList<T>::reserve(qsizetype asize)
0824 {
0825     // capacity() == 0 for immutable data, so this will force a detaching below
0826     if (asize <= capacity() - d.freeSpaceAtBegin()) {
0827         if (d->flags() & Data::CapacityReserved)
0828             return;  // already reserved, don't shrink
0829         if (!d->isShared()) {
0830             // accept current allocation, don't shrink
0831             d->setFlag(Data::CapacityReserved);
0832             return;
0833         }
0834     }
0835
0836     qsizetype newSize = qMax(asize, size());
0837     DataPointer detached(newSize);
0838     if (newSize)
0839         Q_CHECK_PTR(detached.data());
0840     detached->copyAppend(d->begin(), d->end());
0841     if (detached.d_ptr())
0842         detached->setFlag(Data::CapacityReserved);
0843     d.swap(detached);
0844 }
0845
0846 template <typename T>
0847 inline void QList<T>::squeeze()
0848 {
0849     if (!d.isMutable())
0850         return;
0851     if (d->needsDetach() || size() < capacity()) {
0852         // must allocate memory
0853         DataPointer detached(size());
0854         if (size()) {
0855             Q_CHECK_PTR(detached.data());
0856             if (d.needsDetach())
0857                 detached->copyAppend(d.data(), d.data() + d.size);
0858             else
0859                 detached->moveAppend(d.data(), d.data() + d.size);
0860         }
0861         d.swap(detached);
0862     }
0863     // We're detached so this is fine
0864     d->clearFlag(Data::CapacityReserved);
0865 }
0866
0867 template <typename T>
0868 inline void QList<T>::remove(qsizetype i, qsizetype n)
0869 {
0870     Q_ASSERT_X(size_t(i) + size_t(n) <= size_t(d->size), "QList::remove", "index out of range");
0871     Q_ASSERT_X(n >= 0, "QList::remove", "invalid count");
0872
0873     if (n == 0)
0874         return;
0875
0876     d.detach();
0877     d->erase(d->begin() + i, n);
0878 }
0879
0880 template <typename T>
0881 inline void QList<T>::removeFirst() noexcept
0882 {
0883     Q_ASSERT(!isEmpty());
0884     d.detach();
0885     d->eraseFirst();
0886 }
0887
0888 template <typename T>
0889 inline void QList<T>::removeLast() noexcept
0890 {
0891     Q_ASSERT(!isEmpty());
0892     d.detach();
0893     d->eraseLast();
0894 }
0895
0896
0897 template<typename T>
0898 inline T QList<T>::value(qsizetype i, parameter_type defaultValue) const
0899 {
0900     return size_t(i) < size_t(d->size) ? at(i) : defaultValue;
0901 }
0902
0903 template <typename T>
0904 inline void QList<T>::append(const_iterator i1, const_iterator i2)
0905 {
0906     d->growAppend(i1.i, i2.i);
0907 }
0908
0909 template <typename T>
0910 inline void QList<T>::append(QList<T> &&other)
0911 {
0912     Q_ASSERT(&other != this);
0913     if (other.isEmpty())
0914         return;
0915     if (other.d->needsDetach() || !std::is_nothrow_move_constructible_v<T>)
0916         return append(other);
0917
0918     // due to precondition &other != this, we can unconditionally modify 'this'
0919     d.detachAndGrow(QArrayData::GrowsAtEnd, other.size(), nullptr, nullptr);
0920     Q_ASSERT(d.freeSpaceAtEnd() >= other.size());
0921     d->moveAppend(other.d->begin(), other.d->end());
0922 }
0923
0924 template<typename T>
0925 template<typename... Args>
0926 inline typename QList<T>::reference QList<T>::emplaceFront(Args &&... args)
0927 {
0928     d->emplace(0, std::forward<Args>(args)...);
0929     return *d.begin();
0930 }
0931
0932
0933 template <typename T>
0934 inline typename QList<T>::iterator
0935 QList<T>::insert(qsizetype i, qsizetype n, parameter_type t)
0936 {
0937     Q_ASSERT_X(size_t(i) <= size_t(d->size), "QList<T>::insert", "index out of range");
0938     Q_ASSERT_X(n >= 0, "QList::insert", "invalid count");
0939     if (Q_LIKELY(n))
0940         d->insert(i, n, t);
0941     return begin() + i;
0942 }
0943
0944 template <typename T>
0945 template <typename ...Args>
0946 typename QList<T>::iterator
0947 QList<T>::emplace(qsizetype i, Args&&... args)
0948 {
0949     Q_ASSERT_X(i >= 0 && i <= d->size, "QList<T>::insert", "index out of range");
0950     d->emplace(i, std::forward<Args>(args)...);
0951     return begin() + i;
0952 }
0953
0954 template<typename T>
0955 template<typename... Args>
0956 inline typename QList<T>::reference QList<T>::emplaceBack(Args &&... args)
0957 {
0958     d->emplace(d->size, std::forward<Args>(args)...);
0959     return *(end() - 1);
0960 }
0961
0962 template <typename T>
0963 typename QList<T>::iterator QList<T>::erase(const_iterator abegin, const_iterator aend)
0964 {
0965     Q_ASSERT_X(isValidIterator(abegin), "QList::erase", "The specified iterator argument 'abegin' is invalid");
0966     Q_ASSERT_X(isValidIterator(aend), "QList::erase", "The specified iterator argument 'aend' is invalid");
0967     Q_ASSERT(aend >= abegin);
0968
0969     qsizetype i = std::distance(constBegin(), abegin);
0970     qsizetype n = std::distance(abegin, aend);
0971     remove(i, n);
0972
0973     return begin() + i;
0974 }
0975
0976 template <typename T>
0977 inline QList<T> &QList<T>::fill(parameter_type t, qsizetype newSize)
0978 {
0979     if (newSize == -1)
0980         newSize = size();
0981     if (d->needsDetach() || newSize > capacity()) {
0982         // must allocate memory
0983         DataPointer detached(d->detachCapacity(newSize));
0984         detached->copyAppend(newSize, t);
0985         d.swap(detached);
0986     } else {
0987         // we're detached
0988         const T copy(t);
0989         d->assign(d.begin(), d.begin() + qMin(size(), newSize), t);
0990         if (newSize > size()) {
0991             d->copyAppend(newSize - size(), copy);
0992         } else if (newSize < size()) {
0993             d->truncate(newSize);
0994         }
0995     }
0996     return *this;
0997 }
0998
0999 namespace QtPrivate {
1000 template <typename T, typename U>
1001 qsizetype indexOf(const QList<T> &vector, const U &u, qsizetype from) noexcept
1002 {
1003     if (from < 0)
1004         from = qMax(from + vector.size(), qsizetype(0));
1005     if (from < vector.size()) {
1006         auto n = vector.begin() + from - 1;
1007         auto e = vector.end();
1008         while (++n != e)
1009             if (*n == u)
1010                 return qsizetype(n - vector.begin());
1011     }
1012     return -1;
1013 }
1014
1015 template <typename T, typename U>
1016 qsizetype lastIndexOf(const QList<T> &vector, const U &u, qsizetype from) noexcept
1017 {
1018     if (from < 0)
1019         from += vector.d->size;
1020     else if (from >= vector.size())
1021         from = vector.size() - 1;
1022     if (from >= 0) {
1023         auto b = vector.begin();
1024         auto n = vector.begin() + from + 1;
1025         while (n != b) {
1026             if (*--n == u)
1027                 return qsizetype(n - b);
1028         }
1029     }
1030     return -1;
1031 }
1032 }
1033
1034 template <typename T>
1035 template <typename AT>
1036 qsizetype QListSpecialMethodsBase<T>::indexOf(const AT &t, qsizetype from) const noexcept
1037 {
1038     return QtPrivate::indexOf(*self(), t, from);
1039 }
1040
1041 template <typename T>
1042 template <typename AT>
1043 qsizetype QListSpecialMethodsBase<T>::lastIndexOf(const AT &t, qsizetype from) const noexcept
1044 {
1045     return QtPrivate::lastIndexOf(*self(), t, from);
1046 }
1047
1048 template <typename T>
1049 inline QList<T> QList<T>::mid(qsizetype pos, qsizetype len) const
1050 {
1051     qsizetype p = pos;
1052     qsizetype l = len;
1053     using namespace QtPrivate;
1054     switch (QContainerImplHelper::mid(d.size, &p, &l)) {
1055     case QContainerImplHelper::Null:
1056     case QContainerImplHelper::Empty:
1057         return QList();
1058     case QContainerImplHelper::Full:
1059         return *this;
1060     case QContainerImplHelper::Subset:
1061         break;
1062     }
1063
1064     // Allocate memory
1065     DataPointer copied(l);
1066     copied->copyAppend(data() + p, data() + p + l);
1067     return copied;
1068 }
1069
1070 Q_DECLARE_SEQUENTIAL_ITERATOR(List)
1071 Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(List)
1072
1073 template <typename T>
1074 size_t qHash(const QList<T> &key, size_t seed = 0)
1075     noexcept(noexcept(qHashRange(key.cbegin(), key.cend(), seed)))
1076 {
1077     return qHashRange(key.cbegin(), key.cend(), seed);
1078 }
1079
1080 template <typename T, typename AT>
1081 qsizetype erase(QList<T> &list, const AT &t)
1082 {
1083     return QtPrivate::sequential_erase(list, t);
1084 }
1085
1086 template <typename T, typename Predicate>
1087 qsizetype erase_if(QList<T> &list, Predicate pred)
1088 {
1089     return QtPrivate::sequential_erase_if(list, pred);
1090 }
1091
1092 // ### Qt 7 char32_t
1093 QList<uint> QStringView::toUcs4() const { return QtPrivate::convertToUcs4(*this); }
1094
1095 QT_END_NAMESPACE
1096
1097 #include <QtCore/qbytearraylist.h>
1098 #include <QtCore/qstringlist.h>
1099
1100 #endif // QLIST_H