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