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