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