1 | /**************************************************************************** |
2 | ** |
3 | ** Copyright (C) 2016 The Qt Company Ltd. |
4 | ** Contact: https://www.qt.io/licensing/ |
5 | ** |
6 | ** This file is part of the QtCore module of the Qt Toolkit. |
7 | ** |
8 | ** $QT_BEGIN_LICENSE:LGPL$ |
9 | ** Commercial License Usage |
10 | ** Licensees holding valid commercial Qt licenses may use this file in |
11 | ** accordance with the commercial license agreement provided with the |
12 | ** Software or, alternatively, in accordance with the terms contained in |
13 | ** a written agreement between you and The Qt Company. For licensing terms |
14 | ** and conditions see https://www.qt.io/terms-conditions. For further |
15 | ** information use the contact form at https://www.qt.io/contact-us. |
16 | ** |
17 | ** GNU Lesser General Public License Usage |
18 | ** Alternatively, this file may be used under the terms of the GNU Lesser |
19 | ** General Public License version 3 as published by the Free Software |
20 | ** Foundation and appearing in the file LICENSE.LGPL3 included in the |
21 | ** packaging of this file. Please review the following information to |
22 | ** ensure the GNU Lesser General Public License version 3 requirements |
23 | ** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. |
24 | ** |
25 | ** GNU General Public License Usage |
26 | ** Alternatively, this file may be used under the terms of the GNU |
27 | ** General Public License version 2.0 or (at your option) the GNU General |
28 | ** Public license version 3 or any later version approved by the KDE Free |
29 | ** Qt Foundation. The licenses are as published by the Free Software |
30 | ** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 |
31 | ** included in the packaging of this file. Please review the following |
32 | ** information to ensure the GNU General Public License requirements will |
33 | ** be met: https://www.gnu.org/licenses/gpl-2.0.html and |
34 | ** https://www.gnu.org/licenses/gpl-3.0.html. |
35 | ** |
36 | ** $QT_END_LICENSE$ |
37 | ** |
38 | ****************************************************************************/ |
39 | |
40 | #ifndef QVECTOR_H |
41 | #define QVECTOR_H |
42 | |
43 | #include <QtCore/qalgorithms.h> |
44 | #include <QtCore/qiterator.h> |
45 | #include <QtCore/qrefcount.h> |
46 | #include <QtCore/qarraydata.h> |
47 | #include <QtCore/qhashfunctions.h> |
48 | #include <QtCore/qcontainertools_impl.h> |
49 | |
50 | #include <iterator> |
51 | #include <initializer_list> |
52 | #if QT_VERSION < QT_VERSION_CHECK(6,0,0) |
53 | #include <vector> |
54 | #endif |
55 | #include <stdlib.h> |
56 | #include <string.h> |
57 | |
58 | #include <algorithm> |
59 | |
60 | QT_BEGIN_NAMESPACE |
61 | |
62 | template <typename T> |
63 | class QVector |
64 | { |
65 | typedef QTypedArrayData<T> Data; |
66 | Data *d; |
67 | |
68 | public: |
69 | inline QVector() noexcept : d(Data::sharedNull()) { } |
70 | explicit QVector(int size); |
71 | QVector(int size, const T &t); |
72 | inline QVector(const QVector<T> &v); |
73 | inline ~QVector() { if (!d->ref.deref()) freeData(d); } |
74 | QVector<T> &operator=(const QVector<T> &v); |
75 | QVector(QVector<T> &&other) noexcept : d(other.d) { other.d = Data::sharedNull(); } |
76 | QVector<T> &operator=(QVector<T> &&other) noexcept |
77 | { QVector moved(std::move(other)); swap(moved); return *this; } |
78 | void swap(QVector<T> &other) noexcept { qSwap(d, other.d); } |
79 | inline QVector(std::initializer_list<T> args); |
80 | QVector<T> &operator=(std::initializer_list<T> args); |
81 | template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator> = true> |
82 | inline QVector(InputIterator first, InputIterator last); |
83 | explicit QVector(QArrayDataPointerRef<T> ref) noexcept : d(ref.ptr) {} |
84 | |
85 | bool operator==(const QVector<T> &v) const; |
86 | inline bool operator!=(const QVector<T> &v) const { return !(*this == v); } |
87 | |
88 | inline int size() const { return d->size; } |
89 | |
90 | inline bool isEmpty() const { return d->size == 0; } |
91 | |
92 | void resize(int size); |
93 | |
94 | inline int capacity() const { return int(d->alloc); } |
95 | void reserve(int size); |
96 | inline void squeeze() |
97 | { |
98 | if (d->size < int(d->alloc)) { |
99 | if (!d->size) { |
100 | *this = QVector<T>(); |
101 | return; |
102 | } |
103 | realloc(d->size); |
104 | } |
105 | if (d->capacityReserved) { |
106 | // capacity reserved in a read only memory would be useless |
107 | // this checks avoid writing to such memory. |
108 | d->capacityReserved = 0; |
109 | } |
110 | } |
111 | |
112 | inline void detach(); |
113 | inline bool isDetached() const { return !d->ref.isShared(); } |
114 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
115 | inline void setSharable(bool sharable) |
116 | { |
117 | if (sharable == d->ref.isSharable()) |
118 | return; |
119 | if (!sharable) |
120 | detach(); |
121 | |
122 | if (d == Data::unsharableEmpty()) { |
123 | if (sharable) |
124 | d = Data::sharedNull(); |
125 | } else { |
126 | d->ref.setSharable(sharable); |
127 | } |
128 | Q_ASSERT(d->ref.isSharable() == sharable); |
129 | } |
130 | #endif |
131 | |
132 | inline bool isSharedWith(const QVector<T> &other) const { return d == other.d; } |
133 | |
134 | inline T *data() { detach(); return d->begin(); } |
135 | inline const T *data() const { return d->begin(); } |
136 | inline const T *constData() const { return d->begin(); } |
137 | void clear(); |
138 | |
139 | const T &at(int i) const; |
140 | T &operator[](int i); |
141 | const T &operator[](int i) const; |
142 | void append(const T &t); |
143 | void append(T &&t); |
144 | inline void append(const QVector<T> &l) { *this += l; } |
145 | void prepend(T &&t); |
146 | void prepend(const T &t); |
147 | void insert(int i, T &&t); |
148 | void insert(int i, const T &t); |
149 | void insert(int i, int n, const T &t); |
150 | void replace(int i, const T &t); |
151 | void remove(int i); |
152 | void remove(int i, int n); |
153 | inline void removeFirst() { Q_ASSERT(!isEmpty()); erase(d->begin()); } |
154 | inline void removeLast(); |
155 | T takeFirst() { Q_ASSERT(!isEmpty()); T r = std::move(first()); removeFirst(); return r; } |
156 | T takeLast() { Q_ASSERT(!isEmpty()); T r = std::move(last()); removeLast(); return r; } |
157 | |
158 | QVector<T> &fill(const T &t, int size = -1); |
159 | |
160 | int indexOf(const T &t, int from = 0) const; |
161 | int lastIndexOf(const T &t, int from = -1) const; |
162 | bool contains(const T &t) const; |
163 | int count(const T &t) const; |
164 | |
165 | // QList compatibility |
166 | void removeAt(int i) { remove(i); } |
167 | int removeAll(const T &t) |
168 | { |
169 | const const_iterator ce = this->cend(), cit = std::find(this->cbegin(), ce, t); |
170 | if (cit == ce) |
171 | return 0; |
172 | // next operation detaches, so ce, cit, t may become invalidated: |
173 | const T tCopy = t; |
174 | const int firstFoundIdx = std::distance(this->cbegin(), cit); |
175 | const iterator e = end(), it = std::remove(begin() + firstFoundIdx, e, tCopy); |
176 | const int result = std::distance(it, e); |
177 | erase(it, e); |
178 | return result; |
179 | } |
180 | bool removeOne(const T &t) |
181 | { |
182 | const int i = indexOf(t); |
183 | if (i < 0) |
184 | return false; |
185 | remove(i); |
186 | return true; |
187 | } |
188 | int length() const { return size(); } |
189 | T takeAt(int i) { T t = std::move((*this)[i]); remove(i); return t; } |
190 | void move(int from, int to) |
191 | { |
192 | Q_ASSERT_X(from >= 0 && from < size(), "QVector::move(int,int)" , "'from' is out-of-range" ); |
193 | Q_ASSERT_X(to >= 0 && to < size(), "QVector::move(int,int)" , "'to' is out-of-range" ); |
194 | if (from == to) // don't detach when no-op |
195 | return; |
196 | detach(); |
197 | T * const b = d->begin(); |
198 | if (from < to) |
199 | std::rotate(b + from, b + from + 1, b + to + 1); |
200 | else |
201 | std::rotate(b + to, b + from, b + from + 1); |
202 | } |
203 | |
204 | // STL-style |
205 | typedef typename Data::iterator iterator; |
206 | typedef typename Data::const_iterator const_iterator; |
207 | typedef std::reverse_iterator<iterator> reverse_iterator; |
208 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; |
209 | #if !defined(QT_STRICT_ITERATORS) || defined(Q_CLANG_QDOC) |
210 | inline iterator begin() { detach(); return d->begin(); } |
211 | inline const_iterator begin() const noexcept { return d->constBegin(); } |
212 | inline const_iterator cbegin() const noexcept { return d->constBegin(); } |
213 | inline const_iterator constBegin() const noexcept { return d->constBegin(); } |
214 | inline iterator end() { detach(); return d->end(); } |
215 | inline const_iterator end() const noexcept { return d->constEnd(); } |
216 | inline const_iterator cend() const noexcept { return d->constEnd(); } |
217 | inline const_iterator constEnd() const noexcept { return d->constEnd(); } |
218 | #else |
219 | inline iterator begin(iterator = iterator()) { detach(); return d->begin(); } |
220 | inline const_iterator begin(const_iterator = const_iterator()) const noexcept { return d->constBegin(); } |
221 | inline const_iterator cbegin(const_iterator = const_iterator()) const noexcept { return d->constBegin(); } |
222 | inline const_iterator constBegin(const_iterator = const_iterator()) const noexcept { return d->constBegin(); } |
223 | inline iterator end(iterator = iterator()) { detach(); return d->end(); } |
224 | inline const_iterator end(const_iterator = const_iterator()) const noexcept { return d->constEnd(); } |
225 | inline const_iterator cend(const_iterator = const_iterator()) const noexcept { return d->constEnd(); } |
226 | inline const_iterator constEnd(const_iterator = const_iterator()) const noexcept { return d->constEnd(); } |
227 | #endif |
228 | reverse_iterator rbegin() { return reverse_iterator(end()); } |
229 | reverse_iterator rend() { return reverse_iterator(begin()); } |
230 | const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); } |
231 | const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); } |
232 | const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(end()); } |
233 | const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); } |
234 | iterator insert(iterator before, int n, const T &x); |
235 | inline iterator insert(iterator before, const T &x) { return insert(before, 1, x); } |
236 | inline iterator insert(iterator before, T &&x); |
237 | iterator erase(iterator begin, iterator end); |
238 | inline iterator erase(iterator pos) { return erase(pos, pos+1); } |
239 | |
240 | // more Qt |
241 | inline int count() const { return d->size; } |
242 | inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); } |
243 | inline const T &first() const { Q_ASSERT(!isEmpty()); return *begin(); } |
244 | inline const T &constFirst() const { Q_ASSERT(!isEmpty()); return *begin(); } |
245 | inline T& last() { Q_ASSERT(!isEmpty()); return *(end()-1); } |
246 | inline const T &last() const { Q_ASSERT(!isEmpty()); return *(end()-1); } |
247 | inline const T &constLast() const { Q_ASSERT(!isEmpty()); return *(end()-1); } |
248 | inline bool startsWith(const T &t) const { return !isEmpty() && first() == t; } |
249 | inline bool endsWith(const T &t) const { return !isEmpty() && last() == t; } |
250 | QVector<T> mid(int pos, int len = -1) const; |
251 | |
252 | T value(int i) const; |
253 | T value(int i, const T &defaultValue) const; |
254 | |
255 | void swapItemsAt(int i, int j) { |
256 | Q_ASSERT_X(i >= 0 && i < size() && j >= 0 && j < size(), |
257 | "QVector<T>::swap" , "index out of range" ); |
258 | detach(); |
259 | qSwap(d->begin()[i], d->begin()[j]); |
260 | } |
261 | |
262 | // STL compatibility |
263 | typedef T value_type; |
264 | typedef value_type* pointer; |
265 | typedef const value_type* const_pointer; |
266 | typedef value_type& reference; |
267 | typedef const value_type& const_reference; |
268 | typedef qptrdiff difference_type; |
269 | typedef iterator Iterator; |
270 | typedef const_iterator ConstIterator; |
271 | typedef int size_type; |
272 | inline void push_back(const T &t) { append(t); } |
273 | void push_back(T &&t) { append(std::move(t)); } |
274 | void push_front(T &&t) { prepend(std::move(t)); } |
275 | inline void push_front(const T &t) { prepend(t); } |
276 | void pop_back() { removeLast(); } |
277 | void pop_front() { removeFirst(); } |
278 | inline bool empty() const |
279 | { return d->size == 0; } |
280 | inline T& front() { return first(); } |
281 | inline const_reference front() const { return first(); } |
282 | inline reference back() { return last(); } |
283 | inline const_reference back() const { return last(); } |
284 | void shrink_to_fit() { squeeze(); } |
285 | |
286 | // comfort |
287 | QVector<T> &operator+=(const QVector<T> &l); |
288 | inline QVector<T> operator+(const QVector<T> &l) const |
289 | { QVector n = *this; n += l; return n; } |
290 | inline QVector<T> &operator+=(const T &t) |
291 | { append(t); return *this; } |
292 | inline QVector<T> &operator<< (const T &t) |
293 | { append(t); return *this; } |
294 | inline QVector<T> &operator<<(const QVector<T> &l) |
295 | { *this += l; return *this; } |
296 | inline QVector<T> &operator+=(T &&t) |
297 | { append(std::move(t)); return *this; } |
298 | inline QVector<T> &operator<<(T &&t) |
299 | { append(std::move(t)); return *this; } |
300 | |
301 | static QVector<T> fromList(const QList<T> &list); |
302 | QList<T> toList() const; |
303 | |
304 | #if QT_DEPRECATED_SINCE(5, 14) && QT_VERSION < QT_VERSION_CHECK(6,0,0) |
305 | QT_DEPRECATED_X("Use QVector<T>(vector.begin(), vector.end()) instead." ) |
306 | static inline QVector<T> fromStdVector(const std::vector<T> &vector) |
307 | { return QVector<T>(vector.begin(), vector.end()); } |
308 | QT_DEPRECATED_X("Use std::vector<T>(vector.begin(), vector.end()) instead." ) |
309 | inline std::vector<T> toStdVector() const |
310 | { return std::vector<T>(d->begin(), d->end()); } |
311 | #endif |
312 | private: |
313 | // ### Qt6: remove methods, they are unused |
314 | void reallocData(const int size, const int alloc, QArrayData::AllocationOptions options = QArrayData::Default); |
315 | void reallocData(const int sz) { reallocData(sz, d->alloc); } |
316 | void realloc(int alloc, QArrayData::AllocationOptions options = QArrayData::Default); |
317 | void freeData(Data *d); |
318 | void defaultConstruct(T *from, T *to); |
319 | void copyConstruct(const T *srcFrom, const T *srcTo, T *dstFrom); |
320 | void destruct(T *from, T *to); |
321 | bool isValidIterator(const iterator &i) const |
322 | { |
323 | const std::less<const T*> less = {}; |
324 | return !less(d->end(), i) && !less(i, d->begin()); |
325 | } |
326 | class AlignmentDummy { Data ; T array[1]; }; |
327 | }; |
328 | |
329 | #if defined(__cpp_deduction_guides) && __cpp_deduction_guides >= 201606 |
330 | template <typename InputIterator, |
331 | typename ValueType = typename std::iterator_traits<InputIterator>::value_type, |
332 | QtPrivate::IfIsInputIterator<InputIterator> = true> |
333 | QVector(InputIterator, InputIterator) -> QVector<ValueType>; |
334 | #endif |
335 | |
336 | #ifdef Q_CC_MSVC |
337 | // behavior change: an object of POD type constructed with an initializer of the form () |
338 | // will be default-initialized |
339 | # pragma warning ( push ) |
340 | # pragma warning(disable : 4127) // conditional expression is constant |
341 | #endif |
342 | |
343 | template <typename T> |
344 | void QVector<T>::defaultConstruct(T *from, T *to) |
345 | { |
346 | if (QTypeInfo<T>::isComplex) { |
347 | while (from != to) { |
348 | new (from++) T(); |
349 | } |
350 | } else { |
351 | ::memset(static_cast<void *>(from), 0, (to - from) * sizeof(T)); |
352 | } |
353 | } |
354 | |
355 | template <typename T> |
356 | void QVector<T>::copyConstruct(const T *srcFrom, const T *srcTo, T *dstFrom) |
357 | { |
358 | if (QTypeInfo<T>::isComplex) { |
359 | while (srcFrom != srcTo) |
360 | new (dstFrom++) T(*srcFrom++); |
361 | } else { |
362 | ::memcpy(static_cast<void *>(dstFrom), static_cast<const void *>(srcFrom), (srcTo - srcFrom) * sizeof(T)); |
363 | } |
364 | } |
365 | |
366 | template <typename T> |
367 | void QVector<T>::destruct(T *from, T *to) |
368 | { |
369 | if (QTypeInfo<T>::isComplex) { |
370 | while (from != to) { |
371 | from++->~T(); |
372 | } |
373 | } |
374 | } |
375 | |
376 | template <typename T> |
377 | inline QVector<T>::QVector(const QVector<T> &v) |
378 | { |
379 | if (v.d->ref.ref()) { |
380 | d = v.d; |
381 | } else { |
382 | if (v.d->capacityReserved) { |
383 | d = Data::allocate(v.d->alloc); |
384 | Q_CHECK_PTR(d); |
385 | d->capacityReserved = true; |
386 | } else { |
387 | d = Data::allocate(v.d->size); |
388 | Q_CHECK_PTR(d); |
389 | } |
390 | if (d->alloc) { |
391 | copyConstruct(v.d->begin(), v.d->end(), d->begin()); |
392 | d->size = v.d->size; |
393 | } |
394 | } |
395 | } |
396 | |
397 | #if defined(Q_CC_MSVC) |
398 | #pragma warning( pop ) |
399 | #endif |
400 | |
401 | template <typename T> |
402 | void QVector<T>::detach() |
403 | { |
404 | if (!isDetached()) { |
405 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
406 | if (!d->alloc) |
407 | d = Data::unsharableEmpty(); |
408 | else |
409 | #endif |
410 | realloc(int(d->alloc)); |
411 | } |
412 | Q_ASSERT(isDetached()); |
413 | } |
414 | |
415 | template <typename T> |
416 | void QVector<T>::reserve(int asize) |
417 | { |
418 | if (asize > int(d->alloc)) |
419 | realloc(asize); |
420 | if (isDetached() |
421 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
422 | && d != Data::unsharableEmpty() |
423 | #endif |
424 | ) |
425 | d->capacityReserved = 1; |
426 | Q_ASSERT(capacity() >= asize); |
427 | } |
428 | |
429 | template <typename T> |
430 | void QVector<T>::resize(int asize) |
431 | { |
432 | if (asize == d->size) |
433 | return detach(); |
434 | if (asize > int(d->alloc) || !isDetached()) { // there is not enough space |
435 | QArrayData::AllocationOptions opt = asize > int(d->alloc) ? QArrayData::Grow : QArrayData::Default; |
436 | realloc(qMax(int(d->alloc), asize), opt); |
437 | } |
438 | if (asize < d->size) |
439 | destruct(begin() + asize, end()); |
440 | else |
441 | defaultConstruct(end(), begin() + asize); |
442 | d->size = asize; |
443 | } |
444 | template <typename T> |
445 | inline void QVector<T>::clear() |
446 | { |
447 | if (!d->size) |
448 | return; |
449 | destruct(begin(), end()); |
450 | d->size = 0; |
451 | } |
452 | template <typename T> |
453 | inline const T &QVector<T>::at(int i) const |
454 | { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::at" , "index out of range" ); |
455 | return d->begin()[i]; } |
456 | template <typename T> |
457 | inline const T &QVector<T>::operator[](int i) const |
458 | { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]" , "index out of range" ); |
459 | return d->begin()[i]; } |
460 | template <typename T> |
461 | inline T &QVector<T>::operator[](int i) |
462 | { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]" , "index out of range" ); |
463 | return data()[i]; } |
464 | template <typename T> |
465 | inline void QVector<T>::insert(int i, const T &t) |
466 | { Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert" , "index out of range" ); |
467 | insert(begin() + i, 1, t); } |
468 | template <typename T> |
469 | inline void QVector<T>::insert(int i, int n, const T &t) |
470 | { Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert" , "index out of range" ); |
471 | insert(begin() + i, n, t); } |
472 | template <typename T> |
473 | inline void QVector<T>::insert(int i, T &&t) |
474 | { Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert" , "index out of range" ); |
475 | insert(begin() + i, std::move(t)); } |
476 | template <typename T> |
477 | inline void QVector<T>::remove(int i, int n) |
478 | { Q_ASSERT_X(i >= 0 && n >= 0 && i + n <= d->size, "QVector<T>::remove" , "index out of range" ); |
479 | erase(d->begin() + i, d->begin() + i + n); } |
480 | template <typename T> |
481 | inline void QVector<T>::remove(int i) |
482 | { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::remove" , "index out of range" ); |
483 | erase(d->begin() + i, d->begin() + i + 1); } |
484 | template <typename T> |
485 | inline void QVector<T>::prepend(const T &t) |
486 | { insert(begin(), 1, t); } |
487 | template <typename T> |
488 | inline void QVector<T>::prepend(T &&t) |
489 | { insert(begin(), std::move(t)); } |
490 | |
491 | template <typename T> |
492 | inline void QVector<T>::replace(int i, const T &t) |
493 | { |
494 | Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::replace" , "index out of range" ); |
495 | const T copy(t); |
496 | data()[i] = copy; |
497 | } |
498 | |
499 | template <typename T> |
500 | QVector<T> &QVector<T>::operator=(const QVector<T> &v) |
501 | { |
502 | if (v.d != d) { |
503 | QVector<T> tmp(v); |
504 | tmp.swap(*this); |
505 | } |
506 | return *this; |
507 | } |
508 | |
509 | template <typename T> |
510 | QVector<T>::QVector(int asize) |
511 | { |
512 | Q_ASSERT_X(asize >= 0, "QVector::QVector" , "Size must be greater than or equal to 0." ); |
513 | if (Q_LIKELY(asize > 0)) { |
514 | d = Data::allocate(asize); |
515 | Q_CHECK_PTR(d); |
516 | d->size = asize; |
517 | defaultConstruct(d->begin(), d->end()); |
518 | } else { |
519 | d = Data::sharedNull(); |
520 | } |
521 | } |
522 | |
523 | template <typename T> |
524 | QVector<T>::QVector(int asize, const T &t) |
525 | { |
526 | Q_ASSERT_X(asize >= 0, "QVector::QVector" , "Size must be greater than or equal to 0." ); |
527 | if (asize > 0) { |
528 | d = Data::allocate(asize); |
529 | Q_CHECK_PTR(d); |
530 | d->size = asize; |
531 | T* i = d->end(); |
532 | while (i != d->begin()) |
533 | new (--i) T(t); |
534 | } else { |
535 | d = Data::sharedNull(); |
536 | } |
537 | } |
538 | |
539 | #if defined(Q_CC_MSVC) |
540 | QT_WARNING_PUSH |
541 | QT_WARNING_DISABLE_MSVC(4127) // conditional expression is constant |
542 | #endif // Q_CC_MSVC |
543 | |
544 | template <typename T> |
545 | QVector<T>::QVector(std::initializer_list<T> args) |
546 | { |
547 | if (args.size() > 0) { |
548 | d = Data::allocate(args.size()); |
549 | Q_CHECK_PTR(d); |
550 | // std::initializer_list<T>::iterator is guaranteed to be |
551 | // const T* ([support.initlist]/1), so can be memcpy'ed away from by copyConstruct |
552 | copyConstruct(args.begin(), args.end(), d->begin()); |
553 | d->size = int(args.size()); |
554 | } else { |
555 | d = Data::sharedNull(); |
556 | } |
557 | } |
558 | |
559 | template <typename T> |
560 | QVector<T> &QVector<T>::operator=(std::initializer_list<T> args) |
561 | { |
562 | QVector<T> tmp(args); |
563 | tmp.swap(*this); |
564 | return *this; |
565 | } |
566 | |
567 | #if defined(Q_CC_MSVC) |
568 | QT_WARNING_POP |
569 | #endif // Q_CC_MSVC |
570 | |
571 | template <typename T> |
572 | template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator>> |
573 | QVector<T>::QVector(InputIterator first, InputIterator last) |
574 | : QVector() |
575 | { |
576 | QtPrivate::reserveIfForwardIterator(this, first, last); |
577 | std::copy(first, last, std::back_inserter(*this)); |
578 | } |
579 | |
580 | template <typename T> |
581 | void QVector<T>::freeData(Data *x) |
582 | { |
583 | destruct(x->begin(), x->end()); |
584 | Data::deallocate(x); |
585 | } |
586 | |
587 | #if defined(Q_CC_MSVC) |
588 | QT_WARNING_PUSH |
589 | QT_WARNING_DISABLE_MSVC(4127) // conditional expression is constant |
590 | #endif |
591 | |
592 | template <typename T> |
593 | void QVector<T>::reallocData(const int asize, const int aalloc, QArrayData::AllocationOptions options) |
594 | { |
595 | Q_ASSERT(asize >= 0 && asize <= aalloc); |
596 | Data *x = d; |
597 | |
598 | const bool isShared = d->ref.isShared(); |
599 | |
600 | if (aalloc != 0) { |
601 | if (aalloc != int(d->alloc) || isShared) { |
602 | QT_TRY { |
603 | // allocate memory |
604 | x = Data::allocate(aalloc, options); |
605 | Q_CHECK_PTR(x); |
606 | // aalloc is bigger then 0 so it is not [un]sharedEmpty |
607 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
608 | Q_ASSERT(x->ref.isSharable() || options.testFlag(QArrayData::Unsharable)); |
609 | #endif |
610 | Q_ASSERT(!x->ref.isStatic()); |
611 | x->size = asize; |
612 | |
613 | T *srcBegin = d->begin(); |
614 | T *srcEnd = asize > d->size ? d->end() : d->begin() + asize; |
615 | T *dst = x->begin(); |
616 | |
617 | if (!QTypeInfoQuery<T>::isRelocatable || (isShared && QTypeInfo<T>::isComplex)) { |
618 | QT_TRY { |
619 | if (isShared || !std::is_nothrow_move_constructible<T>::value) { |
620 | // we can not move the data, we need to copy construct it |
621 | while (srcBegin != srcEnd) |
622 | new (dst++) T(*srcBegin++); |
623 | } else { |
624 | while (srcBegin != srcEnd) |
625 | new (dst++) T(std::move(*srcBegin++)); |
626 | } |
627 | } QT_CATCH (...) { |
628 | // destruct already copied objects |
629 | destruct(x->begin(), dst); |
630 | QT_RETHROW; |
631 | } |
632 | } else { |
633 | ::memcpy(static_cast<void *>(dst), static_cast<void *>(srcBegin), (srcEnd - srcBegin) * sizeof(T)); |
634 | dst += srcEnd - srcBegin; |
635 | |
636 | // destruct unused / not moved data |
637 | if (asize < d->size) |
638 | destruct(d->begin() + asize, d->end()); |
639 | } |
640 | |
641 | if (asize > d->size) { |
642 | // construct all new objects when growing |
643 | if (!QTypeInfo<T>::isComplex) { |
644 | ::memset(static_cast<void *>(dst), 0, (static_cast<T *>(x->end()) - dst) * sizeof(T)); |
645 | } else { |
646 | QT_TRY { |
647 | while (dst != x->end()) |
648 | new (dst++) T(); |
649 | } QT_CATCH (...) { |
650 | // destruct already copied objects |
651 | destruct(x->begin(), dst); |
652 | QT_RETHROW; |
653 | } |
654 | } |
655 | } |
656 | } QT_CATCH (...) { |
657 | Data::deallocate(x); |
658 | QT_RETHROW; |
659 | } |
660 | x->capacityReserved = d->capacityReserved; |
661 | } else { |
662 | Q_ASSERT(int(d->alloc) == aalloc); // resize, without changing allocation size |
663 | Q_ASSERT(isDetached()); // can be done only on detached d |
664 | Q_ASSERT(x == d); // in this case we do not need to allocate anything |
665 | if (asize <= d->size) { |
666 | destruct(x->begin() + asize, x->end()); // from future end to current end |
667 | } else { |
668 | defaultConstruct(x->end(), x->begin() + asize); // from current end to future end |
669 | } |
670 | x->size = asize; |
671 | } |
672 | } else { |
673 | x = Data::sharedNull(); |
674 | } |
675 | if (d != x) { |
676 | if (!d->ref.deref()) { |
677 | if (!QTypeInfoQuery<T>::isRelocatable || !aalloc || (isShared && QTypeInfo<T>::isComplex)) { |
678 | // data was copy constructed, we need to call destructors |
679 | // or if !alloc we did nothing to the old 'd'. |
680 | freeData(d); |
681 | } else { |
682 | Data::deallocate(d); |
683 | } |
684 | } |
685 | d = x; |
686 | } |
687 | |
688 | Q_ASSERT(d->data()); |
689 | Q_ASSERT(uint(d->size) <= d->alloc); |
690 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
691 | Q_ASSERT(d != Data::unsharableEmpty()); |
692 | #endif |
693 | Q_ASSERT(aalloc ? d != Data::sharedNull() : d == Data::sharedNull()); |
694 | Q_ASSERT(d->alloc >= uint(aalloc)); |
695 | Q_ASSERT(d->size == asize); |
696 | } |
697 | |
698 | template<typename T> |
699 | void QVector<T>::realloc(int aalloc, QArrayData::AllocationOptions options) |
700 | { |
701 | Q_ASSERT(aalloc >= d->size); |
702 | Data *x = d; |
703 | |
704 | const bool isShared = d->ref.isShared(); |
705 | |
706 | QT_TRY { |
707 | // allocate memory |
708 | x = Data::allocate(aalloc, options); |
709 | Q_CHECK_PTR(x); |
710 | // aalloc is bigger then 0 so it is not [un]sharedEmpty |
711 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
712 | Q_ASSERT(x->ref.isSharable() || options.testFlag(QArrayData::Unsharable)); |
713 | #endif |
714 | Q_ASSERT(!x->ref.isStatic()); |
715 | x->size = d->size; |
716 | |
717 | T *srcBegin = d->begin(); |
718 | T *srcEnd = d->end(); |
719 | T *dst = x->begin(); |
720 | |
721 | if (!QTypeInfoQuery<T>::isRelocatable || (isShared && QTypeInfo<T>::isComplex)) { |
722 | QT_TRY { |
723 | if (isShared || !std::is_nothrow_move_constructible<T>::value) { |
724 | // we can not move the data, we need to copy construct it |
725 | while (srcBegin != srcEnd) |
726 | new (dst++) T(*srcBegin++); |
727 | } else { |
728 | while (srcBegin != srcEnd) |
729 | new (dst++) T(std::move(*srcBegin++)); |
730 | } |
731 | } QT_CATCH (...) { |
732 | // destruct already copied objects |
733 | destruct(x->begin(), dst); |
734 | QT_RETHROW; |
735 | } |
736 | } else { |
737 | ::memcpy(static_cast<void *>(dst), static_cast<void *>(srcBegin), (srcEnd - srcBegin) * sizeof(T)); |
738 | dst += srcEnd - srcBegin; |
739 | } |
740 | |
741 | } QT_CATCH (...) { |
742 | Data::deallocate(x); |
743 | QT_RETHROW; |
744 | } |
745 | x->capacityReserved = d->capacityReserved; |
746 | |
747 | Q_ASSERT(d != x); |
748 | if (!d->ref.deref()) { |
749 | if (!QTypeInfoQuery<T>::isRelocatable || !aalloc || (isShared && QTypeInfo<T>::isComplex)) { |
750 | // data was copy constructed, we need to call destructors |
751 | // or if !alloc we did nothing to the old 'd'. |
752 | freeData(d); |
753 | } else { |
754 | Data::deallocate(d); |
755 | } |
756 | } |
757 | d = x; |
758 | |
759 | Q_ASSERT(d->data()); |
760 | Q_ASSERT(uint(d->size) <= d->alloc); |
761 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
762 | Q_ASSERT(d != Data::unsharableEmpty()); |
763 | #endif |
764 | Q_ASSERT(d != Data::sharedNull()); |
765 | Q_ASSERT(d->alloc >= uint(aalloc)); |
766 | } |
767 | |
768 | #if defined(Q_CC_MSVC) |
769 | QT_WARNING_POP |
770 | #endif |
771 | |
772 | template<typename T> |
773 | Q_OUTOFLINE_TEMPLATE T QVector<T>::value(int i) const |
774 | { |
775 | if (uint(i) >= uint(d->size)) { |
776 | return T(); |
777 | } |
778 | return d->begin()[i]; |
779 | } |
780 | template<typename T> |
781 | Q_OUTOFLINE_TEMPLATE T QVector<T>::value(int i, const T &defaultValue) const |
782 | { |
783 | return uint(i) >= uint(d->size) ? defaultValue : d->begin()[i]; |
784 | } |
785 | |
786 | template <typename T> |
787 | void QVector<T>::append(const T &t) |
788 | { |
789 | const bool isTooSmall = uint(d->size + 1) > d->alloc; |
790 | if (!isDetached() || isTooSmall) { |
791 | T copy(t); |
792 | QArrayData::AllocationOptions opt(isTooSmall ? QArrayData::Grow : QArrayData::Default); |
793 | realloc(isTooSmall ? d->size + 1 : d->alloc, opt); |
794 | |
795 | if (QTypeInfo<T>::isComplex) |
796 | new (d->end()) T(std::move(copy)); |
797 | else |
798 | *d->end() = std::move(copy); |
799 | |
800 | } else { |
801 | if (QTypeInfo<T>::isComplex) |
802 | new (d->end()) T(t); |
803 | else |
804 | *d->end() = t; |
805 | } |
806 | ++d->size; |
807 | } |
808 | |
809 | template <typename T> |
810 | void QVector<T>::append(T &&t) |
811 | { |
812 | const bool isTooSmall = uint(d->size + 1) > d->alloc; |
813 | if (!isDetached() || isTooSmall) { |
814 | QArrayData::AllocationOptions opt(isTooSmall ? QArrayData::Grow : QArrayData::Default); |
815 | realloc(isTooSmall ? d->size + 1 : d->alloc, opt); |
816 | } |
817 | |
818 | new (d->end()) T(std::move(t)); |
819 | |
820 | ++d->size; |
821 | } |
822 | |
823 | template <typename T> |
824 | void QVector<T>::removeLast() |
825 | { |
826 | Q_ASSERT(!isEmpty()); |
827 | Q_ASSERT(d->alloc); |
828 | |
829 | if (d->ref.isShared()) |
830 | detach(); |
831 | --d->size; |
832 | if (QTypeInfo<T>::isComplex) |
833 | (d->data() + d->size)->~T(); |
834 | } |
835 | |
836 | template <typename T> |
837 | typename QVector<T>::iterator QVector<T>::insert(iterator before, size_type n, const T &t) |
838 | { |
839 | Q_ASSERT_X(isValidIterator(before), "QVector::insert" , "The specified iterator argument 'before' is invalid" ); |
840 | |
841 | const auto offset = std::distance(d->begin(), before); |
842 | if (n != 0) { |
843 | const T copy(t); |
844 | if (!isDetached() || d->size + n > int(d->alloc)) |
845 | realloc(d->size + n, QArrayData::Grow); |
846 | if (!QTypeInfoQuery<T>::isRelocatable) { |
847 | T *b = d->end(); |
848 | T *i = d->end() + n; |
849 | while (i != b) |
850 | new (--i) T; |
851 | i = d->end(); |
852 | T *j = i + n; |
853 | b = d->begin() + offset; |
854 | while (i != b) |
855 | *--j = *--i; |
856 | i = b+n; |
857 | while (i != b) |
858 | *--i = copy; |
859 | } else { |
860 | T *b = d->begin() + offset; |
861 | T *i = b + n; |
862 | memmove(static_cast<void *>(i), static_cast<const void *>(b), (d->size - offset) * sizeof(T)); |
863 | while (i != b) |
864 | new (--i) T(copy); |
865 | } |
866 | d->size += n; |
867 | } |
868 | return d->begin() + offset; |
869 | } |
870 | |
871 | template <typename T> |
872 | typename QVector<T>::iterator QVector<T>::insert(iterator before, T &&t) |
873 | { |
874 | Q_ASSERT_X(isValidIterator(before), "QVector::insert" , "The specified iterator argument 'before' is invalid" ); |
875 | |
876 | const auto offset = std::distance(d->begin(), before); |
877 | if (!isDetached() || d->size + 1 > int(d->alloc)) |
878 | realloc(d->size + 1, QArrayData::Grow); |
879 | if (!QTypeInfoQuery<T>::isRelocatable) { |
880 | T *i = d->end(); |
881 | T *j = i + 1; |
882 | T *b = d->begin() + offset; |
883 | // The new end-element needs to be constructed, the rest must be move assigned |
884 | if (i != b) { |
885 | new (--j) T(std::move(*--i)); |
886 | while (i != b) |
887 | *--j = std::move(*--i); |
888 | *b = std::move(t); |
889 | } else { |
890 | new (b) T(std::move(t)); |
891 | } |
892 | } else { |
893 | T *b = d->begin() + offset; |
894 | memmove(static_cast<void *>(b + 1), static_cast<const void *>(b), (d->size - offset) * sizeof(T)); |
895 | new (b) T(std::move(t)); |
896 | } |
897 | d->size += 1; |
898 | return d->begin() + offset; |
899 | } |
900 | |
901 | template <typename T> |
902 | typename QVector<T>::iterator QVector<T>::erase(iterator abegin, iterator aend) |
903 | { |
904 | Q_ASSERT_X(isValidIterator(abegin), "QVector::erase" , "The specified iterator argument 'abegin' is invalid" ); |
905 | Q_ASSERT_X(isValidIterator(aend), "QVector::erase" , "The specified iterator argument 'aend' is invalid" ); |
906 | |
907 | const auto itemsToErase = aend - abegin; |
908 | |
909 | if (!itemsToErase) |
910 | return abegin; |
911 | |
912 | Q_ASSERT(abegin >= d->begin()); |
913 | Q_ASSERT(aend <= d->end()); |
914 | Q_ASSERT(abegin <= aend); |
915 | |
916 | const auto itemsUntouched = abegin - d->begin(); |
917 | |
918 | // FIXME we could do a proper realloc, which copy constructs only needed data. |
919 | // FIXME we are about to delete data - maybe it is good time to shrink? |
920 | // FIXME the shrink is also an issue in removeLast, that is just a copy + reduce of this. |
921 | if (d->alloc) { |
922 | detach(); |
923 | abegin = d->begin() + itemsUntouched; |
924 | aend = abegin + itemsToErase; |
925 | if (!QTypeInfoQuery<T>::isRelocatable) { |
926 | iterator moveBegin = abegin + itemsToErase; |
927 | iterator moveEnd = d->end(); |
928 | while (moveBegin != moveEnd) { |
929 | if (QTypeInfo<T>::isComplex) |
930 | static_cast<T *>(abegin)->~T(); |
931 | new (abegin++) T(*moveBegin++); |
932 | } |
933 | if (abegin < d->end()) { |
934 | // destroy rest of instances |
935 | destruct(abegin, d->end()); |
936 | } |
937 | } else { |
938 | destruct(abegin, aend); |
939 | // QTBUG-53605: static_cast<void *> masks clang errors of the form |
940 | // error: destination for this 'memmove' call is a pointer to class containing a dynamic class |
941 | // FIXME maybe use std::is_polymorphic (as soon as allowed) to avoid the memmove |
942 | memmove(static_cast<void *>(abegin), static_cast<void *>(aend), |
943 | (d->size - itemsToErase - itemsUntouched) * sizeof(T)); |
944 | } |
945 | d->size -= int(itemsToErase); |
946 | } |
947 | return d->begin() + itemsUntouched; |
948 | } |
949 | |
950 | template <typename T> |
951 | bool QVector<T>::operator==(const QVector<T> &v) const |
952 | { |
953 | if (d == v.d) |
954 | return true; |
955 | if (d->size != v.d->size) |
956 | return false; |
957 | const T *vb = v.d->begin(); |
958 | const T *b = d->begin(); |
959 | const T *e = d->end(); |
960 | return std::equal(b, e, QT_MAKE_CHECKED_ARRAY_ITERATOR(vb, v.d->size)); |
961 | } |
962 | |
963 | template <typename T> |
964 | QVector<T> &QVector<T>::fill(const T &from, int asize) |
965 | { |
966 | const T copy(from); |
967 | resize(asize < 0 ? d->size : asize); |
968 | if (d->size) { |
969 | T *i = d->end(); |
970 | T *b = d->begin(); |
971 | while (i != b) |
972 | *--i = copy; |
973 | } |
974 | return *this; |
975 | } |
976 | |
977 | template <typename T> |
978 | QVector<T> &QVector<T>::operator+=(const QVector &l) |
979 | { |
980 | if (d->size == 0) { |
981 | *this = l; |
982 | } else { |
983 | uint newSize = d->size + l.d->size; |
984 | const bool isTooSmall = newSize > d->alloc; |
985 | if (!isDetached() || isTooSmall) { |
986 | QArrayData::AllocationOptions opt(isTooSmall ? QArrayData::Grow : QArrayData::Default); |
987 | realloc(isTooSmall ? newSize : d->alloc, opt); |
988 | } |
989 | |
990 | if (d->alloc) { |
991 | T *w = d->begin() + newSize; |
992 | T *i = l.d->end(); |
993 | T *b = l.d->begin(); |
994 | while (i != b) { |
995 | if (QTypeInfo<T>::isComplex) |
996 | new (--w) T(*--i); |
997 | else |
998 | *--w = *--i; |
999 | } |
1000 | d->size = newSize; |
1001 | } |
1002 | } |
1003 | return *this; |
1004 | } |
1005 | |
1006 | template <typename T> |
1007 | int QVector<T>::indexOf(const T &t, int from) const |
1008 | { |
1009 | if (from < 0) |
1010 | from = qMax(from + d->size, 0); |
1011 | if (from < d->size) { |
1012 | T* n = d->begin() + from - 1; |
1013 | T* e = d->end(); |
1014 | while (++n != e) |
1015 | if (*n == t) |
1016 | return n - d->begin(); |
1017 | } |
1018 | return -1; |
1019 | } |
1020 | |
1021 | template <typename T> |
1022 | int QVector<T>::lastIndexOf(const T &t, int from) const |
1023 | { |
1024 | if (from < 0) |
1025 | from += d->size; |
1026 | else if (from >= d->size) |
1027 | from = d->size-1; |
1028 | if (from >= 0) { |
1029 | T* b = d->begin(); |
1030 | T* n = d->begin() + from + 1; |
1031 | while (n != b) { |
1032 | if (*--n == t) |
1033 | return n - b; |
1034 | } |
1035 | } |
1036 | return -1; |
1037 | } |
1038 | |
1039 | template <typename T> |
1040 | bool QVector<T>::contains(const T &t) const |
1041 | { |
1042 | const T *b = d->begin(); |
1043 | const T *e = d->end(); |
1044 | return std::find(b, e, t) != e; |
1045 | } |
1046 | |
1047 | template <typename T> |
1048 | int QVector<T>::count(const T &t) const |
1049 | { |
1050 | const T *b = d->begin(); |
1051 | const T *e = d->end(); |
1052 | return int(std::count(b, e, t)); |
1053 | } |
1054 | |
1055 | template <typename T> |
1056 | Q_OUTOFLINE_TEMPLATE QVector<T> QVector<T>::mid(int pos, int len) const |
1057 | { |
1058 | using namespace QtPrivate; |
1059 | switch (QContainerImplHelper::mid(d->size, &pos, &len)) { |
1060 | case QContainerImplHelper::Null: |
1061 | case QContainerImplHelper::Empty: |
1062 | return QVector<T>(); |
1063 | case QContainerImplHelper::Full: |
1064 | return *this; |
1065 | case QContainerImplHelper::Subset: |
1066 | break; |
1067 | } |
1068 | |
1069 | QVector<T> midResult; |
1070 | midResult.realloc(len); |
1071 | T *srcFrom = d->begin() + pos; |
1072 | T *srcTo = d->begin() + pos + len; |
1073 | midResult.copyConstruct(srcFrom, srcTo, midResult.data()); |
1074 | midResult.d->size = len; |
1075 | return midResult; |
1076 | } |
1077 | |
1078 | Q_DECLARE_SEQUENTIAL_ITERATOR(Vector) |
1079 | Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(Vector) |
1080 | |
1081 | template <typename T> |
1082 | uint qHash(const QVector<T> &key, uint seed = 0) |
1083 | noexcept(noexcept(qHashRange(key.cbegin(), key.cend(), seed))) |
1084 | { |
1085 | return qHashRange(key.cbegin(), key.cend(), seed); |
1086 | } |
1087 | |
1088 | template <typename T> |
1089 | bool operator<(const QVector<T> &lhs, const QVector<T> &rhs) |
1090 | noexcept(noexcept(std::lexicographical_compare(lhs.begin(), lhs.end(), |
1091 | rhs.begin(), rhs.end()))) |
1092 | { |
1093 | return std::lexicographical_compare(lhs.begin(), lhs.end(), |
1094 | rhs.begin(), rhs.end()); |
1095 | } |
1096 | |
1097 | template <typename T> |
1098 | inline bool operator>(const QVector<T> &lhs, const QVector<T> &rhs) |
1099 | noexcept(noexcept(lhs < rhs)) |
1100 | { |
1101 | return rhs < lhs; |
1102 | } |
1103 | |
1104 | template <typename T> |
1105 | inline bool operator<=(const QVector<T> &lhs, const QVector<T> &rhs) |
1106 | noexcept(noexcept(lhs < rhs)) |
1107 | { |
1108 | return !(lhs > rhs); |
1109 | } |
1110 | |
1111 | template <typename T> |
1112 | inline bool operator>=(const QVector<T> &lhs, const QVector<T> &rhs) |
1113 | noexcept(noexcept(lhs < rhs)) |
1114 | { |
1115 | return !(lhs < rhs); |
1116 | } |
1117 | |
1118 | /* |
1119 | ### Qt 5: |
1120 | ### This needs to be removed for next releases of Qt. It is a workaround for vc++ because |
1121 | ### Qt exports QPolygon and QPolygonF that inherit QVector<QPoint> and |
1122 | ### QVector<QPointF> respectively. |
1123 | */ |
1124 | |
1125 | #if defined(Q_CC_MSVC) && !defined(QT_BUILD_CORE_LIB) |
1126 | QT_BEGIN_INCLUDE_NAMESPACE |
1127 | #include <QtCore/qpoint.h> |
1128 | QT_END_INCLUDE_NAMESPACE |
1129 | extern template class Q_CORE_EXPORT QVector<QPointF>; |
1130 | extern template class Q_CORE_EXPORT QVector<QPoint>; |
1131 | #endif |
1132 | |
1133 | QVector<uint> QStringView::toUcs4() const { return QtPrivate::convertToUcs4(*this); } |
1134 | |
1135 | QT_END_NAMESPACE |
1136 | |
1137 | #endif // QVECTOR_H |
1138 | |