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

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