Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2026-05-11 08:50:31 

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

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!