- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files
- Directories
- Examples

- File List
- File Members

# qvector.h

Go to the documentation of this file.

    00001 /****************************************************************************
    00002 **
    00003 ** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).
    00004 ** All rights reserved.
    00005 ** Contact: Nokia Corporation (qt-info@nokia.com)
    00006 **
    00007 ** This file is part of the QtCore module of the Qt Toolkit.
    00008 **
    00009 ** $QT_BEGIN_LICENSE:LGPL$
    00010 ** Commercial Usage
    00011 ** Licensees holding valid Qt Commercial licenses may use this file in
    00012 ** accordance with the Qt Commercial License Agreement provided with the
    00013 ** Software or, alternatively, in accordance with the terms contained in
    00014 ** a written agreement between you and Nokia.
    00015 **
    00016 ** GNU Lesser General Public License Usage
    00017 ** Alternatively, this file may be used under the terms of the GNU Lesser
    00018 ** General Public License version 2.1 as published by the Free Software
    00019 ** Foundation and appearing in the file LICENSE.LGPL included in the
    00020 ** packaging of this file.  Please review the following information to
    00021 ** ensure the GNU Lesser General Public License version 2.1 requirements
    00022 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
    00023 **
    00024 ** In addition, as a special exception, Nokia gives you certain additional
    00025 ** rights.  These rights are described in the Nokia Qt LGPL Exception
    00026 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this module.
    00027 **
    00028 ** GNU General Public License Usage
    00029 ** Alternatively, this file may be used under the terms of the GNU
    00030 ** General Public License version 3.0 as published by the Free Software
    00031 ** Foundation and appearing in the file LICENSE.GPL included in the
    00032 ** packaging of this file.  Please review the following information to
    00033 ** ensure the GNU General Public License version 3.0 requirements will be
    00034 ** met: http://www.gnu.org/copyleft/gpl.html.
    00035 **
    00036 ** If you have questions regarding the use of this file, please contact
    00037 ** Nokia at qt-info@nokia.com.
    00038 ** $QT_END_LICENSE$
    00039 **
    00040 ****************************************************************************/
    00041
    00042 #ifndef QVECTOR_H
    00043 #define QVECTOR_H
    00044
    00045 #include <QtCore/qiterator.h>
    00046 #include <QtCore/qatomic.h>
    00047 #include <QtCore/qalgorithms.h>
    00048 #include <QtCore/qlist.h>
    00049
    00050 #ifndef QT_NO_STL
    00051 #include <iterator>
    00052 #include <vector>
    00053 #endif
    00054 #include <stdlib.h>
    00055 #include <string.h>
    00056
    00057 QT_BEGIN_HEADER
    00058
    00059 QT_BEGIN_NAMESPACE
    00060
    00061 QT_MODULE(Core)
    00062
    00063 struct Q_CORE_EXPORT QVectorData
    00064 {
    00065     QBasicAtomicInt ref;
    00066     int alloc;
    00067     int size;
    00068 #if defined(QT_ARCH_SPARC) && defined(Q_CC_GNU) && defined(__LP64__) && defined(QT_BOOTSTRAPPED)
    00069     // workaround for bug in gcc 3.4.2
    00070     uint sharable;
    00071     uint capacity;
    00072     uint reserved;
    00073 #else
    00074     uint sharable : 1;
    00075     uint capacity : 1;
    00076     uint reserved : 30;
    00077 #endif
    00078
    00079     static QVectorData shared_null;
    00080     // ### Qt 5: rename to 'allocate()'. The current name causes problems for
    00081     // some debugges when the QVector is member of a class within an unnamed namespace.
    00082     // ### Qt 5: can be removed completely. (Ralf)
    00083     static QVectorData *malloc(int sizeofTypedData, int size, int sizeofT, QVectorData *init);
    00084     static QVectorData *allocate(int size, int alignment);
    00085     static QVectorData *reallocate(QVectorData *old, int newsize, int oldsize, int alignment);
    00086     static void free(QVectorData *data, int alignment);
    00087     static int grow(int sizeofTypedData, int size, int sizeofT, bool excessive);
    00088 };
    00089
    00090 template <typename T>
    00091 struct QVectorTypedData : private QVectorData
    00092 { // private inheritance as we must not access QVectorData member thought QVectorTypedData
    00093   // as this would break strict aliasing rules. (in the case of shared_null)
    00094     T array[1];
    00095
    00096     static inline void free(QVectorTypedData<T> *x, int alignment) { QVectorData::free(static_cast<QVectorData *>(x), alignment); }
    00097 };
    00098
    00099 class QRegion;
    00100
    00101 template <typename T>
    00102 class QVector
    00103 {
    00104     typedef QVectorTypedData<T> Data;
    00105     union {
    00106         QVectorData *d;
    00107 #if defined(Q_CC_SUN) && (__SUNPRO_CC <= 0x550)
    00108         QVectorTypedData<T> *p;
    00109 #else
    00110         Data *p;
    00111 #endif
    00112     };
    00113
    00114 public:
    00115     inline QVector() : d(&QVectorData::shared_null) { d->ref.ref(); }
    00116     explicit QVector(int size);
    00117     QVector(int size, const T &t);
    00118     inline QVector(const QVector<T> &v) : d(v.d) { d->ref.ref(); if (!d->sharable) detach_helper(); }
    00119     inline ~QVector() { if (!d) return; if (!d->ref.deref()) free(p); }
    00120     QVector<T> &operator=(const QVector<T> &v);
    00121     bool operator==(const QVector<T> &v) const;
    00122     inline bool operator!=(const QVector<T> &v) const { return !(*this == v); }
    00123
    00124     inline int size() const { return d->size; }
    00125
    00126     inline bool isEmpty() const { return d->size == 0; }
    00127
    00128     void resize(int size);
    00129
    00130     inline int capacity() const { return d->alloc; }
    00131     void reserve(int size);
    00132     inline void squeeze() { realloc(d->size, d->size); d->capacity = 0; }
    00133
    00134     inline void detach() { if (d->ref != 1) detach_helper(); }
    00135     inline bool isDetached() const { return d->ref == 1; }
    00136     inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
    00137     inline bool isSharedWith(const QVector<T> &other) const { return d == other.d; }
    00138
    00139     inline T *data() { detach(); return p->array; }
    00140     inline const T *data() const { return p->array; }
    00141     inline const T *constData() const { return p->array; }
    00142     void clear();
    00143
    00144     const T &at(int i) const;
    00145     T &operator[](int i);
    00146     const T &operator[](int i) const;
    00147     void append(const T &t);
    00148     void prepend(const T &t);
    00149     void insert(int i, const T &t);
    00150     void insert(int i, int n, const T &t);
    00151     void replace(int i, const T &t);
    00152     void remove(int i);
    00153     void remove(int i, int n);
    00154
    00155     QVector<T> &fill(const T &t, int size = -1);
    00156
    00157     int indexOf(const T &t, int from = 0) const;
    00158     int lastIndexOf(const T &t, int from = -1) const;
    00159     bool contains(const T &t) const;
    00160     int count(const T &t) const;
    00161
    00162 #ifdef QT_STRICT_ITERATORS
    00163     class iterator {
    00164     public:
    00165         T *i;
    00166         typedef std::random_access_iterator_tag  iterator_category;
    00167         typedef qptrdiff difference_type;
    00168         typedef T value_type;
    00169         typedef T *pointer;
    00170         typedef T &reference;
    00171
    00172         inline iterator() : i(0) {}
    00173         inline iterator(T *n) : i(n) {}
    00174         inline iterator(const iterator &o): i(o.i){}
    00175         inline T &operator*() const { return *i; }
    00176         inline T *operator->() const { return i; }
    00177         inline T &operator[](int j) const { return *(i + j); }
    00178         inline bool operator==(const iterator &o) const { return i == o.i; }
    00179         inline bool operator!=(const iterator &o) const { return i != o.i; }
    00180         inline bool operator<(const iterator& other) const { return i < other.i; }
    00181         inline bool operator<=(const iterator& other) const { return i <= other.i; }
    00182         inline bool operator>(const iterator& other) const { return i > other.i; }
    00183         inline bool operator>=(const iterator& other) const { return i >= other.i; }
    00184         inline iterator &operator++() { ++i; return *this; }
    00185         inline iterator operator++(int) { T *n = i; ++i; return n; }
    00186         inline iterator &operator--() { i--; return *this; }
    00187         inline iterator operator--(int) { T *n = i; i--; return n; }
    00188         inline iterator &operator+=(int j) { i+=j; return *this; }
    00189         inline iterator &operator-=(int j) { i-=j; return *this; }
    00190         inline iterator operator+(int j) const { return iterator(i+j); }
    00191         inline iterator operator-(int j) const { return iterator(i-j); }
    00192         inline int operator-(iterator j) const { return i - j.i; }
    00193     };
    00194     friend class iterator;
    00195
    00196     class const_iterator {
    00197     public:
    00198         T *i;
    00199         typedef std::random_access_iterator_tag  iterator_category;
    00200         typedef qptrdiff difference_type;
    00201         typedef T value_type;
    00202         typedef const T *pointer;
    00203         typedef const T &reference;
    00204
    00205         inline const_iterator() : i(0) {}
    00206         inline const_iterator(T *n) : i(n) {}
    00207         inline const_iterator(const const_iterator &o): i(o.i) {}
    00208         inline explicit const_iterator(const iterator &o): i(o.i) {}
    00209         inline const T &operator*() const { return *i; }
    00210         inline const T *operator->() const { return i; }
    00211         inline const T &operator[](int j) const { return *(i + j); }
    00212         inline bool operator==(const const_iterator &o) const { return i == o.i; }
    00213         inline bool operator!=(const const_iterator &o) const { return i != o.i; }
    00214         inline bool operator<(const const_iterator& other) const { return i < other.i; }
    00215         inline bool operator<=(const const_iterator& other) const { return i <= other.i; }
    00216         inline bool operator>(const const_iterator& other) const { return i > other.i; }
    00217         inline bool operator>=(const const_iterator& other) const { return i >= other.i; }
    00218         inline const_iterator &operator++() { ++i; return *this; }
    00219         inline const_iterator operator++(int) { T *n = i; ++i; return n; }
    00220         inline const_iterator &operator--() { i--; return *this; }
    00221         inline const_iterator operator--(int) { T *n = i; i--; return n; }
    00222         inline const_iterator &operator+=(int j) { i+=j; return *this; }
    00223         inline const_iterator &operator-=(int j) { i-=j; return *this; }
    00224         inline const_iterator operator+(int j) const { return const_iterator(i+j); }
    00225         inline const_iterator operator-(int j) const { return const_iterator(i-j); }
    00226         inline int operator-(const_iterator j) const { return i - j.i; }
    00227     };
    00228     friend class const_iterator;
    00229 #else
    00230     // STL-style
    00231     typedef T* iterator;
    00232     typedef const T* const_iterator;
    00233 #endif
    00234     inline iterator begin() { detach(); return p->array; }
    00235     inline const_iterator begin() const { return p->array; }
    00236     inline const_iterator constBegin() const { return p->array; }
    00237     inline iterator end() { detach(); return p->array + d->size; }
    00238     inline const_iterator end() const { return p->array + d->size; }
    00239     inline const_iterator constEnd() const { return p->array + d->size; }
    00240     iterator insert(iterator before, int n, const T &x);
    00241     inline iterator insert(iterator before, const T &x) { return insert(before, 1, x); }
    00242     iterator erase(iterator begin, iterator end);
    00243     inline iterator erase(iterator pos) { return erase(pos, pos+1); }
    00244
    00245     // more Qt
    00246     inline int count() const { return d->size; }
    00247     inline T& first() { Q_ASSERT(!isEmpty()); return *begin(); }
    00248     inline const T &first() const { Q_ASSERT(!isEmpty()); return *begin(); }
    00249     inline T& last() { Q_ASSERT(!isEmpty()); return *(end()-1); }
    00250     inline const T &last() const { Q_ASSERT(!isEmpty()); return *(end()-1); }
    00251     inline bool startsWith(const T &t) const { return !isEmpty() && first() == t; }
    00252     inline bool endsWith(const T &t) const { return !isEmpty() && last() == t; }
    00253     QVector<T> mid(int pos, int length = -1) const;
    00254
    00255     T value(int i) const;
    00256     T value(int i, const T &defaultValue) const;
    00257
    00258     // STL compatibility
    00259     typedef T value_type;
    00260     typedef value_type* pointer;
    00261     typedef const value_type* const_pointer;
    00262     typedef value_type& reference;
    00263     typedef const value_type& const_reference;
    00264     typedef qptrdiff difference_type;
    00265     typedef iterator Iterator;
    00266     typedef const_iterator ConstIterator;
    00267     typedef int size_type;
    00268     inline void push_back(const T &t) { append(t); }
    00269     inline void push_front(const T &t) { prepend(t); }
    00270     void pop_back() { Q_ASSERT(!isEmpty()); erase(end()-1); }
    00271     void pop_front() { Q_ASSERT(!isEmpty()); erase(begin()); }
    00272     inline bool empty() const
    00273     { return d->size == 0; }
    00274     inline T& front() { return first(); }
    00275     inline const_reference front() const { return first(); }
    00276     inline reference back() { return last(); }
    00277     inline const_reference back() const { return last(); }
    00278
    00279     // comfort
    00280     QVector<T> &operator+=(const QVector<T> &l);
    00281     inline QVector<T> operator+(const QVector<T> &l) const
    00282     { QVector n = *this; n += l; return n; }
    00283     inline QVector<T> &operator+=(const T &t)
    00284     { append(t); return *this; }
    00285     inline QVector<T> &operator<< (const T &t)
    00286     { append(t); return *this; }
    00287     inline QVector<T> &operator<<(const QVector<T> &l)
    00288     { *this += l; return *this; }
    00289
    00290     QList<T> toList() const;
    00291
    00292     static QVector<T> fromList(const QList<T> &list);
    00293
    00294 #ifndef QT_NO_STL
    00295     static inline QVector<T> fromStdVector(const std::vector<T> &vector)
    00296     { QVector<T> tmp; tmp.reserve(vector.size()); qCopy(vector.begin(), vector.end(), std::back_inserter(tmp)); return tmp; }
    00297     inline std::vector<T> toStdVector() const
    00298     { std::vector<T> tmp; tmp.reserve(size()); qCopy(constBegin(), constEnd(), std::back_inserter(tmp)); return tmp; }
    00299 #endif
    00300
    00301 private:
    00302     friend class QRegion; // Optimization for QRegion::rects()
    00303
    00304     void detach_helper();
    00305     QVectorData *malloc(int alloc);
    00306     void realloc(int size, int alloc);
    00307     void free(Data *d);
    00308     int sizeOfTypedData() {
    00309         // this is more or less the same as sizeof(Data), except that it doesn't
    00310         // count the padding at the end
    00311         return reinterpret_cast<const char *>(&(reinterpret_cast<const Data *>(this))->array[1]) - reinterpret_cast<const char *>(this);
    00312     }
    00313     inline int alignOfTypedData() const
    00314     {
    00315 #ifdef Q_ALIGNOF
    00316         return qMax<int>(sizeof(void*), Q_ALIGNOF(Data));
    00317 #else
    00318         return 0;
    00319 #endif
    00320     }
    00321 };
    00322
    00323 template <typename T>
    00324 void QVector<T>::detach_helper()
    00325 { realloc(d->size, d->alloc); }
    00326 template <typename T>
    00327 void QVector<T>::reserve(int asize)
    00328 { if (asize > d->alloc) realloc(d->size, asize); if (d->ref == 1) d->capacity = 1; }
    00329 template <typename T>
    00330 void QVector<T>::resize(int asize)
    00331 { realloc(asize, (asize > d->alloc || (!d->capacity && asize < d->size && asize < (d->alloc >> 1))) ?
    00332           QVectorData::grow(sizeOfTypedData(), asize, sizeof(T), QTypeInfo<T>::isStatic)
    00333           : d->alloc); }
    00334 template <typename T>
    00335 inline void QVector<T>::clear()
    00336 { *this = QVector<T>(); }
    00337 template <typename T>
    00338 inline const T &QVector<T>::at(int i) const
    00339 { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::at", "index out of range");
    00340   return p->array[i]; }
    00341 template <typename T>
    00342 inline const T &QVector<T>::operator[](int i) const
    00343 { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]", "index out of range");
    00344   return p->array[i]; }
    00345 template <typename T>
    00346 inline T &QVector<T>::operator[](int i)
    00347 { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::operator[]", "index out of range");
    00348   return data()[i]; }
    00349 template <typename T>
    00350 inline void QVector<T>::insert(int i, const T &t)
    00351 { Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert", "index out of range");
    00352   insert(begin() + i, 1, t); }
    00353 template <typename T>
    00354 inline void QVector<T>::insert(int i, int n, const T &t)
    00355 { Q_ASSERT_X(i >= 0 && i <= d->size, "QVector<T>::insert", "index out of range");
    00356   insert(begin() + i, n, t); }
    00357 template <typename T>
    00358 inline void QVector<T>::remove(int i, int n)
    00359 { Q_ASSERT_X(i >= 0 && n >= 0 && i + n <= d->size, "QVector<T>::remove", "index out of range");
    00360   erase(begin() + i, begin() + i + n); }
    00361 template <typename T>
    00362 inline void QVector<T>::remove(int i)
    00363 { Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::remove", "index out of range");
    00364   erase(begin() + i, begin() + i + 1); }
    00365 template <typename T>
    00366 inline void QVector<T>::prepend(const T &t)
    00367 { insert(begin(), 1, t); }
    00368
    00369 template <typename T>
    00370 inline void QVector<T>::replace(int i, const T &t)
    00371 {
    00372     Q_ASSERT_X(i >= 0 && i < d->size, "QVector<T>::replace", "index out of range");
    00373     const T copy(t);
    00374     data()[i] = copy;
    00375 }
    00376
    00377 template <typename T>
    00378 QVector<T> &QVector<T>::operator=(const QVector<T> &v)
    00379 {
    00380     QVectorData *o = v.d;
    00381     o->ref.ref();
    00382     if (!d->ref.deref())
    00383         free(p);
    00384     d = o;
    00385     if (!d->sharable)
    00386         detach_helper();
    00387     return *this;
    00388 }
    00389
    00390 template <typename T>
    00391 inline QVectorData *QVector<T>::malloc(int aalloc)
    00392 {
    00393     QVectorData *vectordata = QVectorData::allocate(sizeOfTypedData() + (aalloc - 1) * sizeof(T), alignOfTypedData());
    00394     Q_CHECK_PTR(vectordata);
    00395     return vectordata;
    00396 }
    00397
    00398 template <typename T>
    00399 QVector<T>::QVector(int asize)
    00400 {
    00401     d = malloc(asize);
    00402     d->ref = 1;
    00403     d->alloc = d->size = asize;
    00404     d->sharable = true;
    00405     d->capacity = false;
    00406     if (QTypeInfo<T>::isComplex) {
    00407         T* b = p->array;
    00408         T* i = p->array + d->size;
    00409         while (i != b)
    00410             new (--i) T;
    00411     } else {
    00412         qMemSet(p->array, 0, asize * sizeof(T));
    00413     }
    00414 }
    00415
    00416 template <typename T>
    00417 QVector<T>::QVector(int asize, const T &t)
    00418 {
    00419     d = malloc(asize);
    00420     d->ref = 1;
    00421     d->alloc = d->size = asize;
    00422     d->sharable = true;
    00423     d->capacity = false;
    00424     T* i = p->array + d->size;
    00425     while (i != p->array)
    00426         new (--i) T(t);
    00427 }
    00428
    00429 template <typename T>
    00430 void QVector<T>::free(Data *x)
    00431 {
    00432     if (QTypeInfo<T>::isComplex) {
    00433         T* b = x->array;
    00434         union { QVectorData *d; Data *p; } u;
    00435         u.p = x;
    00436         T* i = b + u.d->size;
    00437         while (i-- != b)
    00438              i->~T();
    00439     }
    00440     x->free(x, alignOfTypedData());
    00441 }
    00442
    00443 template <typename T>
    00444 void QVector<T>::realloc(int asize, int aalloc)
    00445 {
    00446     Q_ASSERT(asize <= aalloc);
    00447     T *pOld;
    00448     T *pNew;
    00449     union { QVectorData *d; Data *p; } x;
    00450     x.d = d;
    00451
    00452     if (QTypeInfo<T>::isComplex && asize < d->size && d->ref == 1 ) {
    00453         // call the destructor on all objects that need to be
    00454         // destroyed when shrinking
    00455         pOld = p->array + d->size;
    00456         pNew = p->array + asize;
    00457         while (asize < d->size) {
    00458             (--pOld)->~T();
    00459             d->size--;
    00460         }
    00461     }
    00462
    00463     if (aalloc != d->alloc || d->ref != 1) {
    00464         // (re)allocate memory
    00465         if (QTypeInfo<T>::isStatic) {
    00466             x.d = malloc(aalloc);
    00467             Q_CHECK_PTR(x.p);
    00468             x.d->size = 0;
    00469         } else if (d->ref != 1) {
    00470             x.d = malloc(aalloc);
    00471             Q_CHECK_PTR(x.p);
    00472             if (QTypeInfo<T>::isComplex) {
    00473                 x.d->size = 0;
    00474             } else {
    00475                 ::memcpy(x.p, p, sizeOfTypedData() + (qMin(aalloc, d->alloc) - 1) * sizeof(T));
    00476                 x.d->size = d->size;
    00477             }
    00478         } else {
    00479             QT_TRY {
    00480                 QVectorData *mem = QVectorData::reallocate(d, sizeOfTypedData() + (aalloc - 1) * sizeof(T),
    00481                                                            sizeOfTypedData() + (d->alloc - 1) * sizeof(T), alignOfTypedData());
    00482                 Q_CHECK_PTR(mem);
    00483                 x.d = d = mem;
    00484                 x.d->size = d->size;
    00485             } QT_CATCH (const std::bad_alloc &) {
    00486                 if (aalloc > d->alloc) // ignore the error in case we are just shrinking.
    00487                     QT_RETHROW;
    00488             }
    00489         }
    00490         x.d->ref = 1;
    00491         x.d->alloc = aalloc;
    00492         x.d->sharable = true;
    00493         x.d->capacity = d->capacity;
    00494         x.d->reserved = 0;
    00495     }
    00496
    00497     if (QTypeInfo<T>::isComplex) {
    00498         QT_TRY {
    00499             pOld = p->array + x.d->size;
    00500             pNew = x.p->array + x.d->size;
    00501             // copy objects from the old array into the new array
    00502             const int toMove = qMin(asize, d->size);
    00503             while (x.d->size < toMove) {
    00504                 new (pNew++) T(*pOld++);
    00505                 x.d->size++;
    00506             }
    00507             // construct all new objects when growing
    00508             while (x.d->size < asize) {
    00509                 new (pNew++) T;
    00510                 x.d->size++;
    00511             }
    00512         } QT_CATCH (...) {
    00513             free(x.p);
    00514             QT_RETHROW;
    00515         }
    00516
    00517     } else if (asize > x.d->size) {
    00518         // initialize newly allocated memory to 0
    00519         qMemSet(x.p->array + x.d->size, 0, (asize - x.d->size) * sizeof(T));
    00520     }
    00521     x.d->size = asize;
    00522
    00523     if (d != x.d) {
    00524         if (!d->ref.deref())
    00525             free(p);
    00526         d = x.d;
    00527     }
    00528 }
    00529
    00530 template<typename T>
    00531 Q_OUTOFLINE_TEMPLATE T QVector<T>::value(int i) const
    00532 {
    00533     if (i < 0 || i >= d->size) {
    00534         return T();
    00535     }
    00536     return p->array[i];
    00537 }
    00538 template<typename T>
    00539 Q_OUTOFLINE_TEMPLATE T QVector<T>::value(int i, const T &defaultValue) const
    00540 {
    00541     return ((i < 0 || i >= d->size) ? defaultValue : p->array[i]);
    00542 }
    00543
    00544 template <typename T>
    00545 void QVector<T>::append(const T &t)
    00546 {
    00547     if (d->ref != 1 || d->size + 1 > d->alloc) {
    00548         const T copy(t);
    00549         realloc(d->size, QVectorData::grow(sizeOfTypedData(), d->size + 1, sizeof(T),
    00550                                            QTypeInfo<T>::isStatic));
    00551         if (QTypeInfo<T>::isComplex)
    00552             new (p->array + d->size) T(copy);
    00553         else
    00554             p->array[d->size] = copy;
    00555     } else {
    00556         if (QTypeInfo<T>::isComplex)
    00557             new (p->array + d->size) T(t);
    00558         else
    00559             p->array[d->size] = t;
    00560     }
    00561     ++d->size;
    00562 }
    00563
    00564 template <typename T>
    00565 Q_TYPENAME QVector<T>::iterator QVector<T>::insert(iterator before, size_type n, const T &t)
    00566 {
    00567     int offset = int(before - p->array);
    00568     if (n != 0) {
    00569         const T copy(t);
    00570         if (d->ref != 1 || d->size + n > d->alloc)
    00571             realloc(d->size, QVectorData::grow(sizeOfTypedData(), d->size + n, sizeof(T),
    00572                                                QTypeInfo<T>::isStatic));
    00573         if (QTypeInfo<T>::isStatic) {
    00574             T *b = p->array + d->size;
    00575             T *i = p->array + d->size + n;
    00576             while (i != b)
    00577                 new (--i) T;
    00578             i = p->array + d->size;
    00579             T *j = i + n;
    00580             b = p->array + offset;
    00581             while (i != b)
    00582                 *--j = *--i;
    00583             i = b+n;
    00584             while (i != b)
    00585                 *--i = copy;
    00586         } else {
    00587             T *b = p->array + offset;
    00588             T *i = b + n;
    00589             memmove(i, b, (d->size - offset) * sizeof(T));
    00590             while (i != b)
    00591                 new (--i) T(copy);
    00592         }
    00593         d->size += n;
    00594     }
    00595     return p->array + offset;
    00596 }
    00597
    00598 template <typename T>
    00599 Q_TYPENAME QVector<T>::iterator QVector<T>::erase(iterator abegin, iterator aend)
    00600 {
    00601     int f = int(abegin - p->array);
    00602     int l = int(aend - p->array);
    00603     int n = l - f;
    00604     detach();
    00605     if (QTypeInfo<T>::isComplex) {
    00606         qCopy(p->array+l, p->array+d->size, p->array+f);
    00607         T *i = p->array+d->size;
    00608         T* b = p->array+d->size-n;
    00609         while (i != b) {
    00610             --i;
    00611             i->~T();
    00612         }
    00613     } else {
    00614         memmove(p->array + f, p->array + l, (d->size-l)*sizeof(T));
    00615     }
    00616     d->size -= n;
    00617     return p->array + f;
    00618 }
    00619
    00620 template <typename T>
    00621 bool QVector<T>::operator==(const QVector<T> &v) const
    00622 {
    00623     if (d->size != v.d->size)
    00624         return false;
    00625     if (d == v.d)
    00626         return true;
    00627     T* b = p->array;
    00628     T* i = b + d->size;
    00629     T* j = v.p->array + d->size;
    00630     while (i != b)
    00631         if (!(*--i == *--j))
    00632             return false;
    00633     return true;
    00634 }
    00635
    00636 template <typename T>
    00637 QVector<T> &QVector<T>::fill(const T &from, int asize)
    00638 {
    00639     const T copy(from);
    00640     resize(asize < 0 ? d->size : asize);
    00641     if (d->size) {
    00642         T *i = p->array + d->size;
    00643         T *b = p->array;
    00644         while (i != b)
    00645             *--i = copy;
    00646     }
    00647     return *this;
    00648 }
    00649
    00650 template <typename T>
    00651 QVector<T> &QVector<T>::operator+=(const QVector &l)
    00652 {
    00653     int newSize = d->size + l.d->size;
    00654     realloc(d->size, newSize);
    00655
    00656     T *w = p->array + newSize;
    00657     T *i = l.p->array + l.d->size;
    00658     T *b = l.p->array;
    00659     while (i != b) {
    00660         if (QTypeInfo<T>::isComplex)
    00661             new (--w) T(*--i);
    00662         else
    00663             *--w = *--i;
    00664     }
    00665     d->size = newSize;
    00666     return *this;
    00667 }
    00668
    00669 template <typename T>
    00670 int QVector<T>::indexOf(const T &t, int from) const
    00671 {
    00672     if (from < 0)
    00673         from = qMax(from + d->size, 0);
    00674     if (from < d->size) {
    00675         T* n = p->array + from - 1;
    00676         T* e = p->array + d->size;
    00677         while (++n != e)
    00678             if (*n == t)
    00679                 return n - p->array;
    00680     }
    00681     return -1;
    00682 }
    00683
    00684 template <typename T>
    00685 int QVector<T>::lastIndexOf(const T &t, int from) const
    00686 {
    00687     if (from < 0)
    00688         from += d->size;
    00689     else if (from >= d->size)
    00690         from = d->size-1;
    00691     if (from >= 0) {
    00692         T* b = p->array;
    00693         T* n = p->array + from + 1;
    00694         while (n != b) {
    00695             if (*--n == t)
    00696                 return n - b;
    00697         }
    00698     }
    00699     return -1;
    00700 }
    00701
    00702 template <typename T>
    00703 bool QVector<T>::contains(const T &t) const
    00704 {
    00705     T* b = p->array;
    00706     T* i = p->array + d->size;
    00707     while (i != b)
    00708         if (*--i == t)
    00709             return true;
    00710     return false;
    00711 }
    00712
    00713 template <typename T>
    00714 int QVector<T>::count(const T &t) const
    00715 {
    00716     int c = 0;
    00717     T* b = p->array;
    00718     T* i = p->array + d->size;
    00719     while (i != b)
    00720         if (*--i == t)
    00721             ++c;
    00722     return c;
    00723 }
    00724
    00725 template <typename T>
    00726 Q_OUTOFLINE_TEMPLATE QVector<T> QVector<T>::mid(int pos, int length) const
    00727 {
    00728     if (length < 0)
    00729         length = size() - pos;
    00730     if (pos == 0 && length == size())
    00731         return *this;
    00732     if (pos + length > size())
    00733         length = size() - pos;
    00734     QVector<T> copy;
    00735     copy.reserve(length);
    00736     for (int i = pos; i < pos + length; ++i)
    00737         copy += at(i);
    00738     return copy;
    00739 }
    00740
    00741 template <typename T>
    00742 Q_OUTOFLINE_TEMPLATE QList<T> QVector<T>::toList() const
    00743 {
    00744     QList<T> result;
    00745     result.reserve(size());
    00746     for (int i = 0; i < size(); ++i)
    00747         result.append(at(i));
    00748     return result;
    00749 }
    00750
    00751 template <typename T>
    00752 Q_OUTOFLINE_TEMPLATE QVector<T> QList<T>::toVector() const
    00753 {
    00754     QVector<T> result(size());
    00755     for (int i = 0; i < size(); ++i)
    00756         result[i] = at(i);
    00757     return result;
    00758 }
    00759
    00760 template <typename T>
    00761 QVector<T> QVector<T>::fromList(const QList<T> &list)
    00762 {
    00763     return list.toVector();
    00764 }
    00765
    00766 template <typename T>
    00767 QList<T> QList<T>::fromVector(const QVector<T> &vector)
    00768 {
    00769     return vector.toList();
    00770 }
    00771
    00772 Q_DECLARE_SEQUENTIAL_ITERATOR(Vector)
    00773 Q_DECLARE_MUTABLE_SEQUENTIAL_ITERATOR(Vector)
    00774
    00775 /*
    00776    ### Qt 5:
    00777    ### This needs to be removed for next releases of Qt. It is a workaround for vc++ because
    00778    ### Qt exports QPolygon and QPolygonF that inherit QVector<QPoint> and
    00779    ### QVector<QPointF> respectively.
    00780 */
    00781
    00782 #ifdef Q_CC_MSVC
    00783 QT_BEGIN_INCLUDE_NAMESPACE
    00784 #include <QtCore/QPointF>
    00785 #include <QtCore/QPoint>
    00786 QT_END_INCLUDE_NAMESPACE
    00787
    00788 #if defined(QT_BUILD_CORE_LIB)
    00789 #define Q_TEMPLATE_EXTERN
    00790 #else
    00791 #define Q_TEMPLATE_EXTERN extern
    00792 #endif
    00793 # pragma warning(push)          /* MSVC 6.0 doesn't care about the disabling in qglobal.h (why?), so do it here */
    00794 # pragma warning(disable: 4231) /* nonstandard extension used : 'extern' before template explicit instantiation */
    00795 Q_TEMPLATE_EXTERN template class Q_CORE_EXPORT QVector<QPointF>;
    00796 Q_TEMPLATE_EXTERN template class Q_CORE_EXPORT QVector<QPoint>;
    00797 # pragma warning(pop)
    00798 #endif
    00799
    00800 QT_END_NAMESPACE
    00801
    00802 QT_END_HEADER
    00803
    00804 #endif // QVECTOR_H