1 /****************************************************************************
3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
4 ** All rights reserved.
5 ** Contact: Nokia Corporation (qt-info@nokia.com)
7 ** This file is part of the QtCore module of the Qt Toolkit.
9 ** $QT_BEGIN_LICENSE:LGPL$
10 ** GNU Lesser General Public License Usage
11 ** This file may be used under the terms of the GNU Lesser General Public
12 ** License version 2.1 as published by the Free Software Foundation and
13 ** appearing in the file LICENSE.LGPL included in the packaging of this
14 ** file. Please review the following information to ensure the GNU Lesser
15 ** General Public License version 2.1 requirements will be met:
16 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
18 ** In addition, as a special exception, Nokia gives you certain additional
19 ** rights. These rights are described in the Nokia Qt LGPL Exception
20 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
22 ** GNU General Public License Usage
23 ** Alternatively, this file may be used under the terms of the GNU General
24 ** Public License version 3.0 as published by the Free Software Foundation
25 ** and appearing in the file LICENSE.GPL included in the packaging of this
26 ** file. Please review the following information to ensure the GNU General
27 ** Public License version 3.0 requirements will be met:
28 ** http://www.gnu.org/copyleft/gpl.html.
31 ** Alternatively, this file may be used in accordance with the terms and
32 ** conditions contained in a signed written agreement between you and Nokia.
40 ****************************************************************************/
48 static inline int alignmentThreshold()
50 // malloc on 32-bit platforms should return pointers that are 8-byte aligned or more
51 // while on 64-bit platforms they should be 16-byte aligned or more
52 return 2 * sizeof(void*);
55 const QVectorData QVectorData::shared_null = { Q_REFCOUNT_INITIALIZER(-1), 0, 0, true, false, 0 };
57 QVectorData *QVectorData::malloc(int sizeofTypedData, int size, int sizeofT, QVectorData *init)
59 QVectorData* p = (QVectorData *)qMalloc(sizeofTypedData + (size - 1) * sizeofT);
61 ::memcpy(p, init, sizeofTypedData + (qMin(size, init->alloc) - 1) * sizeofT);
65 QVectorData *QVectorData::allocate(int size, int alignment)
67 return static_cast<QVectorData *>(alignment > alignmentThreshold() ? qMallocAligned(size, alignment) : qMalloc(size));
70 QVectorData *QVectorData::reallocate(QVectorData *x, int newsize, int oldsize, int alignment)
72 if (alignment > alignmentThreshold())
73 return static_cast<QVectorData *>(qReallocAligned(x, newsize, oldsize, alignment));
74 return static_cast<QVectorData *>(qRealloc(x, newsize));
77 void QVectorData::free(QVectorData *x, int alignment)
79 if (alignment > alignmentThreshold())
85 int QVectorData::grow(int sizeofTypedData, int size, int sizeofT, bool excessive)
88 return size + size / 2;
89 return qAllocMore(size * sizeofT, sizeofTypedData - sizeofT) / sizeofT;
94 \brief The QVector class is a template class that provides a dynamic array.
101 QVector\<T\> is one of Qt's generic \l{container classes}. It
102 stores its items in adjacent memory locations and provides fast
105 QList\<T\>, QLinkedList\<T\>, and QVarLengthArray\<T\> provide
106 similar functionality. Here's an overview:
109 \i For most purposes, QList is the right class to use. Operations
110 like prepend() and insert() are usually faster than with
111 QVector because of the way QList stores its items in memory
112 (see \l{Algorithmic Complexity} for details),
113 and its index-based API is more convenient than QLinkedList's
114 iterator-based API. It also expands to less code in your
116 \i If you need a real linked list, with guarantees of \l{constant
117 time} insertions in the middle of the list and iterators to
118 items rather than indexes, use QLinkedList.
119 \i If you want the items to occupy adjacent memory positions, or
120 if your items are larger than a pointer and you want to avoid
121 the overhead of allocating them on the heap individually at
122 insertion time, then use QVector.
123 \i If you want a low-level variable-size array, QVarLengthArray
127 Here's an example of a QVector that stores integers and a QVector
128 that stores QString values:
130 \snippet doc/src/snippets/code/src_corelib_tools_qvector.cpp 0
132 QVector stores a vector (or array) of items. Typically, vectors
133 are created with an initial size. For example, the following code
134 constructs a QVector with 200 elements:
136 \snippet doc/src/snippets/code/src_corelib_tools_qvector.cpp 1
138 The elements are automatically initialized with a
139 \l{default-constructed value}. If you want to initialize the
140 vector with a different value, pass that value as the second
141 argument to the constructor:
143 \snippet doc/src/snippets/code/src_corelib_tools_qvector.cpp 2
145 You can also call fill() at any time to fill the vector with a
148 QVector uses 0-based indexes, just like C++ arrays. To access the
149 item at a particular index position, you can use operator[](). On
150 non-const vectors, operator[]() returns a reference to the item
151 that can be used on the left side of an assignment:
153 \snippet doc/src/snippets/code/src_corelib_tools_qvector.cpp 3
155 For read-only access, an alternative syntax is to use at():
157 \snippet doc/src/snippets/code/src_corelib_tools_qvector.cpp 4
159 at() can be faster than operator[](), because it never causes a
160 \l{deep copy} to occur.
162 Another way to access the data stored in a QVector is to call
163 data(). The function returns a pointer to the first item in the
164 vector. You can use the pointer to directly access and modify the
165 elements stored in the vector. The pointer is also useful if you
166 need to pass a QVector to a function that accepts a plain C++
169 If you want to find all occurrences of a particular value in a
170 vector, use indexOf() or lastIndexOf(). The former searches
171 forward starting from a given index position, the latter searches
172 backward. Both return the index of the matching item if they found
173 one; otherwise, they return -1. For example:
175 \snippet doc/src/snippets/code/src_corelib_tools_qvector.cpp 5
177 If you simply want to check whether a vector contains a
178 particular value, use contains(). If you want to find out how
179 many times a particular value occurs in the vector, use count().
181 QVector provides these basic functions to add, move, and remove
182 items: insert(), replace(), remove(), prepend(), append(). With
183 the exception of append() and replace(), these functions can be slow
184 (\l{linear time}) for large vectors, because they require moving many
185 items in the vector by one position in memory. If you want a container
186 class that provides fast insertion/removal in the middle, use
187 QList or QLinkedList instead.
189 Unlike plain C++ arrays, QVectors can be resized at any time by
190 calling resize(). If the new size is larger than the old size,
191 QVector might need to reallocate the whole vector. QVector tries
192 to reduce the number of reallocations by preallocating up to twice
193 as much memory as the actual data needs.
195 If you know in advance approximately how many items the QVector
196 will contain, you can call reserve(), asking QVector to
197 preallocate a certain amount of memory. You can also call
198 capacity() to find out how much memory QVector actually
201 Note that using non-const operators and functions can cause
202 QVector to do a deep copy of the data. This is due to \l{implicit sharing}.
204 QVector's value type must be an \l{assignable data type}. This
205 covers most data types that are commonly used, but the compiler
206 won't let you, for example, store a QWidget as a value; instead,
207 store a QWidget *. A few functions have additional requirements;
208 for example, indexOf() and lastIndexOf() expect the value type to
209 support \c operator==(). These requirements are documented on a
212 Like the other container classes, QVector provides \l{Java-style
213 iterators} (QVectorIterator and QMutableVectorIterator) and
214 \l{STL-style iterators} (QVector::const_iterator and
215 QVector::iterator). In practice, these are rarely used, because
216 you can use indexes into the QVector.
218 In addition to QVector, Qt also provides QVarLengthArray, a very
219 low-level class with little functionality that is optimized for
222 QVector does \e not support inserting, prepending, appending or replacing
223 with references to its own values. Doing so will cause your application to
224 abort with an error message.
226 \sa QVectorIterator, QMutableVectorIterator, QList, QLinkedList
230 \fn QVector<T> QVector::mid(int pos, int length = -1) const
232 Returns a vector whose elements are copied from this vector,
233 starting at position \a pos. If \a length is -1 (the default), all
234 elements after \a pos are copied; otherwise \a length elements (or
235 all remaining elements if there are less than \a length elements)
240 /*! \fn QVector::QVector()
242 Constructs an empty vector.
247 /*! \fn QVector::QVector(int size)
249 Constructs a vector with an initial size of \a size elements.
251 The elements are initialized with a \l{default-constructed
257 /*! \fn QVector::QVector(int size, const T &value)
259 Constructs a vector with an initial size of \a size elements.
260 Each element is initialized with \a value.
265 /*! \fn QVector::QVector(const QVector<T> &other)
267 Constructs a copy of \a other.
269 This operation takes \l{constant time}, because QVector is
270 \l{implicitly shared}. This makes returning a QVector from a
271 function very fast. If a shared instance is modified, it will be
272 copied (copy-on-write), and that takes \l{linear time}.
277 /*! \fn QVector::QVector(std::initializer_list<T> args)
280 Construct a vector from the std::initilizer_list given by \a args.
282 This constructor is only enabled if the compiler supports C++0x
286 /*! \fn QVector::~QVector()
291 /*! \fn QVector<T> &QVector::operator=(const QVector<T> &other)
293 Assigns \a other to this vector and returns a reference to this
297 /*! \fn void QVector::swap(QVector<T> &other)
300 Swaps vector \a other with this vector. This operation is very fast and
304 /*! \fn bool QVector::operator==(const QVector<T> &other) const
306 Returns true if \a other is equal to this vector; otherwise
309 Two vectors are considered equal if they contain the same values
312 This function requires the value type to have an implementation
318 /*! \fn bool QVector::operator!=(const QVector<T> &other) const
320 Returns true if \a other is not equal to this vector; otherwise
323 Two vectors are considered equal if they contain the same values
326 This function requires the value type to have an implementation
332 /*! \fn int QVector::size() const
334 Returns the number of items in the vector.
336 \sa isEmpty(), resize()
339 /*! \fn bool QVector::isEmpty() const
341 Returns true if the vector has size 0; otherwise returns false.
346 /*! \fn void QVector::resize(int size)
348 Sets the size of the vector to \a size. If \a size is greater than the
349 current size, elements are added to the end; the new elements are
350 initialized with a \l{default-constructed value}. If \a size is less
351 than the current size, elements are removed from the end.
356 /*! \fn int QVector::capacity() const
358 Returns the maximum number of items that can be stored in the
359 vector without forcing a reallocation.
361 The sole purpose of this function is to provide a means of fine
362 tuning QVector's memory usage. In general, you will rarely ever
363 need to call this function. If you want to know how many items are
364 in the vector, call size().
366 \sa reserve(), squeeze()
369 /*! \fn void QVector::reserve(int size)
371 Attempts to allocate memory for at least \a size elements. If you
372 know in advance how large the vector will be, you can call this
373 function, and if you call resize() often you are likely to get
374 better performance. If \a size is an underestimate, the worst
375 that will happen is that the QVector will be a bit slower.
377 The sole purpose of this function is to provide a means of fine
378 tuning QVector's memory usage. In general, you will rarely ever
379 need to call this function. If you want to change the size of the
380 vector, call resize().
382 \sa squeeze(), capacity()
385 /*! \fn void QVector::squeeze()
387 Releases any memory not required to store the items.
389 The sole purpose of this function is to provide a means of fine
390 tuning QVector's memory usage. In general, you will rarely ever
391 need to call this function.
393 \sa reserve(), capacity()
396 /*! \fn void QVector::detach()
401 /*! \fn bool QVector::isDetached() const
406 /*! \fn void QVector::setSharable(bool sharable)
411 /*! \fn bool QVector::isSharedWith(const QVector<T> &other) const
416 /*! \fn T *QVector::data()
418 Returns a pointer to the data stored in the vector. The pointer
419 can be used to access and modify the items in the vector.
422 \snippet doc/src/snippets/code/src_corelib_tools_qvector.cpp 6
424 The pointer remains valid as long as the vector isn't
427 This function is mostly useful to pass a vector to a function
428 that accepts a plain C++ array.
430 \sa constData(), operator[]()
433 /*! \fn const T *QVector::data() const
438 /*! \fn const T *QVector::constData() const
440 Returns a const pointer to the data stored in the vector. The
441 pointer can be used to access the items in the vector.
442 The pointer remains valid as long as the vector isn't
445 This function is mostly useful to pass a vector to a function
446 that accepts a plain C++ array.
448 \sa data(), operator[]()
451 /*! \fn void QVector::clear()
453 Removes all the elements from the vector and releases the memory used by
457 /*! \fn const T &QVector::at(int i) const
459 Returns the item at index position \a i in the vector.
461 \a i must be a valid index position in the vector (i.e., 0 <= \a
464 \sa value(), operator[]()
467 /*! \fn T &QVector::operator[](int i)
469 Returns the item at index position \a i as a modifiable reference.
471 \a i must be a valid index position in the vector (i.e., 0 <= \a i
474 Note that using non-const operators can cause QVector to do a deep
480 /*! \fn const T &QVector::operator[](int i) const
488 \fn void QVector::append(const T &value)
490 Inserts \a value at the end of the vector.
493 \snippet doc/src/snippets/code/src_corelib_tools_qvector.cpp 7
495 This is the same as calling resize(size() + 1) and assigning \a
496 value to the new last element in the vector.
498 This operation is relatively fast, because QVector typically
499 allocates more memory than necessary, so it can grow without
500 reallocating the entire vector each time.
502 \sa operator<<(), prepend(), insert()
505 /*! \fn void QVector::prepend(const T &value)
507 Inserts \a value at the beginning of the vector.
510 \snippet doc/src/snippets/code/src_corelib_tools_qvector.cpp 8
512 This is the same as vector.insert(0, \a value).
514 For large vectors, this operation can be slow (\l{linear time}),
515 because it requires moving all the items in the vector by one
516 position further in memory. If you want a container class that
517 provides a fast prepend() function, use QList or QLinkedList
520 \sa append(), insert()
523 /*! \fn void QVector::insert(int i, const T &value)
525 Inserts \a value at index position \a i in the vector. If \a i is
526 0, the value is prepended to the vector. If \a i is size(), the
527 value is appended to the vector.
530 \snippet doc/src/snippets/code/src_corelib_tools_qvector.cpp 9
532 For large vectors, this operation can be slow (\l{linear time}),
533 because it requires moving all the items at indexes \a i and
534 above by one position further in memory. If you want a container
535 class that provides a fast insert() function, use QLinkedList
538 \sa append(), prepend(), remove()
541 /*! \fn void QVector::insert(int i, int count, const T &value)
545 Inserts \a count copies of \a value at index position \a i in the
549 \snippet doc/src/snippets/code/src_corelib_tools_qvector.cpp 10
552 /*! \fn QVector::iterator QVector::insert(iterator before, const T &value)
556 Inserts \a value in front of the item pointed to by the iterator
557 \a before. Returns an iterator pointing at the inserted item.
560 /*! \fn QVector::iterator QVector::insert(iterator before, int count, const T &value)
562 Inserts \a count copies of \a value in front of the item pointed to
563 by the iterator \a before. Returns an iterator pointing at the
564 first of the inserted items.
567 /*! \fn void QVector::replace(int i, const T &value)
569 Replaces the item at index position \a i with \a value.
571 \a i must be a valid index position in the vector (i.e., 0 <= \a
574 \sa operator[](), remove()
577 /*! \fn void QVector::remove(int i)
581 Removes the element at index position \a i.
583 \sa insert(), replace(), fill()
586 /*! \fn void QVector::remove(int i, int count)
590 Removes \a count elements from the middle of the vector, starting at
593 \sa insert(), replace(), fill()
596 /*! \fn QVector &QVector::fill(const T &value, int size = -1)
598 Assigns \a value to all items in the vector. If \a size is
599 different from -1 (the default), the vector is resized to size \a
603 \snippet doc/src/snippets/code/src_corelib_tools_qvector.cpp 11
608 /*! \fn int QVector::indexOf(const T &value, int from = 0) const
610 Returns the index position of the first occurrence of \a value in
611 the vector, searching forward from index position \a from.
612 Returns -1 if no item matched.
615 \snippet doc/src/snippets/code/src_corelib_tools_qvector.cpp 12
617 This function requires the value type to have an implementation of
620 \sa lastIndexOf(), contains()
623 /*! \fn int QVector::lastIndexOf(const T &value, int from = -1) const
625 Returns the index position of the last occurrence of the value \a
626 value in the vector, searching backward from index position \a
627 from. If \a from is -1 (the default), the search starts at the
628 last item. Returns -1 if no item matched.
631 \snippet doc/src/snippets/code/src_corelib_tools_qvector.cpp 13
633 This function requires the value type to have an implementation of
639 /*! \fn bool QVector::contains(const T &value) const
641 Returns true if the vector contains an occurrence of \a value;
642 otherwise returns false.
644 This function requires the value type to have an implementation of
647 \sa indexOf(), count()
650 /*! \fn bool QVector::startsWith(const T &value) const
653 Returns true if this vector is not empty and its first
654 item is equal to \a value; otherwise returns false.
656 \sa isEmpty(), first()
659 /*! \fn bool QVector::endsWith(const T &value) const
662 Returns true if this vector is not empty and its last
663 item is equal to \a value; otherwise returns false.
665 \sa isEmpty(), last()
669 /*! \fn int QVector::count(const T &value) const
671 Returns the number of occurrences of \a value in the vector.
673 This function requires the value type to have an implementation of
676 \sa contains(), indexOf()
679 /*! \fn int QVector::count() const
686 /*! \fn QVector::iterator QVector::begin()
688 Returns an \l{STL-style iterator} pointing to the first item in
691 \sa constBegin(), end()
694 /*! \fn QVector::const_iterator QVector::begin() const
699 /*! \fn QVector::const_iterator QVector::constBegin() const
701 Returns a const \l{STL-style iterator} pointing to the first item
704 \sa begin(), constEnd()
707 /*! \fn QVector::iterator QVector::end()
709 Returns an \l{STL-style iterator} pointing to the imaginary item
710 after the last item in the vector.
712 \sa begin(), constEnd()
715 /*! \fn QVector::const_iterator QVector::end() const
720 /*! \fn QVector::const_iterator QVector::constEnd() const
722 Returns a const \l{STL-style iterator} pointing to the imaginary
723 item after the last item in the vector.
725 \sa constBegin(), end()
728 /*! \fn QVector::iterator QVector::erase(iterator pos)
730 Removes the item pointed to by the iterator \a pos from the
731 vector, and returns an iterator to the next item in the vector
732 (which may be end()).
734 \sa insert(), remove()
737 /*! \fn QVector::iterator QVector::erase(iterator begin, iterator end)
741 Removes all the items from \a begin up to (but not including) \a
742 end. Returns an iterator to the same item that \a end referred to
746 /*! \fn T& QVector::first()
748 Returns a reference to the first item in the vector. This
749 function assumes that the vector isn't empty.
751 \sa last(), isEmpty()
754 /*! \fn const T& QVector::first() const
759 /*! \fn T& QVector::last()
761 Returns a reference to the last item in the vector. This function
762 assumes that the vector isn't empty.
764 \sa first(), isEmpty()
767 /*! \fn const T& QVector::last() const
772 /*! \fn T QVector::value(int i) const
774 Returns the value at index position \a i in the vector.
776 If the index \a i is out of bounds, the function returns
777 a \l{default-constructed value}. If you are certain that
778 \a i is within bounds, you can use at() instead, which is slightly
781 \sa at(), operator[]()
784 /*! \fn T QVector::value(int i, const T &defaultValue) const
788 If the index \a i is out of bounds, the function returns
792 /*! \fn void QVector::push_back(const T &value)
794 This function is provided for STL compatibility. It is equivalent
798 /*! \fn void QVector::push_front(const T &value)
800 This function is provided for STL compatibility. It is equivalent
801 to prepend(\a value).
804 /*! \fn void QVector::pop_front()
806 This function is provided for STL compatibility. It is equivalent
810 /*! \fn void QVector::pop_back()
812 This function is provided for STL compatibility. It is equivalent
816 /*! \fn T& QVector::front()
818 This function is provided for STL compatibility. It is equivalent
822 /*! \fn QVector::const_reference QVector::front() const
827 /*! \fn QVector::reference QVector::back()
829 This function is provided for STL compatibility. It is equivalent
833 /*! \fn QVector::const_reference QVector::back() const
838 /*! \fn bool QVector::empty() const
840 This function is provided for STL compatibility. It is equivalent
841 to isEmpty(), returning true if the vector is empty; otherwise
845 /*! \fn QVector<T> &QVector::operator+=(const QVector<T> &other)
847 Appends the items of the \a other vector to this vector and
848 returns a reference to this vector.
850 \sa operator+(), append()
853 /*! \fn void QVector::operator+=(const T &value)
857 Appends \a value to the vector.
859 \sa append(), operator<<()
862 /*! \fn QVector<T> QVector::operator+(const QVector<T> &other) const
864 Returns a vector that contains all the items in this vector
865 followed by all the items in the \a other vector.
870 /*! \fn QVector<T> &QVector::operator<<(const T &value)
872 Appends \a value to the vector and returns a reference to this
875 \sa append(), operator+=()
878 /*! \fn QVector<T> &QVector::operator<<(const QVector<T> &other)
880 Appends \a other to the vector and returns a reference to the
884 /*! \typedef QVector::iterator
886 The QVector::iterator typedef provides an STL-style non-const
887 iterator for QVector and QStack.
889 QVector provides both \l{STL-style iterators} and \l{Java-style
890 iterators}. The STL-style non-const iterator is simply a typedef
891 for "T *" (pointer to T).
893 \sa QVector::begin(), QVector::end(), QVector::const_iterator, QMutableVectorIterator
896 /*! \typedef QVector::const_iterator
898 The QVector::const_iterator typedef provides an STL-style const
899 iterator for QVector and QStack.
901 QVector provides both \l{STL-style iterators} and \l{Java-style
902 iterators}. The STL-style const iterator is simply a typedef for
903 "const T *" (pointer to const T).
905 \sa QVector::constBegin(), QVector::constEnd(), QVector::iterator, QVectorIterator
908 /*! \typedef QVector::Iterator
910 Qt-style synonym for QVector::iterator.
913 /*! \typedef QVector::ConstIterator
915 Qt-style synonym for QVector::const_iterator.
918 /*! \typedef QVector::const_pointer
920 Typedef for const T *. Provided for STL compatibility.
923 /*! \typedef QVector::const_reference
925 Typedef for T &. Provided for STL compatibility.
928 /*! \typedef QVector::difference_type
930 Typedef for ptrdiff_t. Provided for STL compatibility.
933 /*! \typedef QVector::pointer
935 Typedef for T *. Provided for STL compatibility.
938 /*! \typedef QVector::reference
940 Typedef for T &. Provided for STL compatibility.
943 /*! \typedef QVector::size_type
945 Typedef for int. Provided for STL compatibility.
948 /*! \typedef QVector::value_type
950 Typedef for T. Provided for STL compatibility.
953 /*! \fn QList<T> QVector<T>::toList() const
955 Returns a QList object with the data contained in this QVector.
959 \snippet doc/src/snippets/code/src_corelib_tools_qvector.cpp 14
961 \sa fromList(), QList::fromVector()
964 /*! \fn QVector<T> QVector<T>::fromList(const QList<T> &list)
966 Returns a QVector object with the data contained in \a list.
970 \snippet doc/src/snippets/code/src_corelib_tools_qvector.cpp 15
972 \sa toList(), QList::toVector()
975 /*! \fn QVector<T> QVector<T>::fromStdVector(const std::vector<T> &vector)
977 Returns a QVector object with the data contained in \a vector. The
978 order of the elements in the QVector is the same as in \a vector.
982 \snippet doc/src/snippets/code/src_corelib_tools_qvector.cpp 16
984 \sa toStdVector(), QList::fromStdList()
987 /*! \fn std::vector<T> QVector<T>::toStdVector() const
989 Returns a std::vector object with the data contained in this QVector.
992 \snippet doc/src/snippets/code/src_corelib_tools_qvector.cpp 17
994 \sa fromStdVector(), QList::toStdList()
997 /*! \fn QDataStream &operator<<(QDataStream &out, const QVector<T> &vector)
1000 Writes the vector \a vector to stream \a out.
1002 This function requires the value type to implement \c operator<<().
1004 \sa \link datastreamformat.html Format of the QDataStream operators \endlink
1007 /*! \fn QDataStream &operator>>(QDataStream &in, QVector<T> &vector)
1010 Reads a vector from stream \a in into \a vector.
1012 This function requires the value type to implement \c operator>>().
1014 \sa \link datastreamformat.html Format of the QDataStream operators \endlink