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