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