1 /****************************************************************************
3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
4 ** Contact: http://www.qt-project.org/
6 ** This file is part of the QtCore module of the Qt Toolkit.
8 ** $QT_BEGIN_LICENSE:LGPL$
9 ** GNU Lesser General Public License Usage
10 ** This file may be used under the terms of the GNU Lesser General Public
11 ** License version 2.1 as published by the Free Software Foundation and
12 ** appearing in the file LICENSE.LGPL included in the packaging of this
13 ** file. Please review the following information to ensure the GNU Lesser
14 ** General Public License version 2.1 requirements will be met:
15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
17 ** In addition, as a special exception, Nokia gives you certain additional
18 ** rights. These rights are described in the Nokia Qt LGPL Exception
19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
21 ** GNU General Public License Usage
22 ** Alternatively, this file may be used under the terms of the GNU General
23 ** Public License version 3.0 as published by the Free Software Foundation
24 ** and appearing in the file LICENSE.GPL included in the packaging of this
25 ** file. Please review the following information to ensure the GNU General
26 ** Public License version 3.0 requirements will be met:
27 ** http://www.gnu.org/copyleft/gpl.html.
30 ** Alternatively, this file may be used in accordance with the terms and
31 ** conditions contained in a signed written agreement between you and Nokia.
40 ****************************************************************************/
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>
55 #ifdef Q_COMPILER_INITIALIZER_LISTS
56 #include <initializer_list>
68 typedef QTypedArrayData<T> Data;
72 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 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; }
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);
87 bool operator==(const QVector<T> &v) const;
88 inline bool operator!=(const QVector<T> &v) const { return !(*this == v); }
90 inline int size() const { return d->size; }
92 inline bool isEmpty() const { return d->size == 0; }
94 void resize(int size);
96 inline int capacity() const { return int(d->alloc); }
97 void reserve(int size);
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;
108 inline void detach();
109 inline bool isDetached() const { return !d->ref.isShared(); }
110 inline void setSharable(bool sharable)
112 if (sharable == d->ref.isSharable())
117 if (d == Data::unsharableEmpty()) {
119 d = Data::sharedNull();
121 d->ref.setSharable(sharable);
123 Q_ASSERT(d->ref.isSharable() == sharable);
126 inline bool isSharedWith(const QVector<T> &other) const { return d == other.d; }
128 inline T *data() { detach(); return d->begin(); }
129 inline const T *data() const { return d->begin(); }
130 inline const T *constData() const { return d->begin(); }
133 const T &at(int i) const;
134 T &operator[](int i);
135 const T &operator[](int i) const;
136 void append(const T &t);
137 void prepend(const T &t);
138 void insert(int i, const T &t);
139 void insert(int i, int n, const T &t);
140 void replace(int i, const T &t);
142 void remove(int i, int n);
144 QVector<T> &fill(const T &t, int size = -1);
146 int indexOf(const T &t, int from = 0) const;
147 int lastIndexOf(const T &t, int from = -1) const;
148 bool contains(const T &t) const;
149 int count(const T &t) const;
152 typedef typename Data::iterator iterator;
153 typedef typename Data::const_iterator const_iterator;
154 inline iterator begin() { detach(); return d->begin(); }
155 inline const_iterator begin() const { return d->constBegin(); }
156 inline const_iterator cbegin() const { return d->constBegin(); }
157 inline const_iterator constBegin() const { return d->constBegin(); }
158 inline iterator end() { detach(); return d->end(); }
159 inline const_iterator end() const { return d->constEnd(); }
160 inline const_iterator cend() const { return d->constEnd(); }
161 inline const_iterator constEnd() const { return d->constEnd(); }
162 iterator insert(iterator before, int n, const T &x);
163 inline iterator insert(iterator before, const T &x) { return insert(before, 1, x); }
164 iterator erase(iterator begin, iterator end);
165 inline iterator erase(iterator pos) { return erase(pos, pos+1); }
168 inline int count() const { return d->size; }
169 inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); }
170 inline const T &first() const { Q_ASSERT(!isEmpty()); return *begin(); }
171 inline T& last() { Q_ASSERT(!isEmpty()); return *(end()-1); }
172 inline const T &last() const { Q_ASSERT(!isEmpty()); return *(end()-1); }
173 inline bool startsWith(const T &t) const { return !isEmpty() && first() == t; }
174 inline bool endsWith(const T &t) const { return !isEmpty() && last() == t; }
175 QVector<T> mid(int pos, int length = -1) const;
177 T value(int i) const;
178 T value(int i, const T &defaultValue) const;
181 typedef T value_type;
182 typedef value_type* pointer;
183 typedef const value_type* const_pointer;
184 typedef value_type& reference;
185 typedef const value_type& const_reference;
186 typedef qptrdiff difference_type;
187 typedef iterator Iterator;
188 typedef const_iterator ConstIterator;
189 typedef int size_type;
190 inline void push_back(const T &t) { append(t); }
191 inline void push_front(const T &t) { prepend(t); }
192 void pop_back() { Q_ASSERT(!isEmpty()); erase(end()-1); }
193 void pop_front() { Q_ASSERT(!isEmpty()); erase(begin()); }
194 inline bool empty() const
195 { return d->size == 0; }
196 inline T& front() { return first(); }
197 inline const_reference front() const { return first(); }
198 inline reference back() { return last(); }
199 inline const_reference back() const { return last(); }
202 QVector<T> &operator+=(const QVector<T> &l);
203 inline QVector<T> operator+(const QVector<T> &l) const
204 { QVector n = *this; n += l; return n; }
205 inline QVector<T> &operator+=(const T &t)
206 { append(t); return *this; }
207 inline QVector<T> &operator<< (const T &t)
208 { append(t); return *this; }
209 inline QVector<T> &operator<<(const QVector<T> &l)
210 { *this += l; return *this; }
212 QList<T> toList() const;
214 static QVector<T> fromList(const QList<T> &list);
216 static inline QVector<T> fromStdVector(const std::vector<T> &vector)
217 { QVector<T> tmp; tmp.reserve(int(vector.size())); qCopy(vector.begin(), vector.end(), std::back_inserter(tmp)); return tmp; }
218 inline std::vector<T> toStdVector() const
219 { std::vector<T> tmp; tmp.reserve(size()); qCopy(constBegin(), constEnd(), std::back_inserter(tmp)); return tmp; }
221 friend class QRegion; // Optimization for QRegion::rects()
223 void reallocData(const int size, const int alloc, QArrayData::AllocationOptions options = QArrayData::Default);
224 void freeData(Data *d);
225 void defaultConstruct(T *from, T *to);
226 void copyConstruct(const T *srcFrom, const T *srcTo, T *dstFrom);
227 void destruct(T *from, T *to);
229 class AlignmentDummy { Data header; T array[1]; };
233 # pragma warning ( disable : 4345 ) // behavior change: an object of POD type constructed with an initializer of the form () will be default-initialized
236 template <typename T>
237 void QVector<T>::defaultConstruct(T *from, T *to)
239 if (QTypeInfo<T>::isComplex) {
244 ::memset(from, 0, (to - from) * sizeof(T));
249 # pragma warning ( default: 4345 )
252 template <typename T>
253 void QVector<T>::copyConstruct(const T *srcFrom, const T *srcTo, T *dstFrom)
255 if (QTypeInfo<T>::isComplex) {
256 while (srcFrom != srcTo)
257 new (dstFrom++) T(*srcFrom++);
259 ::memcpy(dstFrom, srcFrom, (srcTo - srcFrom) * sizeof(T));
263 template <typename T>
264 void QVector<T>::destruct(T *from, T *to)
266 if (QTypeInfo<T>::isComplex) {
273 template <typename T>
274 inline QVector<T>::QVector(const QVector<T> &v)
276 if (v.d->ref.ref()) {
279 if (v.d->capacityReserved) {
280 d = Data::allocate(v.d->alloc);
281 d->capacityReserved = true;
283 d = Data::allocate(v.d->size);
286 copyConstruct(v.d->begin(), v.d->end(), d->begin());
292 template <typename T>
293 void QVector<T>::detach()
297 reallocData(d->size, int(d->alloc));
299 d = Data::unsharableEmpty();
301 Q_ASSERT(isDetached());
304 template <typename T>
305 void QVector<T>::reserve(int asize)
307 if (asize > int(d->alloc))
308 reallocData(d->size, asize);
310 d->capacityReserved = 1;
311 Q_ASSERT(capacity() >= asize);
314 template <typename T>
315 void QVector<T>::resize(int asize)
318 const int oldAlloc = int(d->alloc);
319 QArrayData::AllocationOptions opt;
321 if (asize > oldAlloc) { // there is not enough space
323 opt = QArrayData::Grow;
324 } else if (!d->capacityReserved && asize < d->size && asize < (oldAlloc >> 1)) { // we want to shrink
326 opt = QArrayData::Grow;
330 reallocData(asize, newAlloc, opt);
332 template <typename T>
333 inline void QVector<T>::clear()
334 { *this = QVector<T>(); }
335 template <typename T>
336 inline const T &QVector<T>::at(int i) const
337 { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::at", "index out of range");
338 return d->begin()[i]; }
339 template <typename T>
340 inline const T &QVector<T>::operator[](int i) const
341 { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]", "index out of range");
342 return d->begin()[i]; }
343 template <typename T>
344 inline T &QVector<T>::operator[](int i)
345 { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]", "index out of range");
347 template <typename T>
348 inline void QVector<T>::insert(int i, const T &t)
349 { Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert", "index out of range");
350 insert(begin() + i, 1, t); }
351 template <typename T>
352 inline void QVector<T>::insert(int i, int n, const T &t)
353 { Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert", "index out of range");
354 insert(begin() + i, n, t); }
355 template <typename T>
356 inline void QVector<T>::remove(int i, int n)
357 { Q_ASSERT_X(i >= 0 && n >= 0 && i + n <= d->size, "QVector<T>::remove", "index out of range");
358 erase(begin() + i, begin() + i + n); }
359 template <typename T>
360 inline void QVector<T>::remove(int i)
361 { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::remove", "index out of range");
362 erase(begin() + i, begin() + i + 1); }
363 template <typename T>
364 inline void QVector<T>::prepend(const T &t)
365 { insert(begin(), 1, t); }
367 template <typename T>
368 inline void QVector<T>::replace(int i, const T &t)
370 Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::replace", "index out of range");
375 template <typename T>
376 QVector<T> &QVector<T>::operator=(const QVector<T> &v)
385 template <typename T>
386 QVector<T>::QVector(int asize)
388 if (Q_LIKELY(asize)) {
389 d = Data::allocate(asize);
391 defaultConstruct(d->begin(), d->end());
393 d = Data::sharedNull();
397 template <typename T>
398 QVector<T>::QVector(int asize, const T &t)
401 d = Data::allocate(asize);
404 while (i != d->begin())
407 d = Data::sharedNull();
411 #ifdef Q_COMPILER_INITIALIZER_LISTS
412 template <typename T>
413 QVector<T>::QVector(std::initializer_list<T> args)
415 d = Data::allocate(args.size());
416 // std::initializer_list<T>::iterator is guaranteed to be
417 // const T* ([support.initlist]/1), so can be memcpy'ed away from by copyConstruct
418 copyConstruct(args.begin(), args.end(), d->begin());
419 d->size = int(args.size());
423 template <typename T>
424 void QVector<T>::freeData(Data *x)
426 destruct(x->begin(), x->end());
430 template <typename T>
431 void QVector<T>::reallocData(const int asize, const int aalloc, QArrayData::AllocationOptions options)
433 Q_ASSERT(asize >= 0 && asize <= aalloc);
436 const bool isShared = d->ref.isShared();
439 if (aalloc != int(d->alloc) || isShared) {
442 x = Data::allocate(aalloc, options);
444 // aalloc is bigger then 0 so it is not [un]sharedEmpty
445 Q_ASSERT(x->ref.isSharable() || options.testFlag(QArrayData::Unsharable));
446 Q_ASSERT(!x->ref.isStatic());
449 T *srcBegin = d->begin();
450 T *srcEnd = asize > d->size ? d->end() : d->begin() + asize;
453 if (QTypeInfo<T>::isStatic || (isShared && QTypeInfo<T>::isComplex)) {
454 // we can not move the data, we need to copy construct it
455 while (srcBegin != srcEnd) {
456 new (dst++) T(*srcBegin++);
459 ::memcpy(static_cast<void *>(dst), srcBegin, (srcEnd - srcBegin) * sizeof(T));
460 dst += srcEnd - srcBegin;
462 // destruct unused / not moved data
464 destruct(d->begin() + asize, d->end());
467 if (asize > d->size) {
468 // construct all new objects when growing
470 defaultConstruct(dst, x->end());
472 // destruct already copied objects
473 destruct(x->begin(), dst);
481 x->capacityReserved = d->capacityReserved;
483 Q_ASSERT(d->alloc == aalloc); // resize, without changing allocation size
484 Q_ASSERT(isDetached()); // can be done only on detached d
485 Q_ASSERT(x == d); // in this case we do not need to allocate anything
486 if (asize <= d->size) {
487 destruct(x->begin() + asize, x->end()); // from future end to current end
489 defaultConstruct(x->end(), x->begin() + asize); // from current end to future end
494 x = Data::sharedNull();
497 if (!d->ref.deref()) {
499 if (QTypeInfo<T>::isStatic || !aalloc) {
500 // data was copy constructed, we need to call destructors
501 // or if !alloc we did nothing to the old 'd'.
511 Q_ASSERT(uint(d->size) <= d->alloc);
512 Q_ASSERT(d != Data::unsharableEmpty());
513 Q_ASSERT(aalloc ? d != Data::sharedNull() : d == Data::sharedNull());
514 Q_ASSERT(d->alloc >= uint(aalloc));
515 Q_ASSERT(d->size == asize);
519 Q_OUTOFLINE_TEMPLATE T QVector<T>::value(int i) const
521 if (i < 0 || i >= d->size) {
524 return d->begin()[i];
527 Q_OUTOFLINE_TEMPLATE T QVector<T>::value(int i, const T &defaultValue) const
529 return ((i < 0 || i >= d->size) ? defaultValue : d->begin()[i]);
532 template <typename T>
533 void QVector<T>::append(const T &t)
536 const bool isTooSmall = uint(d->size + 1) > d->alloc;
537 if (!isDetached() || isTooSmall) {
538 QArrayData::AllocationOptions opt(isTooSmall ? QArrayData::Grow : QArrayData::Default);
539 reallocData(d->size, isTooSmall ? d->size + 1 : d->alloc, opt);
541 if (QTypeInfo<T>::isComplex)
542 new (d->end()) T(copy);
548 template <typename T>
549 typename QVector<T>::iterator QVector<T>::insert(iterator before, size_type n, const T &t)
551 int offset = std::distance(d->begin(), before);
554 if (!isDetached() || d->size + n > int(d->alloc))
555 reallocData(d->size, d->size + n, QArrayData::Grow);
556 if (QTypeInfo<T>::isStatic) {
563 b = d->begin() + offset;
570 T *b = d->begin() + offset;
572 memmove(i, b, (d->size - offset) * sizeof(T));
578 return d->begin() + offset;
581 template <typename T>
582 typename QVector<T>::iterator QVector<T>::erase(iterator abegin, iterator aend)
584 const int itemsToErase = aend - abegin;
589 Q_ASSERT(abegin >= d->begin());
590 Q_ASSERT(aend <= d->end());
591 Q_ASSERT(abegin <= aend);
593 const int itemsUntouched = abegin - d->begin();
595 // FIXME we could do a proper realloc, which copy constructs only needed data.
596 // FIXME we ara about to delete data maybe it is good time to shrink?
599 if (QTypeInfo<T>::isStatic) {
600 iterator moveBegin = abegin + itemsToErase;
601 iterator moveEnd = d->end();
602 while (moveBegin != moveEnd) {
603 if (QTypeInfo<T>::isComplex)
605 new (abegin++) T(*moveBegin++);
607 if (abegin < d->end()) {
608 // destroy rest of instances
609 destruct(abegin, d->end());
612 destruct(abegin, aend);
613 memmove(abegin, aend, (d->size - itemsToErase - itemsUntouched) * sizeof(T));
615 d->size -= itemsToErase;
617 return d->begin() + itemsUntouched;
620 template <typename T>
621 bool QVector<T>::operator==(const QVector<T> &v) const
623 if (d->size != v.d->size)
636 template <typename T>
637 QVector<T> &QVector<T>::fill(const T &from, int asize)
640 resize(asize < 0 ? d->size : asize);
650 template <typename T>
651 QVector<T> &QVector<T>::operator+=(const QVector &l)
653 int newSize = d->size + l.d->size;
654 reallocData(d->size, newSize);
657 T *w = d->begin() + newSize;
661 if (QTypeInfo<T>::isComplex)
671 template <typename T>
672 int QVector<T>::indexOf(const T &t, int from) const
675 from = qMax(from + d->size, 0);
676 if (from < d->size) {
677 T* n = d->begin() + from - 1;
681 return n - d->begin();
686 template <typename T>
687 int QVector<T>::lastIndexOf(const T &t, int from) const
691 else if (from >= d->size)
695 T* n = d->begin() + from + 1;
704 template <typename T>
705 bool QVector<T>::contains(const T &t) const
715 template <typename T>
716 int QVector<T>::count(const T &t) const
727 template <typename T>
728 Q_OUTOFLINE_TEMPLATE QVector<T> QVector<T>::mid(int pos, int length) const
731 length = size() - pos;
732 if (pos == 0 && length == size())
734 if (pos + length > size())
735 length = size() - pos;
737 copy.reserve(length);
738 for (int i = pos; i < pos + length; ++i)
743 template <typename T>
744 Q_OUTOFLINE_TEMPLATE QList<T> QVector<T>::toList() const
747 result.reserve(size());
748 for (int i = 0; i < size(); ++i)
749 result.append(at(i));
753 template <typename T>
754 Q_OUTOFLINE_TEMPLATE QVector<T> QList<T>::toVector() const
756 QVector<T> result(size());
757 for (int i = 0; i < size(); ++i)
762 template <typename T>
763 QVector<T> QVector<T>::fromList(const QList<T> &list)
765 return list.toVector();
768 template <typename T>
769 QList<T> QList<T>::fromVector(const QVector<T> &vector)
771 return vector.toList();
774 Q_DECLARE_SEQUENTIAL_ITERATOR(Vector)
775 Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(Vector)
779 ### This needs to be removed for next releases of Qt. It is a workaround for vc++ because
780 ### Qt exports QPolygon and QPolygonF that inherit QVector<QPoint> and
781 ### QVector<QPointF> respectively.
785 QT_BEGIN_INCLUDE_NAMESPACE
786 #include <QtCore/QPointF>
787 #include <QtCore/QPoint>
788 QT_END_INCLUDE_NAMESPACE
790 #if defined(QT_BUILD_CORE_LIB)
791 #define Q_TEMPLATE_EXTERN
793 #define Q_TEMPLATE_EXTERN extern
795 Q_TEMPLATE_EXTERN template class Q_CORE_EXPORT QVector<QPointF>;
796 Q_TEMPLATE_EXTERN template class Q_CORE_EXPORT QVector<QPoint>;