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

Provided by KDAB

Privacy Policy
Learn to use CMake with our Intro Training
Find out more

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