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 | while (from != to) |
347 | new (from++) T(); |
348 | } |
349 | |
350 | template <typename T> |
351 | void QVector<T>::copyConstruct(const T *srcFrom, const T *srcTo, T *dstFrom) |
352 | { |
353 | if (QTypeInfo<T>::isComplex) { |
354 | while (srcFrom != srcTo) |
355 | new (dstFrom++) T(*srcFrom++); |
356 | } else { |
357 | ::memcpy(static_cast<void *>(dstFrom), static_cast<const void *>(srcFrom), (srcTo - srcFrom) * sizeof(T)); |
358 | } |
359 | } |
360 | |
361 | template <typename T> |
362 | void QVector<T>::destruct(T *from, T *to) |
363 | { |
364 | if (QTypeInfo<T>::isComplex) { |
365 | while (from != to) { |
366 | from++->~T(); |
367 | } |
368 | } |
369 | } |
370 | |
371 | template <typename T> |
372 | inline QVector<T>::QVector(const QVector<T> &v) |
373 | { |
374 | if (v.d->ref.ref()) { |
375 | d = v.d; |
376 | } else { |
377 | if (v.d->capacityReserved) { |
378 | d = Data::allocate(v.d->alloc); |
379 | Q_CHECK_PTR(d); |
380 | d->capacityReserved = true; |
381 | } else { |
382 | d = Data::allocate(v.d->size); |
383 | Q_CHECK_PTR(d); |
384 | } |
385 | if (d->alloc) { |
386 | copyConstruct(v.d->begin(), v.d->end(), d->begin()); |
387 | d->size = v.d->size; |
388 | } |
389 | } |
390 | } |
391 | |
392 | #if defined(Q_CC_MSVC) |
393 | #pragma warning( pop ) |
394 | #endif |
395 | |
396 | template <typename T> |
397 | void QVector<T>::detach() |
398 | { |
399 | if (!isDetached()) { |
400 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
401 | if (!d->alloc) |
402 | d = Data::unsharableEmpty(); |
403 | else |
404 | #endif |
405 | realloc(int(d->alloc)); |
406 | } |
407 | Q_ASSERT(isDetached()); |
408 | } |
409 | |
410 | template <typename T> |
411 | void QVector<T>::reserve(int asize) |
412 | { |
413 | if (asize > int(d->alloc)) |
414 | realloc(asize); |
415 | if (isDetached() |
416 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
417 | && d != Data::unsharableEmpty() |
418 | #endif |
419 | ) |
420 | d->capacityReserved = 1; |
421 | Q_ASSERT(capacity() >= asize); |
422 | } |
423 | |
424 | template <typename T> |
425 | void QVector<T>::resize(int asize) |
426 | { |
427 | if (asize == d->size) |
428 | return detach(); |
429 | if (asize > int(d->alloc) || !isDetached()) { // there is not enough space |
430 | QArrayData::AllocationOptions opt = asize > int(d->alloc) ? QArrayData::Grow : QArrayData::Default; |
431 | realloc(qMax(int(d->alloc), asize), opt); |
432 | } |
433 | if (asize < d->size) |
434 | destruct(begin() + asize, end()); |
435 | else |
436 | defaultConstruct(end(), begin() + asize); |
437 | d->size = asize; |
438 | } |
439 | template <typename T> |
440 | inline void QVector<T>::clear() |
441 | { |
442 | if (!d->size) |
443 | return; |
444 | destruct(begin(), end()); |
445 | d->size = 0; |
446 | } |
447 | template <typename T> |
448 | inline const T &QVector<T>::at(int i) const |
449 | { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::at" , "index out of range" ); |
450 | return d->begin()[i]; } |
451 | template <typename T> |
452 | inline const T &QVector<T>::operator[](int i) const |
453 | { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]" , "index out of range" ); |
454 | return d->begin()[i]; } |
455 | template <typename T> |
456 | inline T &QVector<T>::operator[](int i) |
457 | { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]" , "index out of range" ); |
458 | return data()[i]; } |
459 | template <typename T> |
460 | inline void QVector<T>::insert(int i, const T &t) |
461 | { Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert" , "index out of range" ); |
462 | insert(begin() + i, 1, t); } |
463 | template <typename T> |
464 | inline void QVector<T>::insert(int i, int n, const T &t) |
465 | { Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert" , "index out of range" ); |
466 | insert(begin() + i, n, t); } |
467 | template <typename T> |
468 | inline void QVector<T>::insert(int i, T &&t) |
469 | { Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert" , "index out of range" ); |
470 | insert(begin() + i, std::move(t)); } |
471 | template <typename T> |
472 | inline void QVector<T>::remove(int i, int n) |
473 | { Q_ASSERT_X(i >= 0 && n >= 0 && i + n <= d->size, "QVector<T>::remove" , "index out of range" ); |
474 | erase(d->begin() + i, d->begin() + i + n); } |
475 | template <typename T> |
476 | inline void QVector<T>::remove(int i) |
477 | { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::remove" , "index out of range" ); |
478 | erase(d->begin() + i, d->begin() + i + 1); } |
479 | template <typename T> |
480 | inline void QVector<T>::prepend(const T &t) |
481 | { insert(begin(), 1, t); } |
482 | template <typename T> |
483 | inline void QVector<T>::prepend(T &&t) |
484 | { insert(begin(), std::move(t)); } |
485 | |
486 | template <typename T> |
487 | inline void QVector<T>::replace(int i, const T &t) |
488 | { |
489 | Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::replace" , "index out of range" ); |
490 | const T copy(t); |
491 | data()[i] = copy; |
492 | } |
493 | |
494 | template <typename T> |
495 | QVector<T> &QVector<T>::operator=(const QVector<T> &v) |
496 | { |
497 | if (v.d != d) { |
498 | QVector<T> tmp(v); |
499 | tmp.swap(*this); |
500 | } |
501 | return *this; |
502 | } |
503 | |
504 | template <typename T> |
505 | QVector<T>::QVector(int asize) |
506 | { |
507 | Q_ASSERT_X(asize >= 0, "QVector::QVector" , "Size must be greater than or equal to 0." ); |
508 | if (Q_LIKELY(asize > 0)) { |
509 | d = Data::allocate(asize); |
510 | Q_CHECK_PTR(d); |
511 | d->size = asize; |
512 | defaultConstruct(d->begin(), d->end()); |
513 | } else { |
514 | d = Data::sharedNull(); |
515 | } |
516 | } |
517 | |
518 | template <typename T> |
519 | QVector<T>::QVector(int asize, const T &t) |
520 | { |
521 | Q_ASSERT_X(asize >= 0, "QVector::QVector" , "Size must be greater than or equal to 0." ); |
522 | if (asize > 0) { |
523 | d = Data::allocate(asize); |
524 | Q_CHECK_PTR(d); |
525 | d->size = asize; |
526 | auto i = d->end(); |
527 | while (i != d->begin()) |
528 | new (--i) T(t); |
529 | } else { |
530 | d = Data::sharedNull(); |
531 | } |
532 | } |
533 | |
534 | #if defined(Q_CC_MSVC) |
535 | QT_WARNING_PUSH |
536 | QT_WARNING_DISABLE_MSVC(4127) // conditional expression is constant |
537 | #endif // Q_CC_MSVC |
538 | |
539 | template <typename T> |
540 | QVector<T>::QVector(std::initializer_list<T> args) |
541 | { |
542 | if (args.size() > 0) { |
543 | d = Data::allocate(args.size()); |
544 | Q_CHECK_PTR(d); |
545 | // std::initializer_list<T>::iterator is guaranteed to be |
546 | // const T* ([support.initlist]/1), so can be memcpy'ed away from by copyConstruct |
547 | copyConstruct(args.begin(), args.end(), d->begin()); |
548 | d->size = int(args.size()); |
549 | } else { |
550 | d = Data::sharedNull(); |
551 | } |
552 | } |
553 | |
554 | template <typename T> |
555 | QVector<T> &QVector<T>::operator=(std::initializer_list<T> args) |
556 | { |
557 | QVector<T> tmp(args); |
558 | tmp.swap(*this); |
559 | return *this; |
560 | } |
561 | |
562 | #if defined(Q_CC_MSVC) |
563 | QT_WARNING_POP |
564 | #endif // Q_CC_MSVC |
565 | |
566 | template <typename T> |
567 | template <typename InputIterator, QtPrivate::IfIsInputIterator<InputIterator>> |
568 | QVector<T>::QVector(InputIterator first, InputIterator last) |
569 | : QVector() |
570 | { |
571 | QtPrivate::reserveIfForwardIterator(this, first, last); |
572 | std::copy(first, last, std::back_inserter(*this)); |
573 | } |
574 | |
575 | template <typename T> |
576 | void QVector<T>::freeData(Data *x) |
577 | { |
578 | destruct(x->begin(), x->end()); |
579 | Data::deallocate(x); |
580 | } |
581 | |
582 | #if defined(Q_CC_MSVC) |
583 | QT_WARNING_PUSH |
584 | QT_WARNING_DISABLE_MSVC(4127) // conditional expression is constant |
585 | #endif |
586 | |
587 | template <typename T> |
588 | void QVector<T>::reallocData(const int asize, const int aalloc, QArrayData::AllocationOptions options) |
589 | { |
590 | Q_ASSERT(asize >= 0 && asize <= aalloc); |
591 | Data *x = d; |
592 | |
593 | const bool isShared = d->ref.isShared(); |
594 | |
595 | if (aalloc != 0) { |
596 | if (aalloc != int(d->alloc) || isShared) { |
597 | QT_TRY { |
598 | // allocate memory |
599 | x = Data::allocate(aalloc, options); |
600 | Q_CHECK_PTR(x); |
601 | // aalloc is bigger then 0 so it is not [un]sharedEmpty |
602 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
603 | Q_ASSERT(x->ref.isSharable() || options.testFlag(QArrayData::Unsharable)); |
604 | #endif |
605 | Q_ASSERT(!x->ref.isStatic()); |
606 | x->size = asize; |
607 | |
608 | T *srcBegin = d->begin(); |
609 | T *srcEnd = asize > d->size ? d->end() : d->begin() + asize; |
610 | T *dst = x->begin(); |
611 | |
612 | if (!QTypeInfoQuery<T>::isRelocatable || (isShared && QTypeInfo<T>::isComplex)) { |
613 | QT_TRY { |
614 | if (isShared || !std::is_nothrow_move_constructible<T>::value) { |
615 | // we can not move the data, we need to copy construct it |
616 | while (srcBegin != srcEnd) |
617 | new (dst++) T(*srcBegin++); |
618 | } else { |
619 | while (srcBegin != srcEnd) |
620 | new (dst++) T(std::move(*srcBegin++)); |
621 | } |
622 | } QT_CATCH (...) { |
623 | // destruct already copied objects |
624 | destruct(x->begin(), dst); |
625 | QT_RETHROW; |
626 | } |
627 | } else { |
628 | ::memcpy(static_cast<void *>(dst), static_cast<void *>(srcBegin), (srcEnd - srcBegin) * sizeof(T)); |
629 | dst += srcEnd - srcBegin; |
630 | |
631 | // destruct unused / not moved data |
632 | if (asize < d->size) |
633 | destruct(d->begin() + asize, d->end()); |
634 | } |
635 | |
636 | if (asize > d->size) { |
637 | // construct all new objects when growing |
638 | QT_TRY { |
639 | while (dst != x->end()) |
640 | new (dst++) T(); |
641 | } QT_CATCH (...) { |
642 | // destruct already copied objects |
643 | destruct(x->begin(), dst); |
644 | QT_RETHROW; |
645 | } |
646 | } |
647 | } QT_CATCH (...) { |
648 | Data::deallocate(x); |
649 | QT_RETHROW; |
650 | } |
651 | x->capacityReserved = d->capacityReserved; |
652 | } else { |
653 | Q_ASSERT(int(d->alloc) == aalloc); // resize, without changing allocation size |
654 | Q_ASSERT(isDetached()); // can be done only on detached d |
655 | Q_ASSERT(x == d); // in this case we do not need to allocate anything |
656 | if (asize <= d->size) { |
657 | destruct(x->begin() + asize, x->end()); // from future end to current end |
658 | } else { |
659 | defaultConstruct(x->end(), x->begin() + asize); // from current end to future end |
660 | } |
661 | x->size = asize; |
662 | } |
663 | } else { |
664 | x = Data::sharedNull(); |
665 | } |
666 | if (d != x) { |
667 | if (!d->ref.deref()) { |
668 | if (!QTypeInfoQuery<T>::isRelocatable || !aalloc || (isShared && QTypeInfo<T>::isComplex)) { |
669 | // data was copy constructed, we need to call destructors |
670 | // or if !alloc we did nothing to the old 'd'. |
671 | freeData(d); |
672 | } else { |
673 | Data::deallocate(d); |
674 | } |
675 | } |
676 | d = x; |
677 | } |
678 | |
679 | Q_ASSERT(d->data()); |
680 | Q_ASSERT(uint(d->size) <= d->alloc); |
681 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
682 | Q_ASSERT(d != Data::unsharableEmpty()); |
683 | #endif |
684 | Q_ASSERT(aalloc ? d != Data::sharedNull() : d == Data::sharedNull()); |
685 | Q_ASSERT(d->alloc >= uint(aalloc)); |
686 | Q_ASSERT(d->size == asize); |
687 | } |
688 | |
689 | template<typename T> |
690 | void QVector<T>::realloc(int aalloc, QArrayData::AllocationOptions options) |
691 | { |
692 | Q_ASSERT(aalloc >= d->size); |
693 | Data *x = d; |
694 | |
695 | const bool isShared = d->ref.isShared(); |
696 | |
697 | QT_TRY { |
698 | // allocate memory |
699 | x = Data::allocate(aalloc, options); |
700 | Q_CHECK_PTR(x); |
701 | // aalloc is bigger then 0 so it is not [un]sharedEmpty |
702 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
703 | Q_ASSERT(x->ref.isSharable() || options.testFlag(QArrayData::Unsharable)); |
704 | #endif |
705 | Q_ASSERT(!x->ref.isStatic()); |
706 | x->size = d->size; |
707 | |
708 | T *srcBegin = d->begin(); |
709 | T *srcEnd = d->end(); |
710 | T *dst = x->begin(); |
711 | |
712 | if (!QTypeInfoQuery<T>::isRelocatable || (isShared && QTypeInfo<T>::isComplex)) { |
713 | QT_TRY { |
714 | if (isShared || !std::is_nothrow_move_constructible<T>::value) { |
715 | // we can not move the data, we need to copy construct it |
716 | while (srcBegin != srcEnd) |
717 | new (dst++) T(*srcBegin++); |
718 | } else { |
719 | while (srcBegin != srcEnd) |
720 | new (dst++) T(std::move(*srcBegin++)); |
721 | } |
722 | } QT_CATCH (...) { |
723 | // destruct already copied objects |
724 | destruct(x->begin(), dst); |
725 | QT_RETHROW; |
726 | } |
727 | } else { |
728 | ::memcpy(static_cast<void *>(dst), static_cast<void *>(srcBegin), (srcEnd - srcBegin) * sizeof(T)); |
729 | dst += srcEnd - srcBegin; |
730 | } |
731 | |
732 | } QT_CATCH (...) { |
733 | Data::deallocate(x); |
734 | QT_RETHROW; |
735 | } |
736 | x->capacityReserved = d->capacityReserved; |
737 | |
738 | Q_ASSERT(d != x); |
739 | if (!d->ref.deref()) { |
740 | if (!QTypeInfoQuery<T>::isRelocatable || !aalloc || (isShared && QTypeInfo<T>::isComplex)) { |
741 | // data was copy constructed, we need to call destructors |
742 | // or if !alloc we did nothing to the old 'd'. |
743 | freeData(d); |
744 | } else { |
745 | Data::deallocate(d); |
746 | } |
747 | } |
748 | d = x; |
749 | |
750 | Q_ASSERT(d->data()); |
751 | Q_ASSERT(uint(d->size) <= d->alloc); |
752 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
753 | Q_ASSERT(d != Data::unsharableEmpty()); |
754 | #endif |
755 | Q_ASSERT(d != Data::sharedNull()); |
756 | Q_ASSERT(d->alloc >= uint(aalloc)); |
757 | } |
758 | |
759 | #if defined(Q_CC_MSVC) |
760 | QT_WARNING_POP |
761 | #endif |
762 | |
763 | template<typename T> |
764 | Q_OUTOFLINE_TEMPLATE T QVector<T>::value(int i) const |
765 | { |
766 | if (uint(i) >= uint(d->size)) { |
767 | return T(); |
768 | } |
769 | return d->begin()[i]; |
770 | } |
771 | template<typename T> |
772 | Q_OUTOFLINE_TEMPLATE T QVector<T>::value(int i, const T &defaultValue) const |
773 | { |
774 | return uint(i) >= uint(d->size) ? defaultValue : d->begin()[i]; |
775 | } |
776 | |
777 | template <typename T> |
778 | void QVector<T>::append(const T &t) |
779 | { |
780 | const bool isTooSmall = uint(d->size + 1) > d->alloc; |
781 | if (!isDetached() || isTooSmall) { |
782 | T copy(t); |
783 | QArrayData::AllocationOptions opt(isTooSmall ? QArrayData::Grow : QArrayData::Default); |
784 | realloc(isTooSmall ? d->size + 1 : d->alloc, opt); |
785 | |
786 | if (QTypeInfo<T>::isComplex) |
787 | new (d->end()) T(std::move(copy)); |
788 | else |
789 | *d->end() = std::move(copy); |
790 | |
791 | } else { |
792 | if (QTypeInfo<T>::isComplex) |
793 | new (d->end()) T(t); |
794 | else |
795 | *d->end() = t; |
796 | } |
797 | ++d->size; |
798 | } |
799 | |
800 | template <typename T> |
801 | void QVector<T>::append(T &&t) |
802 | { |
803 | const bool isTooSmall = uint(d->size + 1) > d->alloc; |
804 | if (!isDetached() || isTooSmall) { |
805 | QArrayData::AllocationOptions opt(isTooSmall ? QArrayData::Grow : QArrayData::Default); |
806 | realloc(isTooSmall ? d->size + 1 : d->alloc, opt); |
807 | } |
808 | |
809 | new (d->end()) T(std::move(t)); |
810 | |
811 | ++d->size; |
812 | } |
813 | |
814 | template <typename T> |
815 | void QVector<T>::removeLast() |
816 | { |
817 | Q_ASSERT(!isEmpty()); |
818 | Q_ASSERT(d->alloc); |
819 | |
820 | if (d->ref.isShared()) |
821 | detach(); |
822 | --d->size; |
823 | if (QTypeInfo<T>::isComplex) |
824 | (d->data() + d->size)->~T(); |
825 | } |
826 | |
827 | template <typename T> |
828 | typename QVector<T>::iterator QVector<T>::insert(iterator before, size_type n, const T &t) |
829 | { |
830 | Q_ASSERT_X(isValidIterator(before), "QVector::insert" , "The specified iterator argument 'before' is invalid" ); |
831 | |
832 | const auto offset = std::distance(d->begin(), before); |
833 | if (n != 0) { |
834 | const T copy(t); |
835 | if (!isDetached() || d->size + n > int(d->alloc)) |
836 | realloc(d->size + n, QArrayData::Grow); |
837 | if (!QTypeInfoQuery<T>::isRelocatable) { |
838 | T *b = d->end(); |
839 | T *i = d->end() + n; |
840 | while (i != b) |
841 | new (--i) T; |
842 | i = d->end(); |
843 | T *j = i + n; |
844 | b = d->begin() + offset; |
845 | while (i != b) |
846 | *--j = *--i; |
847 | i = b+n; |
848 | while (i != b) |
849 | *--i = copy; |
850 | } else { |
851 | T *b = d->begin() + offset; |
852 | T *i = b + n; |
853 | memmove(static_cast<void *>(i), static_cast<const void *>(b), (d->size - offset) * sizeof(T)); |
854 | while (i != b) |
855 | new (--i) T(copy); |
856 | } |
857 | d->size += n; |
858 | } |
859 | return d->begin() + offset; |
860 | } |
861 | |
862 | template <typename T> |
863 | typename QVector<T>::iterator QVector<T>::insert(iterator before, T &&t) |
864 | { |
865 | Q_ASSERT_X(isValidIterator(before), "QVector::insert" , "The specified iterator argument 'before' is invalid" ); |
866 | |
867 | const auto offset = std::distance(d->begin(), before); |
868 | if (!isDetached() || d->size + 1 > int(d->alloc)) |
869 | realloc(d->size + 1, QArrayData::Grow); |
870 | if (!QTypeInfoQuery<T>::isRelocatable) { |
871 | T *i = d->end(); |
872 | T *j = i + 1; |
873 | T *b = d->begin() + offset; |
874 | // The new end-element needs to be constructed, the rest must be move assigned |
875 | if (i != b) { |
876 | new (--j) T(std::move(*--i)); |
877 | while (i != b) |
878 | *--j = std::move(*--i); |
879 | *b = std::move(t); |
880 | } else { |
881 | new (b) T(std::move(t)); |
882 | } |
883 | } else { |
884 | T *b = d->begin() + offset; |
885 | memmove(static_cast<void *>(b + 1), static_cast<const void *>(b), (d->size - offset) * sizeof(T)); |
886 | new (b) T(std::move(t)); |
887 | } |
888 | d->size += 1; |
889 | return d->begin() + offset; |
890 | } |
891 | |
892 | template <typename T> |
893 | typename QVector<T>::iterator QVector<T>::erase(iterator abegin, iterator aend) |
894 | { |
895 | Q_ASSERT_X(isValidIterator(abegin), "QVector::erase" , "The specified iterator argument 'abegin' is invalid" ); |
896 | Q_ASSERT_X(isValidIterator(aend), "QVector::erase" , "The specified iterator argument 'aend' is invalid" ); |
897 | |
898 | const auto itemsToErase = aend - abegin; |
899 | |
900 | if (!itemsToErase) |
901 | return abegin; |
902 | |
903 | Q_ASSERT(abegin >= d->begin()); |
904 | Q_ASSERT(aend <= d->end()); |
905 | Q_ASSERT(abegin <= aend); |
906 | |
907 | const auto itemsUntouched = abegin - d->begin(); |
908 | |
909 | // FIXME we could do a proper realloc, which copy constructs only needed data. |
910 | // FIXME we are about to delete data - maybe it is good time to shrink? |
911 | // FIXME the shrink is also an issue in removeLast, that is just a copy + reduce of this. |
912 | if (d->alloc) { |
913 | detach(); |
914 | abegin = d->begin() + itemsUntouched; |
915 | aend = abegin + itemsToErase; |
916 | if (!QTypeInfoQuery<T>::isRelocatable) { |
917 | iterator moveBegin = abegin + itemsToErase; |
918 | iterator moveEnd = d->end(); |
919 | while (moveBegin != moveEnd) { |
920 | if (QTypeInfo<T>::isComplex) |
921 | static_cast<T *>(abegin)->~T(); |
922 | new (abegin++) T(*moveBegin++); |
923 | } |
924 | if (abegin < d->end()) { |
925 | // destroy rest of instances |
926 | destruct(abegin, d->end()); |
927 | } |
928 | } else { |
929 | destruct(abegin, aend); |
930 | // QTBUG-53605: static_cast<void *> masks clang errors of the form |
931 | // error: destination for this 'memmove' call is a pointer to class containing a dynamic class |
932 | // FIXME maybe use std::is_polymorphic (as soon as allowed) to avoid the memmove |
933 | memmove(static_cast<void *>(abegin), static_cast<void *>(aend), |
934 | (d->size - itemsToErase - itemsUntouched) * sizeof(T)); |
935 | } |
936 | d->size -= int(itemsToErase); |
937 | } |
938 | return d->begin() + itemsUntouched; |
939 | } |
940 | |
941 | template <typename T> |
942 | bool QVector<T>::operator==(const QVector<T> &v) const |
943 | { |
944 | if (d == v.d) |
945 | return true; |
946 | if (d->size != v.d->size) |
947 | return false; |
948 | const T *vb = v.d->begin(); |
949 | const T *b = d->begin(); |
950 | const T *e = d->end(); |
951 | return std::equal(b, e, QT_MAKE_CHECKED_ARRAY_ITERATOR(vb, v.d->size)); |
952 | } |
953 | |
954 | template <typename T> |
955 | QVector<T> &QVector<T>::fill(const T &from, int asize) |
956 | { |
957 | const T copy(from); |
958 | resize(asize < 0 ? d->size : asize); |
959 | if (d->size) { |
960 | T *i = d->end(); |
961 | T *b = d->begin(); |
962 | while (i != b) |
963 | *--i = copy; |
964 | } |
965 | return *this; |
966 | } |
967 | |
968 | template <typename T> |
969 | QVector<T> &QVector<T>::operator+=(const QVector &l) |
970 | { |
971 | if (d->size == 0) { |
972 | *this = l; |
973 | } else { |
974 | uint newSize = d->size + l.d->size; |
975 | const bool isTooSmall = newSize > d->alloc; |
976 | if (!isDetached() || isTooSmall) { |
977 | QArrayData::AllocationOptions opt(isTooSmall ? QArrayData::Grow : QArrayData::Default); |
978 | realloc(isTooSmall ? newSize : d->alloc, opt); |
979 | } |
980 | |
981 | if (d->alloc) { |
982 | T *w = d->begin() + newSize; |
983 | T *i = l.d->end(); |
984 | T *b = l.d->begin(); |
985 | while (i != b) { |
986 | if (QTypeInfo<T>::isComplex) |
987 | new (--w) T(*--i); |
988 | else |
989 | *--w = *--i; |
990 | } |
991 | d->size = newSize; |
992 | } |
993 | } |
994 | return *this; |
995 | } |
996 | |
997 | template <typename T> |
998 | int QVector<T>::indexOf(const T &t, int from) const |
999 | { |
1000 | if (from < 0) |
1001 | from = qMax(from + d->size, 0); |
1002 | if (from < d->size) { |
1003 | T* n = d->begin() + from - 1; |
1004 | T* e = d->end(); |
1005 | while (++n != e) |
1006 | if (*n == t) |
1007 | return n - d->begin(); |
1008 | } |
1009 | return -1; |
1010 | } |
1011 | |
1012 | template <typename T> |
1013 | int QVector<T>::lastIndexOf(const T &t, int from) const |
1014 | { |
1015 | if (from < 0) |
1016 | from += d->size; |
1017 | else if (from >= d->size) |
1018 | from = d->size-1; |
1019 | if (from >= 0) { |
1020 | T* b = d->begin(); |
1021 | T* n = d->begin() + from + 1; |
1022 | while (n != b) { |
1023 | if (*--n == t) |
1024 | return n - b; |
1025 | } |
1026 | } |
1027 | return -1; |
1028 | } |
1029 | |
1030 | template <typename T> |
1031 | bool QVector<T>::contains(const T &t) const |
1032 | { |
1033 | const T *b = d->begin(); |
1034 | const T *e = d->end(); |
1035 | return std::find(b, e, t) != e; |
1036 | } |
1037 | |
1038 | template <typename T> |
1039 | int QVector<T>::count(const T &t) const |
1040 | { |
1041 | const T *b = d->begin(); |
1042 | const T *e = d->end(); |
1043 | return int(std::count(b, e, t)); |
1044 | } |
1045 | |
1046 | template <typename T> |
1047 | Q_OUTOFLINE_TEMPLATE QVector<T> QVector<T>::mid(int pos, int len) const |
1048 | { |
1049 | using namespace QtPrivate; |
1050 | switch (QContainerImplHelper::mid(d->size, &pos, &len)) { |
1051 | case QContainerImplHelper::Null: |
1052 | case QContainerImplHelper::Empty: |
1053 | return QVector<T>(); |
1054 | case QContainerImplHelper::Full: |
1055 | return *this; |
1056 | case QContainerImplHelper::Subset: |
1057 | break; |
1058 | } |
1059 | |
1060 | QVector<T> midResult; |
1061 | midResult.realloc(len); |
1062 | T *srcFrom = d->begin() + pos; |
1063 | T *srcTo = d->begin() + pos + len; |
1064 | midResult.copyConstruct(srcFrom, srcTo, midResult.data()); |
1065 | midResult.d->size = len; |
1066 | return midResult; |
1067 | } |
1068 | |
1069 | Q_DECLARE_SEQUENTIAL_ITERATOR(Vector) |
1070 | Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(Vector) |
1071 | |
1072 | template <typename T> |
1073 | uint qHash(const QVector<T> &key, uint seed = 0) |
1074 | noexcept(noexcept(qHashRange(key.cbegin(), key.cend(), seed))) |
1075 | { |
1076 | return qHashRange(key.cbegin(), key.cend(), seed); |
1077 | } |
1078 | |
1079 | template <typename T> |
1080 | bool operator<(const QVector<T> &lhs, const QVector<T> &rhs) |
1081 | noexcept(noexcept(std::lexicographical_compare(lhs.begin(), lhs.end(), |
1082 | rhs.begin(), rhs.end()))) |
1083 | { |
1084 | return std::lexicographical_compare(lhs.begin(), lhs.end(), |
1085 | rhs.begin(), rhs.end()); |
1086 | } |
1087 | |
1088 | template <typename T> |
1089 | inline bool operator>(const QVector<T> &lhs, const QVector<T> &rhs) |
1090 | noexcept(noexcept(lhs < rhs)) |
1091 | { |
1092 | return rhs < lhs; |
1093 | } |
1094 | |
1095 | template <typename T> |
1096 | inline bool operator<=(const QVector<T> &lhs, const QVector<T> &rhs) |
1097 | noexcept(noexcept(lhs < rhs)) |
1098 | { |
1099 | return !(lhs > rhs); |
1100 | } |
1101 | |
1102 | template <typename T> |
1103 | inline bool operator>=(const QVector<T> &lhs, const QVector<T> &rhs) |
1104 | noexcept(noexcept(lhs < rhs)) |
1105 | { |
1106 | return !(lhs < rhs); |
1107 | } |
1108 | |
1109 | /* |
1110 | ### Qt 5: |
1111 | ### This needs to be removed for next releases of Qt. It is a workaround for vc++ because |
1112 | ### Qt exports QPolygon and QPolygonF that inherit QVector<QPoint> and |
1113 | ### QVector<QPointF> respectively. |
1114 | */ |
1115 | |
1116 | #if defined(Q_CC_MSVC) && !defined(QT_BUILD_CORE_LIB) |
1117 | QT_BEGIN_INCLUDE_NAMESPACE |
1118 | #include <QtCore/qpoint.h> |
1119 | QT_END_INCLUDE_NAMESPACE |
1120 | extern template class Q_CORE_EXPORT QVector<QPointF>; |
1121 | extern template class Q_CORE_EXPORT QVector<QPoint>; |
1122 | #endif |
1123 | |
1124 | QVector<uint> QStringView::toUcs4() const { return QtPrivate::convertToUcs4(*this); } |
1125 | |
1126 | QT_END_NAMESPACE |
1127 | |
1128 | #endif // QVECTOR_H |
1129 | |