1// Copyright (C) 2020 The Qt Company Ltd.
2// Copyright (C) 2019 Intel Corporation
3// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR LGPL-3.0-only OR GPL-2.0-only OR GPL-3.0-only
4
5#ifndef QLIST_H
6#define QLIST_H
7
8#include <QtCore/qarraydatapointer.h>
9#include <QtCore/qcompare.h>
10#include <QtCore/qnamespace.h>
11#include <QtCore/qhashfunctions.h>
12#include <QtCore/qiterator.h>
13#include <QtCore/qcontainertools_impl.h>
14#include <QtCore/qnamespace.h>
15#include <QtCore/qttypetraits.h>
16
17#include <functional>
18#include <limits>
19#include <initializer_list>
20#include <type_traits>
21
22class tst_QList;
23
24QT_BEGIN_NAMESPACE
25
26namespace QtPrivate {
27 template <typename V, typename U> qsizetype indexOf(const QList<V> &list, const U &u, qsizetype from) noexcept;
28 template <typename V, typename U> qsizetype lastIndexOf(const QList<V> &list, const U &u, qsizetype from) noexcept;
29}
30
31template <typename T> struct QListSpecialMethodsBase
32{
33protected:
34 QListSpecialMethodsBase() = default;
35 QT_DECLARE_RO5_SMF_AS_DEFAULTED(QListSpecialMethodsBase)
36
37 using Self = QList<T>;
38 Self *self() { return static_cast<Self *>(this); }
39 const Self *self() const { return static_cast<const Self *>(this); }
40
41public:
42 template <typename AT = T>
43 qsizetype indexOf(const AT &t, qsizetype from = 0) const noexcept;
44 template <typename AT = T>
45 qsizetype lastIndexOf(const AT &t, qsizetype from = -1) const noexcept;
46
47 template <typename AT = T>
48 bool contains(const AT &t) const noexcept
49 {
50 return self()->indexOf(t) != -1;
51 }
52};
53template <typename T> struct QListSpecialMethods : QListSpecialMethodsBase<T>
54{
55protected:
56 QListSpecialMethods() = default;
57 QT_DECLARE_RO5_SMF_AS_DEFAULTED(QListSpecialMethods)
58
59public:
60 using QListSpecialMethodsBase<T>::indexOf;
61 using QListSpecialMethodsBase<T>::lastIndexOf;
62 using QListSpecialMethodsBase<T>::contains;
63};
64template <> struct QListSpecialMethods<QByteArray>;
65template <> struct QListSpecialMethods<QString>;
66
67#if !defined(QT_STRICT_QLIST_ITERATORS) && (QT_VERSION >= QT_VERSION_CHECK(6, 6, 0)) && !defined(Q_OS_WIN)
68#define QT_STRICT_QLIST_ITERATORS
69#endif
70
71#ifdef Q_QDOC // define QVector for QDoc
72template<typename T> class QVector : public QList<T> {};
73#endif
74
75template <typename T>
76class QList
77#ifndef Q_QDOC
78 : public QListSpecialMethods<T>
79#endif
80{
81 using Data = QTypedArrayData<T>;
82 using DataOps = QArrayDataOps<T>;
83 using DataPointer = QArrayDataPointer<T>;
84 class DisableRValueRefs {};
85
86 friend class ::tst_QList;
87
88 DataPointer d;
89
90 template <typename V, typename U> friend qsizetype QtPrivate::indexOf(const QList<V> &list, const U &u, qsizetype from) noexcept;
91 template <typename V, typename U> friend qsizetype QtPrivate::lastIndexOf(const QList<V> &list, const U &u, qsizetype from) noexcept;
92 // This alias prevents the QtPrivate namespace from being exposed into the docs.
93 template <typename InputIterator>
94 using if_input_iterator = QtPrivate::IfIsInputIterator<InputIterator>;
95
96public:
97 using Type = T;
98 using value_type = T;
99 using pointer = T *;
100 using const_pointer = const T *;
101 using reference = T &;
102 using const_reference = const T &;
103 using size_type = qsizetype;
104 using difference_type = qptrdiff;
105#ifndef Q_QDOC
106 using parameter_type = typename DataPointer::parameter_type;
107 using rvalue_ref = typename std::conditional<DataPointer::pass_parameter_by_value, DisableRValueRefs, T &&>::type;
108#else // simplified aliases for QDoc
109 using parameter_type = const T &;
110 using rvalue_ref = T &&;
111#endif
112
113 DataPointer &data_ptr() & { return d; }
114 const DataPointer &data_ptr() const & { return d; }
115 DataPointer &&data_ptr() && { return std::move(d); }
116 // No current use-case for a `const &&` overload
117
118 class const_iterator;
119 class iterator {
120 friend class QList<T>;
121 friend class const_iterator;
122 T *i = nullptr;
123#ifdef QT_STRICT_QLIST_ITERATORS
124 inline constexpr explicit iterator(T *n) : i(n) {}
125#endif
126
127 public:
128 using difference_type = qsizetype;
129 using value_type = T;
130#ifdef QT_COMPILER_HAS_LWG3346
131 using iterator_concept = std::contiguous_iterator_tag;
132#endif
133 using element_type = value_type;
134 using iterator_category = std::random_access_iterator_tag;
135 using pointer = T *;
136 using reference = T &;
137
138 inline constexpr iterator() = default;
139#ifndef QT_STRICT_QLIST_ITERATORS
140 inline constexpr explicit iterator(T *n) : i(n) {}
141#endif
142 inline T &operator*() const { return *i; }
143 inline T *operator->() const { return i; }
144 inline T &operator[](qsizetype j) const { return *(i + j); }
145#ifdef __cpp_lib_three_way_comparison
146 friend constexpr auto operator<=>(iterator, iterator) noexcept = default;
147 friend constexpr bool operator==(iterator, iterator) noexcept = default;
148#else
149 inline constexpr bool operator==(iterator o) const { return i == o.i; }
150 inline constexpr bool operator!=(iterator o) const { return i != o.i; }
151 inline constexpr bool operator<(iterator other) const { return i < other.i; }
152 inline constexpr bool operator<=(iterator other) const { return i <= other.i; }
153 inline constexpr bool operator>(iterator other) const { return i > other.i; }
154 inline constexpr bool operator>=(iterator other) const { return i >= other.i; }
155 inline constexpr bool operator==(const_iterator o) const { return i == o.i; }
156 inline constexpr bool operator!=(const_iterator o) const { return i != o.i; }
157 inline constexpr bool operator<(const_iterator other) const { return i < other.i; }
158 inline constexpr bool operator<=(const_iterator other) const { return i <= other.i; }
159 inline constexpr bool operator>(const_iterator other) const { return i > other.i; }
160 inline constexpr bool operator>=(const_iterator other) const { return i >= other.i; }
161#endif // __cpp_lib_three_way_comparison
162 inline constexpr bool operator==(pointer p) const { return i == p; }
163 inline constexpr bool operator!=(pointer p) const { return i != p; }
164 inline iterator &operator++() { ++i; return *this; }
165 inline iterator operator++(int) { auto copy = *this; ++*this; return copy; }
166 inline iterator &operator--() { --i; return *this; }
167 inline iterator operator--(int) { auto copy = *this; --*this; return copy; }
168 inline qsizetype operator-(iterator j) const { return i - j.i; }
169#if QT_DEPRECATED_SINCE(6, 3) && !defined(QT_STRICT_QLIST_ITERATORS)
170 QT_DEPRECATED_VERSION_X_6_3("Use operator* or operator-> rather than relying on "
171 "the implicit conversion between a QList/QVector::iterator "
172 "and a raw pointer")
173 inline operator T*() const { return i; }
174
175 template <typename Int> std::enable_if_t<std::is_integral_v<Int>, iterator>
176 &operator+=(Int j) { i+=j; return *this; }
177 template <typename Int> std::enable_if_t<std::is_integral_v<Int>, iterator>
178 &operator-=(Int j) { i-=j; return *this; }
179 template <typename Int> std::enable_if_t<std::is_integral_v<Int>, iterator>
180 operator+(Int j) const { return iterator(i+j); }
181 template <typename Int> std::enable_if_t<std::is_integral_v<Int>, iterator>
182 operator-(Int j) const { return iterator(i-j); }
183 template <typename Int> friend std::enable_if_t<std::is_integral_v<Int>, iterator>
184 operator+(Int j, iterator k) { return k + j; }
185#else
186 inline iterator &operator+=(qsizetype j) { i += j; return *this; }
187 inline iterator &operator-=(qsizetype j) { i -= j; return *this; }
188 inline iterator operator+(qsizetype j) const { return iterator(i + j); }
189 inline iterator operator-(qsizetype j) const { return iterator(i - j); }
190 friend inline iterator operator+(qsizetype j, iterator k) { return k + j; }
191#endif
192 };
193
194 class const_iterator {
195 friend class QList<T>;
196 friend class iterator;
197 const T *i = nullptr;
198#ifdef QT_STRICT_QLIST_ITERATORS
199 inline constexpr explicit const_iterator(const T *n) : i(n) {}
200#endif
201
202 public:
203 using difference_type = qsizetype;
204 using value_type = T;
205#ifdef QT_COMPILER_HAS_LWG3346
206 using iterator_concept = std::contiguous_iterator_tag;
207#endif
208 using element_type = const value_type;
209 using iterator_category = std::random_access_iterator_tag;
210 using pointer = const T *;
211 using reference = const T &;
212
213 inline constexpr const_iterator() = default;
214#ifndef QT_STRICT_QLIST_ITERATORS
215 inline constexpr explicit const_iterator(const T *n) : i(n) {}
216#endif
217 inline constexpr const_iterator(iterator o): i(o.i) {}
218 inline const T &operator*() const { return *i; }
219 inline const T *operator->() const { return i; }
220 inline const T &operator[](qsizetype j) const { return *(i + j); }
221#ifdef __cpp_lib_three_way_comparison
222 friend constexpr auto operator<=>(const_iterator, const_iterator) noexcept = default;
223 friend constexpr auto operator<=>(const_iterator a, iterator b) noexcept
224 { return a <=> const_iterator(b); }
225 friend constexpr bool operator==(const_iterator, const_iterator) noexcept = default;
226 friend constexpr bool operator==(const_iterator a, iterator b) noexcept
227 { return a == const_iterator(b); }
228#else
229 inline constexpr bool operator==(const_iterator o) const { return i == o.i; }
230 inline constexpr bool operator!=(const_iterator o) const { return i != o.i; }
231 inline constexpr bool operator<(const_iterator other) const { return i < other.i; }
232 inline constexpr bool operator<=(const_iterator other) const { return i <= other.i; }
233 inline constexpr bool operator>(const_iterator other) const { return i > other.i; }
234 inline constexpr bool operator>=(const_iterator other) const { return i >= other.i; }
235 inline constexpr bool operator==(iterator o) const { return i == o.i; }
236 inline constexpr bool operator!=(iterator o) const { return i != o.i; }
237 inline constexpr bool operator<(iterator other) const { return i < other.i; }
238 inline constexpr bool operator<=(iterator other) const { return i <= other.i; }
239 inline constexpr bool operator>(iterator other) const { return i > other.i; }
240 inline constexpr bool operator>=(iterator other) const { return i >= other.i; }
241#endif // __cpp_lib_three_way_comparison
242 inline constexpr bool operator==(pointer p) const { return i == p; }
243 inline constexpr bool operator!=(pointer p) const { return i != p; }
244 inline const_iterator &operator++() { ++i; return *this; }
245 inline const_iterator operator++(int) { auto copy = *this; ++*this; return copy; }
246 inline const_iterator &operator--() { --i; return *this; }
247 inline const_iterator operator--(int) { auto copy = *this; --*this; return copy; }
248 inline qsizetype operator-(const_iterator j) const { return i - j.i; }
249#if QT_DEPRECATED_SINCE(6, 3) && !defined(QT_STRICT_QLIST_ITERATORS)
250 QT_DEPRECATED_VERSION_X_6_3("Use operator* or operator-> rather than relying on "
251 "the implicit conversion between a QList/QVector::const_iterator "
252 "and a raw pointer")
253 inline operator const T*() const { return i; }
254
255 template <typename Int> std::enable_if_t<std::is_integral_v<Int>, const_iterator>
256 &operator+=(Int j) { i+=j; return *this; }
257 template <typename Int> std::enable_if_t<std::is_integral_v<Int>, const_iterator>
258 &operator-=(Int j) { i-=j; return *this; }
259 template <typename Int> std::enable_if_t<std::is_integral_v<Int>, const_iterator>
260 operator+(Int j) const { return const_iterator(i+j); }
261 template <typename Int> std::enable_if_t<std::is_integral_v<Int>, const_iterator>
262 operator-(Int j) const { return const_iterator(i-j); }
263 template <typename Int> friend std::enable_if_t<std::is_integral_v<Int>, const_iterator>
264 operator+(Int j, const_iterator k) { return k + j; }
265#else
266 inline const_iterator &operator+=(qsizetype j) { i += j; return *this; }
267 inline const_iterator &operator-=(qsizetype j) { i -= j; return *this; }
268 inline const_iterator operator+(qsizetype j) const { return const_iterator(i + j); }
269 inline const_iterator operator-(qsizetype j) const { return const_iterator(i - j); }
270 friend inline const_iterator operator+(qsizetype j, const_iterator k) { return k + j; }
271#endif
272 };
273 using Iterator = iterator;
274 using ConstIterator = const_iterator;
275 using reverse_iterator = std::reverse_iterator<iterator>;
276 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
277
278private:
279 void resize_internal(qsizetype i);
280 bool isValidIterator(const_iterator i) const
281 {
282 const std::less<const T*> less = {};
283 return !less(d->end(), i.i) && !less(i.i, d->begin());
284 }
285
286 void verify([[maybe_unused]] qsizetype pos = 0, [[maybe_unused]] qsizetype n = 1) const
287 {
288 Q_ASSERT(pos >= 0);
289 Q_ASSERT(pos <= size());
290 Q_ASSERT(n >= 0);
291 Q_ASSERT(n <= size() - pos);
292 }
293public:
294 QList(DataPointer dd) noexcept
295 : d(dd)
296 {
297 }
298
299public:
300 constexpr QList() noexcept = default;
301 explicit QList(qsizetype size)
302 : d(size)
303 {
304 if (size)
305 d->appendInitialize(size);
306 }
307 QList(qsizetype size, parameter_type t)
308 : d(size)
309 {
310 if (size)
311 d->copyAppend(size, t);
312 }
313
314 inline QList(std::initializer_list<T> args)
315 : d(qsizetype(args.size()))
316 {
317 if (args.size())
318 d->copyAppend(args.begin(), args.end());
319 }
320
321 QList<T> &operator=(std::initializer_list<T> args)
322 {
323 return assign(args);
324 }
325
326 template <typename InputIterator, if_input_iterator<InputIterator> = true>
327 QList(InputIterator i1, InputIterator i2)
328 {
329 if constexpr (!std::is_convertible_v<typename std::iterator_traits<InputIterator>::iterator_category, std::forward_iterator_tag>) {
330 std::copy(i1, i2, std::back_inserter(*this));
331 } else {
332 const auto distance = std::distance(i1, i2);
333 if (distance) {
334 d = DataPointer(qsizetype(distance));
335 // appendIteratorRange can deal with contiguous iterators on its own,
336 // this is an optimization for C++17 code.
337 if constexpr (std::is_same_v<std::decay_t<InputIterator>, iterator> ||
338 std::is_same_v<std::decay_t<InputIterator>, const_iterator>) {
339 d->copyAppend(i1.i, i2.i);
340 } else {
341 d->appendIteratorRange(i1, i2);
342 }
343 }
344 }
345 }
346
347 // This constructor is here for compatibility with QStringList in Qt 5, that has a QStringList(const QString &) constructor
348 template<typename String, typename = std::enable_if_t<std::is_same_v<T, QString> && std::is_convertible_v<String, QString>>>
349 inline explicit QList(const String &str)
350 { append(str); }
351
352 QList(qsizetype size, Qt::Initialization)
353 : d(size)
354 {
355 if (size)
356 d->appendUninitialized(size);
357 }
358
359 // compiler-generated special member functions are fine!
360
361 void swap(QList &other) noexcept { d.swap(other.d); }
362
363#ifndef Q_QDOC
364private:
365 template <typename U = T,
366 Qt::if_has_qt_compare_three_way<U, U> = true>
367 friend auto compareThreeWay(const QList &lhs, const QList &rhs)
368 {
369 return QtOrderingPrivate::lexicographicalCompareThreeWay(lhs.begin(), lhs.end(),
370 rhs.begin(), rhs.end());
371 }
372
373#if defined(__cpp_lib_three_way_comparison) && defined(__cpp_lib_concepts)
374 template <typename U = T,
375 QtOrderingPrivate::if_has_op_less_or_op_compare_three_way<QList, U> = true>
376 friend auto operator<=>(const QList &lhs, const QList &rhs)
377 {
378 return std::lexicographical_compare_three_way(lhs.begin(), lhs.end(),
379 rhs.begin(), rhs.end(),
380 QtOrderingPrivate::synthThreeWay);
381 }
382#endif // __cpp_lib_three_way_comparison && __cpp_lib_concepts
383
384public:
385 template <typename U = T>
386 QTypeTraits::compare_eq_result_container<QList, U> operator==(const QList &other) const
387 {
388 if (size() != other.size())
389 return false;
390 if (begin() == other.begin())
391 return true;
392
393 // do element-by-element comparison
394 return std::equal(begin(), end(), other.begin(), other.end());
395 }
396
397 template <typename U = T>
398 QTypeTraits::compare_eq_result_container<QList, U> operator!=(const QList &other) const
399 {
400 return !(*this == other);
401 }
402
403#ifndef __cpp_lib_three_way_comparison
404 template <typename U = T>
405 QTypeTraits::compare_lt_result_container<QList, U> operator<(const QList &other) const
406 noexcept(noexcept(std::lexicographical_compare<typename QList<U>::const_iterator,
407 typename QList::const_iterator>(
408 std::declval<QList<U>>().begin(), std::declval<QList<U>>().end(),
409 other.begin(), other.end())))
410 {
411 return std::lexicographical_compare(begin(), end(),
412 other.begin(), other.end());
413 }
414
415 template <typename U = T>
416 QTypeTraits::compare_lt_result_container<QList, U> operator>(const QList &other) const
417 noexcept(noexcept(other < std::declval<QList<U>>()))
418 {
419 return other < *this;
420 }
421
422 template <typename U = T>
423 QTypeTraits::compare_lt_result_container<QList, U> operator<=(const QList &other) const
424 noexcept(noexcept(other < std::declval<QList<U>>()))
425 {
426 return !(other < *this);
427 }
428
429 template <typename U = T>
430 QTypeTraits::compare_lt_result_container<QList, U> operator>=(const QList &other) const
431 noexcept(noexcept(std::declval<QList<U>>() < other))
432 {
433 return !(*this < other);
434 }
435#endif // __cpp_lib_three_way_comparison
436#else
437 bool operator==(const QList &other) const;
438 bool operator!=(const QList &other) const;
439 bool operator<(const QList &other) const;
440 bool operator>(const QList &other) const;
441 bool operator<=(const QList &other) const;
442 bool operator>=(const QList &other) const;
443 friend auto operator<=>(const QList &lhs, const QList &rhs);
444#endif // Q_QDOC
445
446 static constexpr qsizetype maxSize() { return Data::maxSize(); }
447 constexpr qsizetype size() const noexcept
448 {
449#if __has_cpp_attribute(assume)
450 constexpr size_t MaxSize = maxSize();
451 [[assume(size_t(d.size) <= MaxSize)]];
452#endif
453 return d.size;
454 }
455 constexpr qsizetype count() const noexcept { return size(); }
456 constexpr qsizetype length() const noexcept { return size(); }
457
458 constexpr bool isEmpty() const noexcept { return size() == 0; }
459
460 void resize(qsizetype size)
461 {
462 resize_internal(i: size);
463 if (size > this->size())
464 d->appendInitialize(size);
465 }
466 void resize(qsizetype size, parameter_type c)
467 {
468 resize_internal(i: size);
469 if (size > this->size())
470 d->copyAppend(size - this->size(), c);
471 }
472 void resizeForOverwrite(qsizetype size)
473 {
474 resize_internal(i: size);
475 if (size > this->size())
476 d->appendUninitialized(size);
477 }
478
479 inline qsizetype capacity() const { return qsizetype(d->constAllocatedCapacity()); }
480 void reserve(qsizetype size);
481 inline void squeeze();
482
483 void detach() { d.detach(); }
484 bool isDetached() const noexcept { return !d->isShared(); }
485
486 inline bool isSharedWith(const QList<T> &other) const { return d == other.d; }
487
488 pointer data() { detach(); return d->data(); }
489 const_pointer data() const noexcept { return d->data(); }
490 const_pointer constData() const noexcept { return d->data(); }
491 void clear() {
492 if (!size())
493 return;
494 if (d->needsDetach()) {
495 // must allocate memory
496 DataPointer detached(d.allocatedCapacity());
497 d.swap(detached);
498 } else {
499 d->truncate(0);
500 }
501 }
502
503 const_reference at(qsizetype i) const noexcept
504 {
505 Q_ASSERT_X(size_t(i) < size_t(d->size), "QList::at", "index out of range");
506 return data()[i];
507 }
508 reference operator[](qsizetype i)
509 {
510 Q_ASSERT_X(size_t(i) < size_t(d->size), "QList::operator[]", "index out of range");
511 // don't detach() here, we detach in data below:
512 return data()[i];
513 }
514 const_reference operator[](qsizetype i) const noexcept { return at(i); }
515 void append(parameter_type t) { emplaceBack(t); }
516 void append(const_iterator i1, const_iterator i2);
517 void append(rvalue_ref t)
518 {
519 if constexpr (DataPointer::pass_parameter_by_value) {
520 Q_UNUSED(t);
521 } else {
522 emplaceBack(std::move(t));
523 }
524 }
525 void append(const QList<T> &l)
526 {
527 append(l.constBegin(), l.constEnd());
528 }
529 void append(QList<T> &&l);
530 void prepend(rvalue_ref t) {
531 if constexpr (DataPointer::pass_parameter_by_value) {
532 Q_UNUSED(t);
533 } else {
534 emplaceFront(std::move(t));
535 }
536 }
537 void prepend(parameter_type t) { emplaceFront(t); }
538
539 template<typename... Args>
540 inline reference emplaceBack(Args &&... args);
541
542 template <typename ...Args>
543 inline reference emplaceFront(Args&&... args);
544
545 iterator insert(qsizetype i, parameter_type t)
546 { return emplace(i, t); }
547 iterator insert(qsizetype i, qsizetype n, parameter_type t);
548 iterator insert(const_iterator before, parameter_type t)
549 {
550 Q_ASSERT_X(isValidIterator(before), "QList::insert", "The specified iterator argument 'before' is invalid");
551 return insert(before, 1, t);
552 }
553 iterator insert(const_iterator before, qsizetype n, parameter_type t)
554 {
555 Q_ASSERT_X(isValidIterator(before), "QList::insert", "The specified iterator argument 'before' is invalid");
556 return insert(std::distance(constBegin(), before), n, t);
557 }
558 iterator insert(const_iterator before, rvalue_ref t)
559 {
560 Q_ASSERT_X(isValidIterator(before), "QList::insert", "The specified iterator argument 'before' is invalid");
561 return insert(std::distance(constBegin(), before), std::move(t));
562 }
563 iterator insert(qsizetype i, rvalue_ref t) {
564 if constexpr (DataPointer::pass_parameter_by_value) {
565 Q_UNUSED(i);
566 Q_UNUSED(t);
567 return end();
568 } else {
569 return emplace(i, std::move(t));
570 }
571 }
572
573 QList &assign(qsizetype n, parameter_type t)
574 {
575 Q_ASSERT(n >= 0);
576 return fill(t, size: n);
577 }
578
579 template <typename InputIterator, if_input_iterator<InputIterator> = true>
580 QList &assign(InputIterator first, InputIterator last)
581 { d.assign(first, last); return *this; }
582
583 QList &assign(std::initializer_list<T> l)
584 { return assign(l.begin(), l.end()); }
585
586 template <typename ...Args>
587 iterator emplace(const_iterator before, Args&&... args)
588 {
589 Q_ASSERT_X(isValidIterator(before), "QList::emplace", "The specified iterator argument 'before' is invalid");
590 return emplace(std::distance(constBegin(), before), std::forward<Args>(args)...);
591 }
592
593 template <typename ...Args>
594 iterator emplace(qsizetype i, Args&&... args);
595#if 0
596 template< class InputIt >
597 iterator insert( const_iterator pos, InputIt first, InputIt last );
598 iterator insert( const_iterator pos, std::initializer_list<T> ilist );
599#endif
600 void replace(qsizetype i, parameter_type t)
601 {
602 Q_ASSERT_X(i >= 0 && i < d->size, "QList<T>::replace", "index out of range");
603 DataPointer oldData;
604 d.detach(&oldData);
605 d.data()[i] = t;
606 }
607 void replace(qsizetype i, rvalue_ref t)
608 {
609 if constexpr (DataPointer::pass_parameter_by_value) {
610 Q_UNUSED(i);
611 Q_UNUSED(t);
612 } else {
613 Q_ASSERT_X(i >= 0 && i < d->size, "QList<T>::replace", "index out of range");
614 DataPointer oldData;
615 d.detach(&oldData);
616 d.data()[i] = std::move(t);
617 }
618 }
619
620 void remove(qsizetype i, qsizetype n = 1);
621 void removeFirst() noexcept;
622 void removeLast() noexcept;
623 value_type takeFirst() { Q_ASSERT(!isEmpty()); value_type v = std::move(first()); d->eraseFirst(); return v; }
624 value_type takeLast() { Q_ASSERT(!isEmpty()); value_type v = std::move(last()); d->eraseLast(); return v; }
625
626 QList<T> &fill(parameter_type t, qsizetype size = -1);
627
628#ifndef Q_QDOC
629 using QListSpecialMethods<T>::contains;
630 using QListSpecialMethods<T>::indexOf;
631 using QListSpecialMethods<T>::lastIndexOf;
632#else
633 template <typename AT>
634 qsizetype indexOf(const AT &t, qsizetype from = 0) const noexcept;
635 template <typename AT>
636 qsizetype lastIndexOf(const AT &t, qsizetype from = -1) const noexcept;
637 template <typename AT>
638 bool contains(const AT &t) const noexcept;
639#endif
640
641 template <typename AT = T>
642 qsizetype count(const AT &t) const noexcept
643 {
644 return qsizetype(std::count(data(), data() + size(), t));
645 }
646
647 void removeAt(qsizetype i) { remove(i); }
648 template <typename AT = T>
649 qsizetype removeAll(const AT &t)
650 {
651 return QtPrivate::sequential_erase_with_copy(*this, t);
652 }
653
654 template <typename AT = T>
655 bool removeOne(const AT &t)
656 {
657 return QtPrivate::sequential_erase_one(*this, t);
658 }
659
660 template <typename Predicate>
661 qsizetype removeIf(Predicate pred)
662 {
663 return QtPrivate::sequential_erase_if(*this, pred);
664 }
665
666 T takeAt(qsizetype i) { T t = std::move((*this)[i]); remove(i); return t; }
667 void move(qsizetype from, qsizetype to)
668 {
669 Q_ASSERT_X(from >= 0 && from < size(), "QList::move(qsizetype, qsizetype)", "'from' is out-of-range");
670 Q_ASSERT_X(to >= 0 && to < size(), "QList::move(qsizetype, qsizetype)", "'to' is out-of-range");
671 if (from == to) // don't detach when no-op
672 return;
673 detach();
674 T * const b = d->begin();
675 if (from < to)
676 std::rotate(b + from, b + from + 1, b + to + 1);
677 else
678 std::rotate(b + to, b + from, b + from + 1);
679 }
680
681 // STL-style
682 iterator begin() { detach(); return iterator(d->begin()); }
683 iterator end() { detach(); return iterator(d->end()); }
684
685 const_iterator begin() const noexcept { return const_iterator(d->constBegin()); }
686 const_iterator end() const noexcept { return const_iterator(d->constEnd()); }
687 const_iterator cbegin() const noexcept { return const_iterator(d->constBegin()); }
688 const_iterator cend() const noexcept { return const_iterator(d->constEnd()); }
689 const_iterator constBegin() const noexcept { return const_iterator(d->constBegin()); }
690 const_iterator constEnd() const noexcept { return const_iterator(d->constEnd()); }
691 reverse_iterator rbegin() { return reverse_iterator(end()); }
692 reverse_iterator rend() { return reverse_iterator(begin()); }
693 const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
694 const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }
695 const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(end()); }
696 const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); }
697
698 iterator erase(const_iterator begin, const_iterator end);
699 inline iterator erase(const_iterator pos) { return erase(pos, pos+1); }
700
701 // more Qt
702 inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); }
703 inline const T &first() const noexcept { Q_ASSERT(!isEmpty()); return *begin(); }
704 inline const T &constFirst() const noexcept { Q_ASSERT(!isEmpty()); return *begin(); }
705 inline T& last() { Q_ASSERT(!isEmpty()); return *(end()-1); }
706 inline const T &last() const noexcept { Q_ASSERT(!isEmpty()); return *(end()-1); }
707 inline const T &constLast() const noexcept { Q_ASSERT(!isEmpty()); return *(end()-1); }
708 inline bool startsWith(parameter_type t) const { return !isEmpty() && first() == t; }
709 inline bool endsWith(parameter_type t) const { return !isEmpty() && last() == t; }
710 QList<T> mid(qsizetype pos, qsizetype len = -1) const;
711
712 QList<T> first(qsizetype n) const
713 { verify(pos: 0, n); return QList<T>(begin(), begin() + n); }
714 QList<T> last(qsizetype n) const
715 { verify(pos: 0, n); return QList<T>(end() - n, end()); }
716 QList<T> sliced(qsizetype pos) const
717 { verify(pos, n: 0); return QList<T>(begin() + pos, end()); }
718 QList<T> sliced(qsizetype pos, qsizetype n) const
719 { verify(pos, n); return QList<T>(begin() + pos, begin() + pos + n); }
720
721 T value(qsizetype i) const { return value(i, T()); }
722 T value(qsizetype i, parameter_type defaultValue) const;
723
724 void swapItemsAt(qsizetype i, qsizetype j) {
725 Q_ASSERT_X(i >= 0 && i < size() && j >= 0 && j < size(),
726 "QList<T>::swap", "index out of range");
727 detach();
728 qSwap(d->begin()[i], d->begin()[j]);
729 }
730
731 // STL compatibility
732 inline void push_back(parameter_type t) { append(t); }
733 void push_back(rvalue_ref t) { append(std::move(t)); }
734 void push_front(rvalue_ref t) { prepend(std::move(t)); }
735 inline void push_front(parameter_type t) { prepend(t); }
736 void pop_back() noexcept { removeLast(); }
737 void pop_front() noexcept { removeFirst(); }
738
739 template <typename ...Args>
740 reference emplace_back(Args&&... args) { return emplaceBack(std::forward<Args>(args)...); }
741
742 inline bool empty() const noexcept
743 { return d->size == 0; }
744 inline reference front() { return first(); }
745 inline const_reference front() const noexcept { return first(); }
746 inline reference back() { return last(); }
747 inline const_reference back() const noexcept { return last(); }
748 void shrink_to_fit() { squeeze(); }
749 constexpr qsizetype max_size() const noexcept
750 {
751 return maxSize();
752 }
753
754 // comfort
755 QList<T> &operator+=(const QList<T> &l) { append(l); return *this; }
756 QList<T> &operator+=(QList<T> &&l) { append(std::move(l)); return *this; }
757 inline QList<T> operator+(const QList<T> &l) const &
758 { QList n = *this; n += l; return n; }
759 QList<T> operator+(const QList<T> &l) &&
760 { return std::move(*this += l); }
761 inline QList<T> operator+(QList<T> &&l) const &
762 { QList n = *this; n += std::move(l); return n; }
763 QList<T> operator+(QList<T> &&l) &&
764 { return std::move(*this += std::move(l)); }
765 inline QList<T> &operator+=(parameter_type t)
766 { append(t); return *this; }
767 inline QList<T> &operator<< (parameter_type t)
768 { append(t); return *this; }
769 inline QList<T> &operator<<(const QList<T> &l)
770 { *this += l; return *this; }
771 inline QList<T> &operator<<(QList<T> &&l)
772 { *this += std::move(l); return *this; }
773 inline QList<T> &operator+=(rvalue_ref t)
774 { append(std::move(t)); return *this; }
775 inline QList<T> &operator<<(rvalue_ref t)
776 { append(std::move(t)); return *this; }
777
778 // Consider deprecating in 6.4 or later
779 static QList<T> fromList(const QList<T> &list) noexcept { return list; }
780 QList<T> toList() const noexcept { return *this; }
781
782 static inline QList<T> fromVector(const QList<T> &vector) noexcept { return vector; }
783 inline QList<T> toVector() const noexcept { return *this; }
784
785 template<qsizetype N>
786 static QList<T> fromReadOnlyData(const T (&t)[N]) noexcept
787 {
788 return QList<T>({ nullptr, const_cast<T *>(t), N });
789 }
790};
791
792template <typename InputIterator,
793 typename ValueType = typename std::iterator_traits<InputIterator>::value_type,
794 QtPrivate::IfIsInputIterator<InputIterator> = true>
795QList(InputIterator, InputIterator) -> QList<ValueType>;
796
797template <typename T>
798inline void QList<T>::resize_internal(qsizetype newSize)
799{
800 Q_ASSERT(newSize >= 0);
801
802 if (d->needsDetach() || newSize > capacity() - d.freeSpaceAtBegin()) {
803 d.detachAndGrow(QArrayData::GrowsAtEnd, newSize - d.size, nullptr, nullptr);
804 } else if (newSize < size()) {
805 d->truncate(newSize);
806 }
807}
808
809template <typename T>
810void QList<T>::reserve(qsizetype asize)
811{
812 // capacity() == 0 for immutable data, so this will force a detaching below
813 if (asize <= capacity() - d.freeSpaceAtBegin()) {
814 if (d->flags() & Data::CapacityReserved)
815 return; // already reserved, don't shrink
816 if (!d->isShared()) {
817 // accept current allocation, don't shrink
818 d->setFlag(Data::CapacityReserved);
819 return;
820 }
821 }
822
823 DataPointer detached(qMax(asize, size()));
824 detached->copyAppend(d->begin(), d->end());
825 if (detached.d_ptr())
826 detached->setFlag(Data::CapacityReserved);
827 d.swap(detached);
828}
829
830template <typename T>
831inline void QList<T>::squeeze()
832{
833 if (!d.isMutable())
834 return;
835 if (d->needsDetach() || size() < capacity()) {
836 // must allocate memory
837 DataPointer detached(size());
838 if (size()) {
839 if (d.needsDetach())
840 detached->copyAppend(d.data(), d.data() + d.size);
841 else
842 detached->moveAppend(d.data(), d.data() + d.size);
843 }
844 d.swap(detached);
845 }
846 // We're detached so this is fine
847 d->clearFlag(Data::CapacityReserved);
848}
849
850template <typename T>
851inline void QList<T>::remove(qsizetype i, qsizetype n)
852{
853 Q_ASSERT_X(size_t(i) + size_t(n) <= size_t(d->size), "QList::remove", "index out of range");
854 Q_ASSERT_X(n >= 0, "QList::remove", "invalid count");
855
856 if (n == 0)
857 return;
858
859 d.detach();
860 d->erase(d->begin() + i, n);
861}
862
863template <typename T>
864inline void QList<T>::removeFirst() noexcept
865{
866 Q_ASSERT(!isEmpty());
867 d.detach();
868 d->eraseFirst();
869}
870
871template <typename T>
872inline void QList<T>::removeLast() noexcept
873{
874 Q_ASSERT(!isEmpty());
875 d.detach();
876 d->eraseLast();
877}
878
879
880template<typename T>
881inline T QList<T>::value(qsizetype i, parameter_type defaultValue) const
882{
883 return size_t(i) < size_t(d->size) ? at(i) : defaultValue;
884}
885
886template <typename T>
887inline void QList<T>::append(const_iterator i1, const_iterator i2)
888{
889 d->growAppend(i1.i, i2.i);
890}
891
892template <typename T>
893inline void QList<T>::append(QList<T> &&other)
894{
895 Q_ASSERT(&other != this);
896 if (other.isEmpty())
897 return;
898 if (other.d->needsDetach() || !std::is_nothrow_move_constructible_v<T>)
899 return append(other);
900
901 // due to precondition &other != this, we can unconditionally modify 'this'
902 d.detachAndGrow(QArrayData::GrowsAtEnd, other.size(), nullptr, nullptr);
903 Q_ASSERT(d.freeSpaceAtEnd() >= other.size());
904 d->moveAppend(other.d->begin(), other.d->end());
905}
906
907template<typename T>
908template<typename... Args>
909inline typename QList<T>::reference QList<T>::emplaceFront(Args &&... args)
910{
911 d->emplace(0, std::forward<Args>(args)...);
912 return *d.begin();
913}
914
915
916template <typename T>
917inline typename QList<T>::iterator
918QList<T>::insert(qsizetype i, qsizetype n, parameter_type t)
919{
920 Q_ASSERT_X(size_t(i) <= size_t(d->size), "QList<T>::insert", "index out of range");
921 Q_ASSERT_X(n >= 0, "QList::insert", "invalid count");
922 if (Q_LIKELY(n))
923 d->insert(i, n, t);
924 return begin() + i;
925}
926
927template <typename T>
928template <typename ...Args>
929typename QList<T>::iterator
930QList<T>::emplace(qsizetype i, Args&&... args)
931{
932 Q_ASSERT_X(i >= 0 && i <= d->size, "QList<T>::insert", "index out of range");
933 d->emplace(i, std::forward<Args>(args)...);
934 return begin() + i;
935}
936
937template<typename T>
938template<typename... Args>
939inline typename QList<T>::reference QList<T>::emplaceBack(Args &&... args)
940{
941 d->emplace(d->size, std::forward<Args>(args)...);
942 return *(end() - 1);
943}
944
945template <typename T>
946typename QList<T>::iterator QList<T>::erase(const_iterator abegin, const_iterator aend)
947{
948 Q_ASSERT_X(isValidIterator(abegin), "QList::erase", "The specified iterator argument 'abegin' is invalid");
949 Q_ASSERT_X(isValidIterator(aend), "QList::erase", "The specified iterator argument 'aend' is invalid");
950 Q_ASSERT(aend >= abegin);
951
952 qsizetype i = std::distance(constBegin(), abegin);
953 qsizetype n = std::distance(abegin, aend);
954 remove(i, n);
955
956 return begin() + i;
957}
958
959template <typename T>
960inline QList<T> &QList<T>::fill(parameter_type t, qsizetype newSize)
961{
962 if (newSize == -1)
963 newSize = size();
964 if (d->needsDetach() || newSize > capacity()) {
965 // must allocate memory
966 DataPointer detached(d->detachCapacity(newSize));
967 detached->copyAppend(newSize, t);
968 d.swap(detached);
969 } else {
970 // we're detached
971 const T copy(t);
972 d->assign(d.begin(), d.begin() + qMin(size(), newSize), t);
973 if (newSize > size()) {
974 d->copyAppend(newSize - size(), copy);
975 } else if (newSize < size()) {
976 d->truncate(newSize);
977 }
978 }
979 return *this;
980}
981
982namespace QtPrivate {
983template <typename T, typename U>
984qsizetype indexOf(const QList<T> &vector, const U &u, qsizetype from) noexcept
985{
986 if (from < 0)
987 from = qMax(from + vector.size(), qsizetype(0));
988 if (from < vector.size()) {
989 auto n = vector.begin() + from - 1;
990 auto e = vector.end();
991 while (++n != e)
992 if (*n == u)
993 return qsizetype(n - vector.begin());
994 }
995 return -1;
996}
997
998template <typename T, typename U>
999qsizetype lastIndexOf(const QList<T> &vector, const U &u, qsizetype from) noexcept
1000{
1001 if (from < 0)
1002 from += vector.d->size;
1003 else if (from >= vector.size())
1004 from = vector.size() - 1;
1005 if (from >= 0) {
1006 auto b = vector.begin();
1007 auto n = vector.begin() + from + 1;
1008 while (n != b) {
1009 if (*--n == u)
1010 return qsizetype(n - b);
1011 }
1012 }
1013 return -1;
1014}
1015}
1016
1017template <typename T>
1018template <typename AT>
1019qsizetype QListSpecialMethodsBase<T>::indexOf(const AT &t, qsizetype from) const noexcept
1020{
1021 return QtPrivate::indexOf(*self(), t, from);
1022}
1023
1024template <typename T>
1025template <typename AT>
1026qsizetype QListSpecialMethodsBase<T>::lastIndexOf(const AT &t, qsizetype from) const noexcept
1027{
1028 return QtPrivate::lastIndexOf(*self(), t, from);
1029}
1030
1031template <typename T>
1032inline QList<T> QList<T>::mid(qsizetype pos, qsizetype len) const
1033{
1034 qsizetype p = pos;
1035 qsizetype l = len;
1036 using namespace QtPrivate;
1037 switch (QContainerImplHelper::mid(originalLength: d.size, position: &p, length: &l)) {
1038 case QContainerImplHelper::Null:
1039 case QContainerImplHelper::Empty:
1040 return QList();
1041 case QContainerImplHelper::Full:
1042 return *this;
1043 case QContainerImplHelper::Subset:
1044 break;
1045 }
1046
1047 // Allocate memory
1048 DataPointer copied(l);
1049 copied->copyAppend(data() + p, data() + p + l);
1050 return copied;
1051}
1052
1053Q_DECLARE_SEQUENTIAL_ITERATOR(List)
1054Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(List)
1055
1056template <typename T>
1057size_t qHash(const QList<T> &key, size_t seed = 0)
1058 noexcept(noexcept(qHashRange(key.cbegin(), key.cend(), seed)))
1059{
1060 return qHashRange(key.cbegin(), key.cend(), seed);
1061}
1062
1063template <typename T, typename AT>
1064qsizetype erase(QList<T> &list, const AT &t)
1065{
1066 return QtPrivate::sequential_erase(list, t);
1067}
1068
1069template <typename T, typename Predicate>
1070qsizetype erase_if(QList<T> &list, Predicate pred)
1071{
1072 return QtPrivate::sequential_erase_if(list, pred);
1073}
1074
1075// ### Qt 7 char32_t
1076QList<uint> QStringView::toUcs4() const { return QtPrivate::convertToUcs4(str: *this); }
1077
1078QT_END_NAMESPACE
1079
1080#include <QtCore/qbytearraylist.h>
1081#include <QtCore/qstringlist.h>
1082
1083#endif // QLIST_H
1084

source code of qtbase/src/corelib/tools/qlist.h