Line data Source code
1 : /****************************************************************************
2 : **
3 : ** Copyright (C) 2013 Digia Plc and/or its subsidiary(-ies).
4 : ** Contact: http://www.qt-project.org/legal
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 Digia. For licensing terms and
14 : ** conditions see http://qt.digia.com/licensing. For further information
15 : ** use the contact form at http://qt.digia.com/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 2.1 as published by the Free Software
20 : ** Foundation and appearing in the file LICENSE.LGPL included in the
21 : ** packaging of this file. Please review the following information to
22 : ** ensure the GNU Lesser General Public License version 2.1 requirements
23 : ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
24 : **
25 : ** In addition, as a special exception, Digia gives you certain additional
26 : ** rights. These rights are described in the Digia Qt LGPL Exception
27 : ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
28 : **
29 : ** GNU General Public License Usage
30 : ** Alternatively, this file may be used under the terms of the GNU
31 : ** General Public License version 3.0 as published by the Free Software
32 : ** Foundation and appearing in the file LICENSE.GPL included in the
33 : ** packaging of this file. Please review the following information to
34 : ** ensure the GNU General Public License version 3.0 requirements will be
35 : ** met: http://www.gnu.org/copyleft/gpl.html.
36 : **
37 : **
38 : ** $QT_END_LICENSE$
39 : **
40 : ****************************************************************************/
41 :
42 : #ifndef QVECTOR_H
43 : #define QVECTOR_H
44 :
45 : #include <QtCore/qalgorithms.h>
46 : #include <QtCore/qiterator.h>
47 : #include <QtCore/qlist.h>
48 : #include <QtCore/qrefcount.h>
49 : #include <QtCore/qarraydata.h>
50 :
51 : #include <iterator>
52 : #include <vector>
53 : #include <stdlib.h>
54 : #include <string.h>
55 : #ifdef Q_COMPILER_INITIALIZER_LISTS
56 : #include <initializer_list>
57 : #endif
58 :
59 : #include <algorithm>
60 :
61 : QT_BEGIN_NAMESPACE
62 :
63 : class QRegion;
64 :
65 : template <typename T>
66 : class QVector
67 : {
68 : typedef QTypedArrayData<T> Data;
69 : Data *d;
70 :
71 : public:
72 5 : inline QVector() : d(Data::sharedNull()) { }
73 : explicit QVector(int size);
74 : QVector(int size, const T &t);
75 : inline QVector(const QVector<T> &v);
76 5 : inline ~QVector() { if (!d->ref.deref()) freeData(d); }
77 : QVector<T> &operator=(const QVector<T> &v);
78 : #ifdef Q_COMPILER_RVALUE_REFS
79 : inline QVector(QVector<T> &&other) : d(other.d) { other.d = Data::sharedNull(); }
80 : inline QVector<T> operator=(QVector<T> &&other)
81 : { qSwap(d, other.d); return *this; }
82 : #endif
83 : inline void swap(QVector<T> &other) { qSwap(d, other.d); }
84 : #ifdef Q_COMPILER_INITIALIZER_LISTS
85 : inline QVector(std::initializer_list<T> args);
86 : #endif
87 : bool operator==(const QVector<T> &v) const;
88 : inline bool operator!=(const QVector<T> &v) const { return !(*this == v); }
89 :
90 : inline int size() const { return d->size; }
91 :
92 : inline bool isEmpty() const { return d->size == 0; }
93 :
94 : void resize(int size);
95 :
96 5 : inline int capacity() const { return int(d->alloc); }
97 : void reserve(int size);
98 : inline void squeeze()
99 : {
100 : reallocData(d->size, d->size);
101 : if (d->capacityReserved) {
102 : // capacity reserved in a read only memory would be useless
103 : // this checks avoid writing to such memory.
104 : d->capacityReserved = 0;
105 : }
106 : }
107 :
108 : inline void detach();
109 5 : inline bool isDetached() const { return !d->ref.isShared(); }
110 : #if QT_SUPPORTS(UNSHARABLE_CONTAINERS)
111 : inline void setSharable(bool sharable)
112 : {
113 : if (sharable == d->ref.isSharable())
114 : return;
115 : if (!sharable)
116 : detach();
117 :
118 : if (d == Data::unsharableEmpty()) {
119 : if (sharable)
120 : d = Data::sharedNull();
121 : } else {
122 : d->ref.setSharable(sharable);
123 : }
124 : Q_ASSERT(d->ref.isSharable() == sharable);
125 : }
126 : #endif
127 :
128 : inline bool isSharedWith(const QVector<T> &other) const { return d == other.d; }
129 :
130 : inline T *data() { detach(); return d->begin(); }
131 : inline const T *data() const { return d->begin(); }
132 : inline const T *constData() const { return d->begin(); }
133 : void clear();
134 :
135 : const T &at(int i) const;
136 : T &operator[](int i);
137 : const T &operator[](int i) const;
138 : void append(const T &t);
139 : void prepend(const T &t);
140 : void insert(int i, const T &t);
141 : void insert(int i, int n, const T &t);
142 : void replace(int i, const T &t);
143 : void remove(int i);
144 : void remove(int i, int n);
145 : inline void removeFirst() { Q_ASSERT(!isEmpty()); erase(d->begin()); }
146 : inline void removeLast();
147 : inline T takeFirst() { Q_ASSERT(!isEmpty()); T r = first(); removeFirst(); return r; }
148 : inline T takeLast() { Q_ASSERT(!isEmpty()); T r = last(); removeLast(); return r; }
149 :
150 : QVector<T> &fill(const T &t, int size = -1);
151 :
152 : int indexOf(const T &t, int from = 0) const;
153 : int lastIndexOf(const T &t, int from = -1) const;
154 : bool contains(const T &t) const;
155 : int count(const T &t) const;
156 :
157 : // QList compatibility
158 : void removeAt(int i) { remove(i); }
159 : int length() const { return size(); }
160 : T takeAt(int i) { T t = at(i); remove(i); return t; }
161 :
162 : // STL-style
163 : typedef typename Data::iterator iterator;
164 : typedef typename Data::const_iterator const_iterator;
165 : #if !defined(QT_STRICT_ITERATORS) || defined(Q_QDOC)
166 : inline iterator begin() { detach(); return d->begin(); }
167 : inline const_iterator begin() const { return d->constBegin(); }
168 : inline const_iterator cbegin() const { return d->constBegin(); }
169 : inline const_iterator constBegin() const { return d->constBegin(); }
170 : inline iterator end() { detach(); return d->end(); }
171 : inline const_iterator end() const { return d->constEnd(); }
172 : inline const_iterator cend() const { return d->constEnd(); }
173 : inline const_iterator constEnd() const { return d->constEnd(); }
174 : #else
175 : inline iterator begin(iterator = iterator()) { detach(); return d->begin(); }
176 : inline const_iterator begin(const_iterator = const_iterator()) const { return d->constBegin(); }
177 : inline const_iterator cbegin(const_iterator = const_iterator()) const { return d->constBegin(); }
178 : inline const_iterator constBegin(const_iterator = const_iterator()) const { return d->constBegin(); }
179 : inline iterator end(iterator = iterator()) { detach(); return d->end(); }
180 : inline const_iterator end(const_iterator = const_iterator()) const { return d->constEnd(); }
181 : inline const_iterator cend(const_iterator = const_iterator()) const { return d->constEnd(); }
182 : inline const_iterator constEnd(const_iterator = const_iterator()) const { return d->constEnd(); }
183 : #endif
184 : iterator insert(iterator before, int n, const T &x);
185 : inline iterator insert(iterator before, const T &x) { return insert(before, 1, x); }
186 : iterator erase(iterator begin, iterator end);
187 : inline iterator erase(iterator pos) { return erase(pos, pos+1); }
188 :
189 : // more Qt
190 12 : inline int count() const { return d->size; }
191 : inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); }
192 : inline const T &first() const { Q_ASSERT(!isEmpty()); return *begin(); }
193 : inline T& last() { Q_ASSERT(!isEmpty()); return *(end()-1); }
194 : inline const T &last() const { Q_ASSERT(!isEmpty()); return *(end()-1); }
195 : inline bool startsWith(const T &t) const { return !isEmpty() && first() == t; }
196 : inline bool endsWith(const T &t) const { return !isEmpty() && last() == t; }
197 : QVector<T> mid(int pos, int len = -1) const;
198 :
199 : T value(int i) const;
200 : T value(int i, const T &defaultValue) const;
201 :
202 : // STL compatibility
203 : typedef T value_type;
204 : typedef value_type* pointer;
205 : typedef const value_type* const_pointer;
206 : typedef value_type& reference;
207 : typedef const value_type& const_reference;
208 : typedef qptrdiff difference_type;
209 : typedef iterator Iterator;
210 : typedef const_iterator ConstIterator;
211 : typedef int size_type;
212 : inline void push_back(const T &t) { append(t); }
213 : inline void push_front(const T &t) { prepend(t); }
214 : void pop_back() { removeLast(); }
215 : void pop_front() { removeFirst(); }
216 : inline bool empty() const
217 : { return d->size == 0; }
218 : inline T& front() { return first(); }
219 : inline const_reference front() const { return first(); }
220 : inline reference back() { return last(); }
221 : inline const_reference back() const { return last(); }
222 :
223 : // comfort
224 : QVector<T> &operator+=(const QVector<T> &l);
225 : inline QVector<T> operator+(const QVector<T> &l) const
226 : { QVector n = *this; n += l; return n; }
227 : inline QVector<T> &operator+=(const T &t)
228 : { append(t); return *this; }
229 0 : inline QVector<T> &operator<< (const T &t)
230 0 : { append(t); return *this; }
231 : inline QVector<T> &operator<<(const QVector<T> &l)
232 : { *this += l; return *this; }
233 :
234 : QList<T> toList() const;
235 :
236 : static QVector<T> fromList(const QList<T> &list);
237 :
238 : static inline QVector<T> fromStdVector(const std::vector<T> &vector)
239 : { QVector<T> tmp; tmp.reserve(int(vector.size())); std::copy(vector.begin(), vector.end(), std::back_inserter(tmp)); return tmp; }
240 : inline std::vector<T> toStdVector() const
241 : { std::vector<T> tmp; tmp.reserve(size()); std::copy(constBegin(), constEnd(), std::back_inserter(tmp)); return tmp; }
242 : private:
243 : friend class QRegion; // Optimization for QRegion::rects()
244 :
245 : void reallocData(const int size, const int alloc, QArrayData::AllocationOptions options = QArrayData::Default);
246 : void reallocData(const int sz) { reallocData(sz, d->alloc); }
247 : void freeData(Data *d);
248 : void defaultConstruct(T *from, T *to);
249 : void copyConstruct(const T *srcFrom, const T *srcTo, T *dstFrom);
250 : void destruct(T *from, T *to);
251 : bool isValidIterator(const iterator &i) const
252 : {
253 : return (i <= d->end()) && (d->begin() <= i);
254 : }
255 : class AlignmentDummy { Data header; T array[1]; };
256 : };
257 :
258 : #ifdef Q_CC_MSVC
259 : // behavior change: an object of POD type constructed with an initializer of the form ()
260 : // will be default-initialized
261 : # pragma warning ( push )
262 : # pragma warning ( disable : 4345 )
263 : #endif
264 :
265 : template <typename T>
266 0 : void QVector<T>::defaultConstruct(T *from, T *to)
267 : {
268 : if (QTypeInfo<T>::isComplex) {
269 : while (from != to) {
270 : new (from++) T();
271 : }
272 : } else {
273 0 : ::memset(static_cast<void *>(from), 0, (to - from) * sizeof(T));
274 : }
275 0 : }
276 :
277 : #ifdef Q_CC_MSVC
278 : # pragma warning ( pop )
279 : #endif
280 :
281 : template <typename T>
282 : void QVector<T>::copyConstruct(const T *srcFrom, const T *srcTo, T *dstFrom)
283 : {
284 : if (QTypeInfo<T>::isComplex) {
285 : while (srcFrom != srcTo)
286 : new (dstFrom++) T(*srcFrom++);
287 : } else {
288 : ::memcpy(static_cast<void *>(dstFrom), static_cast<const void *>(srcFrom), (srcTo - srcFrom) * sizeof(T));
289 : }
290 : }
291 :
292 : #if defined(Q_CC_MSVC)
293 : #pragma warning( push )
294 : #pragma warning( disable : 4127 ) // conditional expression is constant
295 : #endif
296 :
297 : template <typename T>
298 0 : void QVector<T>::destruct(T *from, T *to)
299 : {
300 : if (QTypeInfo<T>::isComplex) {
301 : while (from != to) {
302 : from++->~T();
303 : }
304 : }
305 0 : }
306 :
307 : #if defined(Q_CC_MSVC)
308 : #pragma warning( pop )
309 : #endif
310 :
311 : template <typename T>
312 : inline QVector<T>::QVector(const QVector<T> &v)
313 : {
314 : if (v.d->ref.ref()) {
315 : d = v.d;
316 : } else {
317 : if (v.d->capacityReserved) {
318 : d = Data::allocate(v.d->alloc);
319 : d->capacityReserved = true;
320 : } else {
321 : d = Data::allocate(v.d->size);
322 : }
323 : if (d->alloc) {
324 : copyConstruct(v.d->begin(), v.d->end(), d->begin());
325 : d->size = v.d->size;
326 : }
327 : }
328 : }
329 :
330 : template <typename T>
331 : void QVector<T>::detach()
332 : {
333 : if (!isDetached()) {
334 : #if QT_SUPPORTS(UNSHARABLE_CONTAINERS)
335 : if (!d->alloc)
336 : d = Data::unsharableEmpty();
337 : else
338 : #endif
339 : reallocData(d->size, int(d->alloc));
340 : }
341 : Q_ASSERT(isDetached());
342 : }
343 :
344 : template <typename T>
345 5 : void QVector<T>::reserve(int asize)
346 : {
347 5 : if (asize > int(d->alloc))
348 0 : reallocData(d->size, asize);
349 5 : if (isDetached())
350 0 : d->capacityReserved = 1;
351 5 : Q_ASSERT(capacity() >= asize);
352 5 : }
353 :
354 : template <typename T>
355 : void QVector<T>::resize(int asize)
356 : {
357 : int newAlloc;
358 : const int oldAlloc = int(d->alloc);
359 : QArrayData::AllocationOptions opt;
360 :
361 : if (asize > oldAlloc) { // there is not enough space
362 : newAlloc = asize;
363 : opt = QArrayData::Grow;
364 : } else if (!d->capacityReserved && asize < d->size && asize < (oldAlloc >> 1)) { // we want to shrink
365 : newAlloc = asize;
366 : opt = QArrayData::Grow;
367 : } else {
368 : newAlloc = oldAlloc;
369 : }
370 : reallocData(asize, newAlloc, opt);
371 : }
372 : template <typename T>
373 : inline void QVector<T>::clear()
374 : { *this = QVector<T>(); }
375 : template <typename T>
376 0 : inline const T &QVector<T>::at(int i) const
377 0 : { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::at", "index out of range");
378 0 : return d->begin()[i]; }
379 : template <typename T>
380 : inline const T &QVector<T>::operator[](int i) const
381 : { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]", "index out of range");
382 : return d->begin()[i]; }
383 : template <typename T>
384 : inline T &QVector<T>::operator[](int i)
385 : { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]", "index out of range");
386 : return data()[i]; }
387 : template <typename T>
388 : inline void QVector<T>::insert(int i, const T &t)
389 : { Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert", "index out of range");
390 : insert(begin() + i, 1, t); }
391 : template <typename T>
392 : inline void QVector<T>::insert(int i, int n, const T &t)
393 : { Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert", "index out of range");
394 : insert(begin() + i, n, t); }
395 : template <typename T>
396 : inline void QVector<T>::remove(int i, int n)
397 : { Q_ASSERT_X(i >= 0 && n >= 0 && i + n <= d->size, "QVector<T>::remove", "index out of range");
398 : erase(d->begin() + i, d->begin() + i + n); }
399 : template <typename T>
400 : inline void QVector<T>::remove(int i)
401 : { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::remove", "index out of range");
402 : erase(d->begin() + i, d->begin() + i + 1); }
403 : template <typename T>
404 : inline void QVector<T>::prepend(const T &t)
405 : { insert(begin(), 1, t); }
406 :
407 : template <typename T>
408 : inline void QVector<T>::replace(int i, const T &t)
409 : {
410 : Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::replace", "index out of range");
411 : const T copy(t);
412 : data()[i] = copy;
413 : }
414 :
415 : template <typename T>
416 : QVector<T> &QVector<T>::operator=(const QVector<T> &v)
417 : {
418 : if (v.d != d) {
419 : QVector<T> tmp(v);
420 : tmp.swap(*this);
421 : }
422 : return *this;
423 : }
424 :
425 : template <typename T>
426 : QVector<T>::QVector(int asize)
427 : {
428 : Q_ASSERT_X(asize >= 0, "QVector::QVector", "Size must be greater than or equal to 0.");
429 : if (Q_LIKELY(asize > 0)) {
430 : d = Data::allocate(asize);
431 : d->size = asize;
432 : defaultConstruct(d->begin(), d->end());
433 : } else {
434 : d = Data::sharedNull();
435 : }
436 : }
437 :
438 : template <typename T>
439 : QVector<T>::QVector(int asize, const T &t)
440 : {
441 : Q_ASSERT_X(asize >= 0, "QVector::QVector", "Size must be greater than or equal to 0.");
442 : if (asize > 0) {
443 : d = Data::allocate(asize);
444 : d->size = asize;
445 : T* i = d->end();
446 : while (i != d->begin())
447 : new (--i) T(t);
448 : } else {
449 : d = Data::sharedNull();
450 : }
451 : }
452 :
453 : #ifdef Q_COMPILER_INITIALIZER_LISTS
454 : template <typename T>
455 : QVector<T>::QVector(std::initializer_list<T> args)
456 : {
457 : if (args.size() > 0) {
458 : d = Data::allocate(args.size());
459 : // std::initializer_list<T>::iterator is guaranteed to be
460 : // const T* ([support.initlist]/1), so can be memcpy'ed away from by copyConstruct
461 : copyConstruct(args.begin(), args.end(), d->begin());
462 : d->size = int(args.size());
463 : } else {
464 : d = Data::sharedNull();
465 : }
466 : }
467 : #endif
468 :
469 : template <typename T>
470 0 : void QVector<T>::freeData(Data *x)
471 : {
472 0 : destruct(x->begin(), x->end());
473 0 : Data::deallocate(x);
474 0 : }
475 :
476 : template <typename T>
477 0 : void QVector<T>::reallocData(const int asize, const int aalloc, QArrayData::AllocationOptions options)
478 : {
479 0 : Q_ASSERT(asize >= 0 && asize <= aalloc);
480 0 : Data *x = d;
481 :
482 0 : const bool isShared = d->ref.isShared();
483 :
484 0 : if (aalloc != 0) {
485 0 : if (aalloc != int(d->alloc) || isShared) {
486 : QT_TRY {
487 : // allocate memory
488 0 : x = Data::allocate(aalloc, options);
489 0 : Q_CHECK_PTR(x);
490 : // aalloc is bigger then 0 so it is not [un]sharedEmpty
491 : #if QT_SUPPORTS(UNSHARABLE_CONTAINERS)
492 0 : Q_ASSERT(x->ref.isSharable() || options.testFlag(QArrayData::Unsharable));
493 : #endif
494 0 : Q_ASSERT(!x->ref.isStatic());
495 0 : x->size = asize;
496 :
497 0 : T *srcBegin = d->begin();
498 0 : T *srcEnd = asize > d->size ? d->end() : d->begin() + asize;
499 0 : T *dst = x->begin();
500 :
501 : if (QTypeInfo<T>::isStatic || (isShared && QTypeInfo<T>::isComplex)) {
502 : // we can not move the data, we need to copy construct it
503 : while (srcBegin != srcEnd) {
504 : new (dst++) T(*srcBegin++);
505 : }
506 : } else {
507 0 : ::memcpy(static_cast<void *>(dst), static_cast<void *>(srcBegin), (srcEnd - srcBegin) * sizeof(T));
508 0 : dst += srcEnd - srcBegin;
509 :
510 : // destruct unused / not moved data
511 0 : if (asize < d->size)
512 0 : destruct(d->begin() + asize, d->end());
513 : }
514 :
515 0 : if (asize > d->size) {
516 : // construct all new objects when growing
517 : QT_TRY {
518 0 : defaultConstruct(dst, x->end());
519 0 : } QT_CATCH (...) {
520 : // destruct already copied objects
521 0 : destruct(x->begin(), dst);
522 0 : QT_RETHROW;
523 : }
524 : }
525 0 : } QT_CATCH (...) {
526 0 : Data::deallocate(x);
527 0 : QT_RETHROW;
528 : }
529 0 : x->capacityReserved = d->capacityReserved;
530 : } else {
531 0 : Q_ASSERT(int(d->alloc) == aalloc); // resize, without changing allocation size
532 0 : Q_ASSERT(isDetached()); // can be done only on detached d
533 0 : Q_ASSERT(x == d); // in this case we do not need to allocate anything
534 0 : if (asize <= d->size) {
535 0 : destruct(x->begin() + asize, x->end()); // from future end to current end
536 : } else {
537 0 : defaultConstruct(x->end(), x->begin() + asize); // from current end to future end
538 : }
539 0 : x->size = asize;
540 : }
541 : } else {
542 0 : x = Data::sharedNull();
543 : }
544 0 : if (d != x) {
545 0 : if (!d->ref.deref()) {
546 0 : if (QTypeInfo<T>::isStatic || !aalloc || (isShared && QTypeInfo<T>::isComplex)) {
547 : // data was copy constructed, we need to call destructors
548 : // or if !alloc we did nothing to the old 'd'.
549 0 : freeData(d);
550 : } else {
551 0 : Data::deallocate(d);
552 : }
553 : }
554 0 : d = x;
555 : }
556 :
557 0 : Q_ASSERT(d->data());
558 0 : Q_ASSERT(uint(d->size) <= d->alloc);
559 : #if QT_SUPPORTS(UNSHARABLE_CONTAINERS)
560 0 : Q_ASSERT(d != Data::unsharableEmpty());
561 : #endif
562 0 : Q_ASSERT(aalloc ? d != Data::sharedNull() : d == Data::sharedNull());
563 0 : Q_ASSERT(d->alloc >= uint(aalloc));
564 0 : Q_ASSERT(d->size == asize);
565 0 : }
566 :
567 : template<typename T>
568 : Q_OUTOFLINE_TEMPLATE T QVector<T>::value(int i) const
569 : {
570 : if (uint(i) >= uint(d->size)) {
571 : return T();
572 : }
573 : return d->begin()[i];
574 : }
575 : template<typename T>
576 : Q_OUTOFLINE_TEMPLATE T QVector<T>::value(int i, const T &defaultValue) const
577 : {
578 : return uint(i) >= uint(d->size) ? defaultValue : d->begin()[i];
579 : }
580 :
581 : template <typename T>
582 0 : void QVector<T>::append(const T &t)
583 : {
584 0 : const T copy(t);
585 0 : const bool isTooSmall = uint(d->size + 1) > d->alloc;
586 0 : if (!isDetached() || isTooSmall) {
587 0 : QArrayData::AllocationOptions opt(isTooSmall ? QArrayData::Grow : QArrayData::Default);
588 0 : reallocData(d->size, isTooSmall ? d->size + 1 : d->alloc, opt);
589 : }
590 : if (QTypeInfo<T>::isComplex)
591 : new (d->end()) T(copy);
592 : else
593 0 : *d->end() = copy;
594 0 : ++d->size;
595 0 : }
596 :
597 : template <typename T>
598 : void QVector<T>::removeLast()
599 : {
600 : Q_ASSERT(!isEmpty());
601 : Q_ASSERT(d->alloc);
602 :
603 : if (!d->ref.isShared()) {
604 : --d->size;
605 : if (QTypeInfo<T>::isComplex)
606 : (d->data() + d->size)->~T();
607 : } else {
608 : reallocData(d->size - 1);
609 : }
610 : }
611 :
612 : template <typename T>
613 : typename QVector<T>::iterator QVector<T>::insert(iterator before, size_type n, const T &t)
614 : {
615 : Q_ASSERT_X(isValidIterator(before), "QVector::insert", "The specified iterator argument 'before' is invalid");
616 :
617 : int offset = std::distance(d->begin(), before);
618 : if (n != 0) {
619 : const T copy(t);
620 : if (!isDetached() || d->size + n > int(d->alloc))
621 : reallocData(d->size, d->size + n, QArrayData::Grow);
622 : if (QTypeInfo<T>::isStatic) {
623 : T *b = d->end();
624 : T *i = d->end() + n;
625 : while (i != b)
626 : new (--i) T;
627 : i = d->end();
628 : T *j = i + n;
629 : b = d->begin() + offset;
630 : while (i != b)
631 : *--j = *--i;
632 : i = b+n;
633 : while (i != b)
634 : *--i = copy;
635 : } else {
636 : T *b = d->begin() + offset;
637 : T *i = b + n;
638 : memmove(i, b, (d->size - offset) * sizeof(T));
639 : while (i != b)
640 : new (--i) T(copy);
641 : }
642 : d->size += n;
643 : }
644 : return d->begin() + offset;
645 : }
646 :
647 : template <typename T>
648 : typename QVector<T>::iterator QVector<T>::erase(iterator abegin, iterator aend)
649 : {
650 : Q_ASSERT_X(isValidIterator(abegin), "QVector::erase", "The specified iterator argument 'abegin' is invalid");
651 : Q_ASSERT_X(isValidIterator(aend), "QVector::erase", "The specified iterator argument 'aend' is invalid");
652 :
653 : const int itemsToErase = aend - abegin;
654 :
655 : if (!itemsToErase)
656 : return abegin;
657 :
658 : Q_ASSERT(abegin >= d->begin());
659 : Q_ASSERT(aend <= d->end());
660 : Q_ASSERT(abegin <= aend);
661 :
662 : const int itemsUntouched = abegin - d->begin();
663 :
664 : // FIXME we could do a proper realloc, which copy constructs only needed data.
665 : // FIXME we ara about to delete data maybe it is good time to shrink?
666 : // FIXME the shrink is also an issue in removeLast, that is just a copy + reduce of this.
667 : if (d->alloc) {
668 : detach();
669 : abegin = d->begin() + itemsUntouched;
670 : aend = abegin + itemsToErase;
671 : if (QTypeInfo<T>::isStatic) {
672 : iterator moveBegin = abegin + itemsToErase;
673 : iterator moveEnd = d->end();
674 : while (moveBegin != moveEnd) {
675 : if (QTypeInfo<T>::isComplex)
676 : static_cast<T *>(abegin)->~T();
677 : new (abegin++) T(*moveBegin++);
678 : }
679 : if (abegin < d->end()) {
680 : // destroy rest of instances
681 : destruct(abegin, d->end());
682 : }
683 : } else {
684 : destruct(abegin, aend);
685 : memmove(abegin, aend, (d->size - itemsToErase - itemsUntouched) * sizeof(T));
686 : }
687 : d->size -= itemsToErase;
688 : }
689 : return d->begin() + itemsUntouched;
690 : }
691 :
692 : template <typename T>
693 : bool QVector<T>::operator==(const QVector<T> &v) const
694 : {
695 : if (d->size != v.d->size)
696 : return false;
697 : if (d == v.d)
698 : return true;
699 : T* b = d->begin();
700 : T* i = b + d->size;
701 : T* j = v.d->end();
702 : while (i != b)
703 : if (!(*--i == *--j))
704 : return false;
705 : return true;
706 : }
707 :
708 : template <typename T>
709 : QVector<T> &QVector<T>::fill(const T &from, int asize)
710 : {
711 : const T copy(from);
712 : resize(asize < 0 ? d->size : asize);
713 : if (d->size) {
714 : T *i = d->end();
715 : T *b = d->begin();
716 : while (i != b)
717 : *--i = copy;
718 : }
719 : return *this;
720 : }
721 :
722 : template <typename T>
723 : QVector<T> &QVector<T>::operator+=(const QVector &l)
724 : {
725 : uint newSize = d->size + l.d->size;
726 : const bool isTooSmall = newSize > d->alloc;
727 : if (!isDetached() || isTooSmall) {
728 : QArrayData::AllocationOptions opt(isTooSmall ? QArrayData::Grow : QArrayData::Default);
729 : reallocData(d->size, isTooSmall ? newSize : d->alloc, opt);
730 : }
731 :
732 : if (d->alloc) {
733 : T *w = d->begin() + newSize;
734 : T *i = l.d->end();
735 : T *b = l.d->begin();
736 : while (i != b) {
737 : if (QTypeInfo<T>::isComplex)
738 : new (--w) T(*--i);
739 : else
740 : *--w = *--i;
741 : }
742 : d->size = newSize;
743 : }
744 : return *this;
745 : }
746 :
747 : template <typename T>
748 : int QVector<T>::indexOf(const T &t, int from) const
749 : {
750 : if (from < 0)
751 : from = qMax(from + d->size, 0);
752 : if (from < d->size) {
753 : T* n = d->begin() + from - 1;
754 : T* e = d->end();
755 : while (++n != e)
756 : if (*n == t)
757 : return n - d->begin();
758 : }
759 : return -1;
760 : }
761 :
762 : template <typename T>
763 : int QVector<T>::lastIndexOf(const T &t, int from) const
764 : {
765 : if (from < 0)
766 : from += d->size;
767 : else if (from >= d->size)
768 : from = d->size-1;
769 : if (from >= 0) {
770 : T* b = d->begin();
771 : T* n = d->begin() + from + 1;
772 : while (n != b) {
773 : if (*--n == t)
774 : return n - b;
775 : }
776 : }
777 : return -1;
778 : }
779 :
780 : template <typename T>
781 : bool QVector<T>::contains(const T &t) const
782 : {
783 : T* b = d->begin();
784 : T* i = d->end();
785 : while (i != b)
786 : if (*--i == t)
787 : return true;
788 : return false;
789 : }
790 :
791 : template <typename T>
792 : int QVector<T>::count(const T &t) const
793 : {
794 : int c = 0;
795 : T* b = d->begin();
796 : T* i = d->end();
797 : while (i != b)
798 : if (*--i == t)
799 : ++c;
800 : return c;
801 : }
802 :
803 : template <typename T>
804 : Q_OUTOFLINE_TEMPLATE QVector<T> QVector<T>::mid(int pos, int len) const
805 : {
806 : if (len < 0)
807 : len = size() - pos;
808 : if (pos == 0 && len == size())
809 : return *this;
810 : if (pos + len > size())
811 : len = size() - pos;
812 : QVector<T> copy;
813 : copy.reserve(len);
814 : for (int i = pos; i < pos + len; ++i)
815 : copy += at(i);
816 : return copy;
817 : }
818 :
819 : template <typename T>
820 : Q_OUTOFLINE_TEMPLATE QList<T> QVector<T>::toList() const
821 : {
822 : QList<T> result;
823 : result.reserve(size());
824 : for (int i = 0; i < size(); ++i)
825 : result.append(at(i));
826 : return result;
827 : }
828 :
829 : template <typename T>
830 : Q_OUTOFLINE_TEMPLATE QVector<T> QList<T>::toVector() const
831 : {
832 : QVector<T> result(size());
833 : for (int i = 0; i < size(); ++i)
834 : result[i] = at(i);
835 : return result;
836 : }
837 :
838 : template <typename T>
839 : QVector<T> QVector<T>::fromList(const QList<T> &list)
840 : {
841 : return list.toVector();
842 : }
843 :
844 : template <typename T>
845 : QList<T> QList<T>::fromVector(const QVector<T> &vector)
846 : {
847 : return vector.toList();
848 : }
849 :
850 : Q_DECLARE_SEQUENTIAL_ITERATOR(Vector)
851 : Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(Vector)
852 :
853 : /*
854 : ### Qt 5:
855 : ### This needs to be removed for next releases of Qt. It is a workaround for vc++ because
856 : ### Qt exports QPolygon and QPolygonF that inherit QVector<QPoint> and
857 : ### QVector<QPointF> respectively.
858 : */
859 :
860 : #ifdef Q_CC_MSVC
861 : QT_BEGIN_INCLUDE_NAMESPACE
862 : #include <QtCore/qpoint.h>
863 : QT_END_INCLUDE_NAMESPACE
864 :
865 : #if defined(QT_BUILD_CORE_LIB)
866 : #define Q_TEMPLATE_EXTERN
867 : #else
868 : #define Q_TEMPLATE_EXTERN extern
869 : #endif
870 : Q_TEMPLATE_EXTERN template class Q_CORE_EXPORT QVector<QPointF>;
871 : Q_TEMPLATE_EXTERN template class Q_CORE_EXPORT QVector<QPoint>;
872 : #endif
873 :
874 : QT_END_NAMESPACE
875 :
876 : #endif // QVECTOR_H
|
