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

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