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

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