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 ****************************************************************************/
52 QList as an array-list combines the easy-of-use of a random
53 access interface with fast list operations and the low memory
54 management overhead of an array. Accessing elements by index,
55 appending, prepending, and removing elements from both the front
56 and the back all happen in constant time O(1). Inserting or
57 removing elements at random index positions \ai happens in linear
58 time, or more precisly in O(min{i,n-i}) <= O(n/2), with n being
59 the number of elements in the list.
62 const QListData::Data QListData::shared_null = { Q_REFCOUNT_INITIALIZE_STATIC, 0, 0, 0, { 0 } };
64 static int grow(int size)
66 // dear compiler: don't optimize me out.
67 volatile int x = qAllocMore(size * sizeof(void *), QListData::DataHeaderSize) / sizeof(void *);
72 * Detaches the QListData by allocating new memory for a list which will be bigger
73 * than the copied one and is expected to grow further.
74 * *idx is the desired insertion point and is clamped to the actual size of the list.
75 * num is the number of new elements to insert at the insertion point.
76 * Returns the old (shared) data, it is up to the caller to deref() and free().
77 * For the new data node_copy needs to be called.
81 QListData::Data *QListData::detach_grow(int *idx, int num)
84 int l = x->end - x->begin;
87 Data* t = static_cast<Data *>(::malloc(DataHeaderSize + alloc * sizeof(void *)));
90 t->ref.initializeOwned();
92 // The space reservation algorithm's optimization is biased towards appending:
93 // Something which looks like an append will put the data at the beginning,
94 // while something which looks like a prepend will put it in the middle
95 // instead of at the end. That's based on the assumption that prepending
96 // is uncommon and even an initial prepend will eventually be followed by
97 // at least some appends.
101 bg = (alloc - nl) >> 1;
102 } else if (*idx > l) {
105 } else if (*idx < (l >> 1)) {
106 bg = (alloc - nl) >> 1;
118 * Detaches the QListData by allocating new memory for a list which possibly
119 * has a different size than the copied one.
120 * Returns the old (shared) data, it is up to the caller to deref() and free()
121 * For the new data node_copy needs to be called.
125 QListData::Data *QListData::detach(int alloc)
128 Data* t = static_cast<Data *>(::malloc(DataHeaderSize + alloc * sizeof(void *)));
131 t->ref.initializeOwned();
145 void QListData::realloc(int alloc)
147 Q_ASSERT(!d->ref.isShared());
148 Data *x = static_cast<Data *>(::realloc(d, DataHeaderSize + alloc * sizeof(void *)));
154 d->begin = d->end = 0;
157 // ensures that enough space is available to append n elements
158 void **QListData::append(int n)
160 Q_ASSERT(!d->ref.isShared());
162 if (e + n > d->alloc) {
164 if (b - n >= 2 * d->alloc / 3) {
165 // we have enough space. Just not at the end -> move it.
167 ::memcpy(d->array, d->array + b, e * sizeof(void *));
170 realloc(grow(d->alloc + n));
177 // ensures that enough space is available to append one element
178 void **QListData::append()
183 // ensures that enough space is available to append the list
184 void **QListData::append(const QListData& l)
186 return append(l.d->end - l.d->begin);
189 void **QListData::prepend()
191 Q_ASSERT(!d->ref.isShared());
193 if (d->end >= d->alloc / 3)
194 realloc(grow(d->alloc + 1));
196 if (d->end < d->alloc / 3)
197 d->begin = d->alloc - 2 * d->end;
199 d->begin = d->alloc - d->end;
201 ::memmove(d->array + d->begin, d->array, d->end * sizeof(void *));
204 return d->array + --d->begin;
207 void **QListData::insert(int i)
209 Q_ASSERT(!d->ref.isShared());
212 int size = d->end - d->begin;
216 bool leftward = false;
219 if (d->end == d->alloc) {
220 // If the array is full, we expand it and move some items rightward
221 realloc(grow(d->alloc + 1));
223 // If there is free space at the end of the array, we move some items rightward
226 if (d->end == d->alloc) {
227 // If there is free space at the beginning of the array, we move some items leftward
230 // If there is free space at both ends, we move as few items as possible
231 leftward = (i < size - i);
237 ::memmove(d->array + d->begin, d->array + d->begin + 1, i * sizeof(void *));
239 ::memmove(d->array + d->begin + i + 1, d->array + d->begin + i,
240 (size - i) * sizeof(void *));
243 return d->array + d->begin + i;
246 void QListData::remove(int i)
248 Q_ASSERT(!d->ref.isShared());
250 if (i - d->begin < d->end - i) {
251 if (int offset = i - d->begin)
252 ::memmove(d->array + d->begin + 1, d->array + d->begin, offset * sizeof(void *));
255 if (int offset = d->end - i - 1)
256 ::memmove(d->array + i, d->array + i + 1, offset * sizeof(void *));
261 void QListData::remove(int i, int n)
263 Q_ASSERT(!d->ref.isShared());
265 int middle = i + n/2;
266 if (middle - d->begin < d->end - middle) {
267 ::memmove(d->array + d->begin + n, d->array + d->begin,
268 (i - d->begin) * sizeof(void*));
271 ::memmove(d->array + i, d->array + i + n,
272 (d->end - i - n) * sizeof(void*));
277 void QListData::move(int from, int to)
279 Q_ASSERT(!d->ref.isShared());
285 void *t = d->array[from];
288 if (d->end == d->alloc || 3 * (to - from) < 2 * (d->end - d->begin)) {
289 ::memmove(d->array + from, d->array + from + 1, (to - from) * sizeof(void *));
292 if (int offset = from - d->begin)
293 ::memmove(d->array + d->begin + 1, d->array + d->begin, offset * sizeof(void *));
294 if (int offset = d->end - (to + 1))
295 ::memmove(d->array + to + 2, d->array + to + 1, offset * sizeof(void *));
301 if (d->begin == 0 || 3 * (from - to) < 2 * (d->end - d->begin)) {
302 ::memmove(d->array + to + 1, d->array + to, (from - to) * sizeof(void *));
305 if (int offset = to - d->begin)
306 ::memmove(d->array + d->begin - 1, d->array + d->begin, offset * sizeof(void *));
307 if (int offset = d->end - (from + 1))
308 ::memmove(d->array + from, d->array + from + 1, offset * sizeof(void *));
317 void **QListData::erase(void **xi)
319 Q_ASSERT(!d->ref.isShared());
320 int i = xi - (d->array + d->begin);
322 return d->array + d->begin + i;
326 \brief The QList class is a template class that provides lists.
333 QList\<T\> is one of Qt's generic \l{container classes}. It
334 stores a list of values and provides fast index-based access as
335 well as fast insertions and removals.
337 QList\<T\>, QLinkedList\<T\>, and QVector\<T\> provide similar
338 functionality. Here's an overview:
341 \li For most purposes, QList is the right class to use. Its
342 index-based API is more convenient than QLinkedList's
343 iterator-based API, and it is usually faster than
344 QVector because of the way it stores its items in
345 memory. It also expands to less code in your executable.
346 \li If you need a real linked list, with guarantees of \l{constant
347 time} insertions in the middle of the list and iterators to
348 items rather than indexes, use QLinkedList.
349 \li If you want the items to occupy adjacent memory positions,
354 Internally, QList\<T\> is represented as an array of pointers to
355 items of type T. If T is itself a pointer type or a basic type
356 that is no larger than a pointer, or if T is one of Qt's \l{shared
357 classes}, then QList\<T\> stores the items directly in the pointer
358 array. For lists under a thousand items, this array representation
359 allows for very fast insertions in the middle, and it allows
360 index-based access. Furthermore, operations like prepend() and
361 append() are very fast, because QList preallocates memory at both
362 ends of its internal array. (See \l{Algorithmic Complexity} for
363 details.) Note, however, that for unshared list items that are
364 larger than a pointer, each append or insert of a new item
365 requires allocating the new item on the heap, and this per item
366 allocation might make QVector a better choice in cases that do
367 lots of appending or inserting, since QVector allocates memory for
368 its items in a single heap allocation.
370 Note that the internal array only ever gets bigger over the life
371 of the list. It never shrinks. The internal array is deallocated
372 by the destructor and by the assignment operator, when one list
373 is assigned to another.
375 Here's an example of a QList that stores integers and
376 a QList that stores QDate values:
378 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 0
380 Qt includes a QStringList class that inherits QList\<QString\>
381 and adds a few convenience functions, such as QStringList::join()
382 and QStringList::find(). (QString::split() creates QStringLists
385 QList stores a list of items. The default constructor creates an
386 empty list. To insert items into the list, you can use
389 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 1
391 QList provides these basic functions to add, move, and remove
392 items: insert(), replace(), removeAt(), move(), and swap(). In
393 addition, it provides the following convenience functions:
394 append(), prepend(), removeFirst(), and removeLast().
396 QList uses 0-based indexes, just like C++ arrays. To access the
397 item at a particular index position, you can use operator[](). On
398 non-const lists, operator[]() returns a reference to the item and
399 can be used on the left side of an assignment:
401 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 2
403 Because QList is implemented as an array of pointers, this
404 operation is very fast (\l{constant time}). For read-only access,
405 an alternative syntax is to use at():
407 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 3
409 at() can be faster than operator[](), because it never causes a
410 \l{deep copy} to occur.
412 A common requirement is to remove an item from a list and do
413 something with it. For this, QList provides takeAt(), takeFirst(),
414 and takeLast(). Here's a loop that removes the items from a list
415 one at a time and calls \c delete on them:
417 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 4
419 Inserting and removing items at either ends of the list is very
420 fast (\l{constant time} in most cases), because QList
421 preallocates extra space on both sides of its internal buffer to
422 allow for fast growth at both ends of the list.
424 If you want to find all occurrences of a particular value in a
425 list, use indexOf() or lastIndexOf(). The former searches forward
426 starting from a given index position, the latter searches
427 backward. Both return the index of a matching item if they find
428 it; otherwise, they return -1. For example:
430 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 5
432 If you simply want to check whether a list contains a particular
433 value, use contains(). If you want to find out how many times a
434 particular value occurs in the list, use count(). If you want to
435 replace all occurrences of a particular value with another, use
438 QList's value type must be an \l{assignable data type}. This
439 covers most data types that are commonly used, but the compiler
440 won't let you, for example, store a QWidget as a value; instead,
441 store a QWidget *. A few functions have additional requirements;
442 for example, indexOf() and lastIndexOf() expect the value type to
443 support \c operator==(). These requirements are documented on a
446 Like the other container classes, QList provides \l{Java-style
447 iterators} (QListIterator and QMutableListIterator) and
448 \l{STL-style iterators} (QList::const_iterator and
449 QList::iterator). In practice, these are rarely used, because you
450 can use indexes into the QList. QList is implemented in such a way
451 that direct index-based access is just as fast as using iterators.
453 QList does \e not support inserting, prepending, appending or
454 replacing with references to its own values. Doing so will cause
455 your application to abort with an error message.
457 To make QList as efficient as possible, its member functions don't
458 validate their input before using it. Except for isEmpty(), member
459 functions always assume the list is \e not empty. Member functions
460 that take index values as parameters always assume their index
461 value parameters are in the valid range. This means QList member
462 functions can fail. If you define QT_NO_DEBUG when you compile,
463 failures will not be detected. If you \e don't define QT_NO_DEBUG,
464 failures will be detected using Q_ASSERT() or Q_ASSERT_X() with an
467 To avoid failures when your list can be empty, call isEmpty()
468 before calling other member functions. If you must pass an index
469 value that might not be in the valid range, check that it is less
470 than the value returned by size() but \e not less than 0.
472 \sa QListIterator, QMutableListIterator, QLinkedList, QVector
476 \fn QList<T> QList<T>::mid(int pos, int length) const
478 Returns a list whose elements are copied from this list,
479 starting at position \a pos. If \a length is -1 (the default), all
480 elements from \a pos are copied; otherwise \a length elements (or
481 all remaining elements if there are less than \a length elements)
485 /*! \fn QList::QList()
487 Constructs an empty list.
490 /*! \fn QList::QList(const QList<T> &other)
492 Constructs a copy of \a other.
494 This operation takes \l{constant time}, because QList is
495 \l{implicitly shared}. This makes returning a QList from a
496 function very fast. If a shared instance is modified, it will be
497 copied (copy-on-write), and that takes \l{linear time}.
502 /*! \fn inline QList::QList(std::initializer_list<T> args)
505 Construct a list from the std::initializer_list specified by \a args.
507 This constructor is only enabled if the compiler supports C++0x
510 /*! \fn QList::~QList()
512 Destroys the list. References to the values in the list and all
513 iterators of this list become invalid.
516 /*! \fn QList<T> &QList::operator=(const QList<T> &other)
518 Assigns \a other to this list and returns a reference to this
522 /*! \fn void QList::swap(QList<T> &other)
525 Swaps list \a other with this list. This operation is very
526 fast and never fails.
529 /*! \fn bool QList::operator==(const QList<T> &other) const
531 Returns true if \a other is equal to this list; otherwise returns
534 Two lists are considered equal if they contain the same values in
537 This function requires the value type to have an implementation of
543 /*! \fn bool QList::operator!=(const QList<T> &other) const
545 Returns true if \a other is not equal to this list; otherwise
548 Two lists are considered equal if they contain the same values in
551 This function requires the value type to have an implementation of
558 \fn int QList::size() const
560 Returns the number of items in the list.
562 \sa isEmpty(), count()
565 /*! \fn void QList::detach()
570 /*! \fn void QList::detachShared()
574 like detach(), but does nothing if we're shared_null.
575 This prevents needless mallocs, and makes QList more exception safe
576 in case of cleanup work done in destructors on empty lists.
579 /*! \fn bool QList::isDetached() const
584 /*! \fn void QList::setSharable(bool sharable)
589 /*! \fn bool QList::isSharedWith(const QList<T> &other) const
594 /*! \fn bool QList::isEmpty() const
596 Returns true if the list contains no items; otherwise returns
602 /*! \fn void QList::clear()
604 Removes all items from the list.
609 /*! \fn const T &QList::at(int i) const
611 Returns the item at index position \a i in the list. \a i must be
612 a valid index position in the list (i.e., 0 <= \a i < size()).
614 This function is very fast (\l{constant time}).
616 \sa value(), operator[]()
619 /*! \fn T &QList::operator[](int i)
621 Returns the item at index position \a i as a modifiable reference.
622 \a i must be a valid index position in the list (i.e., 0 <= \a i <
625 This function is very fast (\l{constant time}).
630 /*! \fn const T &QList::operator[](int i) const
637 /*! \fn QList::reserve(int alloc)
639 Reserve space for \a alloc elements.
641 If \a alloc is smaller than the current size of the list, nothing will happen.
643 Use this function to avoid repetetive reallocation of QList's internal
644 data if you can predict how many elements will be appended.
645 Note that the reservation applies only to the internal pointer array.
650 /*! \fn void QList::append(const T &value)
652 Inserts \a value at the end of the list.
655 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 6
657 This is the same as list.insert(size(), \a value).
659 This operation is typically very fast (\l{constant time}),
660 because QList preallocates extra space on both sides of its
661 internal buffer to allow for fast growth at both ends of the
664 \sa operator<<(), prepend(), insert()
667 /*! \fn void QList::append(const QList<T> &value)
673 Appends the items of the \a value list to this list.
675 \sa operator<<(), operator+=()
678 /*! \fn void QList::prepend(const T &value)
680 Inserts \a value at the beginning of the list.
683 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 7
685 This is the same as list.insert(0, \a value).
687 This operation is usually very fast (\l{constant time}), because
688 QList preallocates extra space on both sides of its internal
689 buffer to allow for fast growth at both ends of the list.
691 \sa append(), insert()
694 /*! \fn void QList::insert(int i, const T &value)
696 Inserts \a value at index position \a i in the list. If \a i
697 is 0, the value is prepended to the list. If \a i is size(), the
698 value is appended to the list.
701 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 8
703 \sa append(), prepend(), replace(), removeAt()
706 /*! \fn QList::iterator QList::insert(iterator before, const T &value)
710 Inserts \a value in front of the item pointed to by the
711 iterator \a before. Returns an iterator pointing at the inserted
712 item. Note that the iterator passed to the function will be
713 invalid after the call; the returned iterator should be used
717 /*! \fn void QList::replace(int i, const T &value)
719 Replaces the item at index position \a i with \a value. \a i must
720 be a valid index position in the list (i.e., 0 <= \a i < size()).
722 \sa operator[](), removeAt()
726 \fn int QList::removeAll(const T &value)
728 Removes all occurrences of \a value in the list and returns the
729 number of entries removed.
732 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 9
734 This function requires the value type to have an implementation of
737 \sa removeOne(), removeAt(), takeAt(), replace()
741 \fn bool QList::removeOne(const T &value)
744 Removes the first occurrence of \a value in the list and returns
745 true on success; otherwise returns false.
748 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 10
750 This function requires the value type to have an implementation of
753 \sa removeAll(), removeAt(), takeAt(), replace()
756 /*! \fn void QList::removeAt(int i)
758 Removes the item at index position \a i. \a i must be a valid
759 index position in the list (i.e., 0 <= \a i < size()).
761 \sa takeAt(), removeFirst(), removeLast(), removeOne()
764 /*! \fn T QList::takeAt(int i)
766 Removes the item at index position \a i and returns it. \a i must
767 be a valid index position in the list (i.e., 0 <= \a i < size()).
769 If you don't use the return value, removeAt() is more efficient.
771 \sa removeAt(), takeFirst(), takeLast()
774 /*! \fn T QList::takeFirst()
776 Removes the first item in the list and returns it. This is the
777 same as takeAt(0). This function assumes the list is not empty. To
778 avoid failure, call isEmpty() before calling this function.
780 This operation takes \l{constant time}.
782 If you don't use the return value, removeFirst() is more
785 \sa takeLast(), takeAt(), removeFirst()
788 /*! \fn T QList::takeLast()
790 Removes the last item in the list and returns it. This is the
791 same as takeAt(size() - 1). This function assumes the list is
792 not empty. To avoid failure, call isEmpty() before calling this
795 This operation takes \l{constant time}.
797 If you don't use the return value, removeLast() is more
800 \sa takeFirst(), takeAt(), removeLast()
803 /*! \fn void QList::move(int from, int to)
805 Moves the item at index position \a from to index position \a to.
808 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 11
810 This is the same as insert(\a{to}, takeAt(\a{from})).This function
811 assumes that both \a from and \a to are at least 0 but less than
812 size(). To avoid failure, test that both \a from and \a to are at
813 least 0 and less than size().
815 \sa swap(), insert(), takeAt()
818 /*! \fn void QList::swap(int i, int j)
820 Exchange the item at index position \a i with the item at index
821 position \a j. This function assumes that both \a i and \a j are
822 at least 0 but less than size(). To avoid failure, test that both
823 \a i and \a j are at least 0 and less than size().
826 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 12
831 /*! \fn int QList::indexOf(const T &value, int from = 0) const
833 Returns the index position of the first occurrence of \a value in
834 the list, searching forward from index position \a from. Returns
835 -1 if no item matched.
838 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 13
840 This function requires the value type to have an implementation of
843 Note that QList uses 0-based indexes, just like C++ arrays. Negative
844 indexes are not supported with the exception of the value mentioned
847 \sa lastIndexOf(), contains()
850 /*! \fn int QList::lastIndexOf(const T &value, int from = -1) const
852 Returns the index position of the last occurrence of \a value in
853 the list, searching backward from index position \a from. If \a
854 from is -1 (the default), the search starts at the last item.
855 Returns -1 if no item matched.
858 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 14
860 This function requires the value type to have an implementation of
863 Note that QList uses 0-based indexes, just like C++ arrays. Negative
864 indexes are not supported with the exception of the value mentioned
870 /*! \fn bool QList::contains(const T &value) const
872 Returns true if the list contains an occurrence of \a value;
873 otherwise returns false.
875 This function requires the value type to have an implementation of
878 \sa indexOf(), count()
881 /*! \fn int QList::count(const T &value) const
883 Returns the number of occurrences of \a value in the list.
885 This function requires the value type to have an implementation of
888 \sa contains(), indexOf()
891 /*! \fn bool QList::startsWith(const T &value) const
894 Returns true if this list is not empty and its first
895 item is equal to \a value; otherwise returns false.
897 \sa isEmpty(), contains()
900 /*! \fn bool QList::endsWith(const T &value) const
903 Returns true if this list is not empty and its last
904 item is equal to \a value; otherwise returns false.
906 \sa isEmpty(), contains()
909 /*! \fn QList::iterator QList::begin()
911 Returns an \l{STL-style iterator} pointing to the first item in
914 \sa constBegin(), end()
917 /*! \fn QList::const_iterator QList::begin() const
922 /*! \fn QList::const_iterator QList::cbegin() const
925 Returns a const \l{STL-style iterator} pointing to the first item
931 /*! \fn QList::const_iterator QList::constBegin() const
933 Returns a const \l{STL-style iterator} pointing to the first item
936 \sa begin(), constEnd()
939 /*! \fn QList::iterator QList::end()
941 Returns an \l{STL-style iterator} pointing to the imaginary item
942 after the last item in the list.
944 \sa begin(), constEnd()
947 /*! \fn const_iterator QList::end() const
952 /*! \fn QList::const_iterator QList::cend() const
955 Returns a const \l{STL-style iterator} pointing to the imaginary
956 item after the last item in the list.
961 /*! \fn QList::const_iterator QList::constEnd() const
963 Returns a const \l{STL-style iterator} pointing to the imaginary
964 item after the last item in the list.
966 \sa constBegin(), end()
969 /*! \fn QList::iterator QList::erase(iterator pos)
971 Removes the item associated with the iterator \a pos from the
972 list, and returns an iterator to the next item in the list (which
975 \sa insert(), removeAt()
978 /*! \fn QList::iterator QList::erase(iterator begin, iterator end)
982 Removes all the items from \a begin up to (but not including) \a
983 end. Returns an iterator to the same item that \a end referred to
987 /*! \typedef QList::Iterator
989 Qt-style synonym for QList::iterator.
992 /*! \typedef QList::ConstIterator
994 Qt-style synonym for QList::const_iterator.
998 \typedef QList::size_type
1000 Typedef for int. Provided for STL compatibility.
1004 \typedef QList::value_type
1006 Typedef for T. Provided for STL compatibility.
1010 \typedef QList::difference_type
1012 Typedef for ptrdiff_t. Provided for STL compatibility.
1016 \typedef QList::pointer
1018 Typedef for T *. Provided for STL compatibility.
1022 \typedef QList::const_pointer
1024 Typedef for const T *. Provided for STL compatibility.
1028 \typedef QList::reference
1030 Typedef for T &. Provided for STL compatibility.
1034 \typedef QList::const_reference
1036 Typedef for const T &. Provided for STL compatibility.
1039 /*! \fn int QList::count() const
1041 Returns the number of items in the list. This is effectively the
1045 /*! \fn int QList::length() const
1048 This function is identical to count().
1053 /*! \fn T& QList::first()
1055 Returns a reference to the first item in the list. The list must
1056 not be empty. If the list can be empty, call isEmpty() before
1057 calling this function.
1059 \sa last(), isEmpty()
1062 /*! \fn const T& QList::first() const
1067 /*! \fn T& QList::last()
1069 Returns a reference to the last item in the list. The list must
1070 not be empty. If the list can be empty, call isEmpty() before
1071 calling this function.
1073 \sa first(), isEmpty()
1076 /*! \fn const T& QList::last() const
1081 /*! \fn void QList::removeFirst()
1083 Removes the first item in the list. Calling this function is
1084 equivalent to calling removeAt(0). The list must not be empty. If
1085 the list can be empty, call isEmpty() before calling this
1088 \sa removeAt(), takeFirst()
1091 /*! \fn void QList::removeLast()
1093 Removes the last item in the list. Calling this function is
1094 equivalent to calling removeAt(size() - 1). The list must not be
1095 empty. If the list can be empty, call isEmpty() before calling
1098 \sa removeAt(), takeLast()
1101 /*! \fn T QList::value(int i) const
1103 Returns the value at index position \a i in the list.
1105 If the index \a i is out of bounds, the function returns a
1106 \l{default-constructed value}. If you are certain that the index
1107 is going to be within bounds, you can use at() instead, which is
1110 \sa at(), operator[]()
1113 /*! \fn T QList::value(int i, const T &defaultValue) const
1117 If the index \a i is out of bounds, the function returns
1121 /*! \fn void QList::push_back(const T &value)
1123 This function is provided for STL compatibility. It is equivalent
1124 to \l{QList::append()}{append(\a value)}.
1127 /*! \fn void QList::push_front(const T &value)
1129 This function is provided for STL compatibility. It is equivalent
1130 to \l{QList::prepend()}{prepend(\a value)}.
1133 /*! \fn T& QList::front()
1135 This function is provided for STL compatibility. It is equivalent
1136 to first(). The list must not be empty. If the list can be empty,
1137 call isEmpty() before calling this function.
1140 /*! \fn const T& QList::front() const
1145 /*! \fn T& QList::back()
1147 This function is provided for STL compatibility. It is equivalent
1148 to last(). The list must not be empty. If the list can be empty,
1149 call isEmpty() before calling this function.
1152 /*! \fn const T& QList::back() const
1157 /*! \fn void QList::pop_front()
1159 This function is provided for STL compatibility. It is equivalent
1160 to removeFirst(). The list must not be empty. If the list can be
1161 empty, call isEmpty() before calling this function.
1164 /*! \fn void QList::pop_back()
1166 This function is provided for STL compatibility. It is equivalent
1167 to removeLast(). The list must not be empty. If the list can be
1168 empty, call isEmpty() before calling this function.
1171 /*! \fn bool QList::empty() const
1173 This function is provided for STL compatibility. It is equivalent
1174 to isEmpty() and returns true if the list is empty.
1177 /*! \fn QList<T> &QList::operator+=(const QList<T> &other)
1179 Appends the items of the \a other list to this list and returns a
1180 reference to this list.
1182 \sa operator+(), append()
1185 /*! \fn void QList::operator+=(const T &value)
1189 Appends \a value to the list.
1191 \sa append(), operator<<()
1194 /*! \fn QList<T> QList::operator+(const QList<T> &other) const
1196 Returns a list that contains all the items in this list followed
1197 by all the items in the \a other list.
1202 /*! \fn QList<T> &QList::operator<<(const QList<T> &other)
1204 Appends the items of the \a other list to this list and returns a
1205 reference to this list.
1207 \sa operator+=(), append()
1210 /*! \fn void QList::operator<<(const T &value)
1214 Appends \a value to the list.
1217 /*! \class QList::iterator
1218 \brief The QList::iterator class provides an STL-style non-const iterator for QList and QQueue.
1220 QList features both \l{STL-style iterators} and \l{Java-style
1221 iterators}. The STL-style iterators are more low-level and more
1222 cumbersome to use; on the other hand, they are slightly faster
1223 and, for developers who already know STL, have the advantage of
1226 QList\<T\>::iterator allows you to iterate over a QList\<T\> (or
1227 QQueue\<T\>) and to modify the list item associated with the
1228 iterator. If you want to iterate over a const QList, use
1229 QList::const_iterator instead. It is generally good practice to
1230 use QList::const_iterator on a non-const QList as well, unless
1231 you need to change the QList through the iterator. Const
1232 iterators are slightly faster, and can improve code readability.
1234 The default QList::iterator constructor creates an uninitialized
1235 iterator. You must initialize it using a QList function like
1236 QList::begin(), QList::end(), or QList::insert() before you can
1237 start iterating. Here's a typical loop that prints all the items
1240 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 15
1242 Let's see a few examples of things we can do with a
1243 QList::iterator that we cannot do with a QList::const_iterator.
1244 Here's an example that increments every value stored in a
1247 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 16
1249 Most QList functions accept an integer index rather than an
1250 iterator. For that reason, iterators are rarely useful in
1251 connection with QList. One place where STL-style iterators do
1252 make sense is as arguments to \l{generic algorithms}.
1254 For example, here's how to delete all the widgets stored in a
1257 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 17
1259 Multiple iterators can be used on the same list. However, be
1260 aware that any non-const function call performed on the QList
1261 will render all existing iterators undefined. If you need to keep
1262 iterators over a long period of time, we recommend that you use
1263 QLinkedList rather than QList.
1265 \sa QList::const_iterator, QMutableListIterator
1268 /*! \typedef QList::iterator::iterator_category
1270 A synonym for \e {std::random_access_iterator_tag} indicating
1271 this iterator is a random access iterator.
1274 /*! \typedef QList::iterator::difference_type
1279 /*! \typedef QList::iterator::value_type
1284 /*! \typedef QList::iterator::pointer
1289 /*! \typedef QList::iterator::reference
1294 /*! \fn QList::iterator::iterator()
1296 Constructs an uninitialized iterator.
1298 Functions like operator*() and operator++() should not be called
1299 on an uninitialized iterator. Use operator=() to assign a value
1300 to it before using it.
1302 \sa QList::begin() QList::end()
1305 /*! \fn QList::iterator::iterator(Node *node)
1310 /*! \fn QList::iterator::iterator(const iterator &other)
1312 Constructs a copy of \a other.
1315 /*! \fn T &QList::iterator::operator*() const
1317 Returns a modifiable reference to the current item.
1319 You can change the value of an item by using operator*() on the
1320 left side of an assignment, for example:
1322 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 18
1327 /*! \fn T *QList::iterator::operator->() const
1329 Returns a pointer to the current item.
1334 /*! \fn T &QList::iterator::operator[](int j) const
1336 Returns a modifiable reference to the item at position *this +
1339 This function is provided to make QList iterators behave like C++
1346 \fn bool QList::iterator::operator==(const iterator &other) const
1347 \fn bool QList::iterator::operator==(const const_iterator &other) const
1349 Returns true if \a other points to the same item as this
1350 iterator; otherwise returns false.
1356 \fn bool QList::iterator::operator!=(const iterator &other) const
1357 \fn bool QList::iterator::operator!=(const const_iterator &other) const
1359 Returns true if \a other points to a different item than this
1360 iterator; otherwise returns false.
1366 \fn bool QList::iterator::operator<(const iterator& other) const
1367 \fn bool QList::iterator::operator<(const const_iterator& other) const
1369 Returns true if the item pointed to by this iterator is less than
1370 the item pointed to by the \a other iterator.
1374 \fn bool QList::iterator::operator<=(const iterator& other) const
1375 \fn bool QList::iterator::operator<=(const const_iterator& other) const
1377 Returns true if the item pointed to by this iterator is less than
1378 or equal to the item pointed to by the \a other iterator.
1382 \fn bool QList::iterator::operator>(const iterator& other) const
1383 \fn bool QList::iterator::operator>(const const_iterator& other) const
1385 Returns true if the item pointed to by this iterator is greater
1386 than the item pointed to by the \a other iterator.
1390 \fn bool QList::iterator::operator>=(const iterator& other) const
1391 \fn bool QList::iterator::operator>=(const const_iterator& other) const
1393 Returns true if the item pointed to by this iterator is greater
1394 than or equal to the item pointed to by the \a other iterator.
1397 /*! \fn QList::iterator &QList::iterator::operator++()
1399 The prefix ++ operator (\c{++it}) advances the iterator to the
1400 next item in the list and returns an iterator to the new current
1403 Calling this function on QList::end() leads to undefined results.
1408 /*! \fn QList::iterator QList::iterator::operator++(int)
1412 The postfix ++ operator (\c{it++}) advances the iterator to the
1413 next item in the list and returns an iterator to the previously
1417 /*! \fn QList::iterator &QList::iterator::operator--()
1419 The prefix -- operator (\c{--it}) makes the preceding item
1420 current and returns an iterator to the new current item.
1422 Calling this function on QList::begin() leads to undefined results.
1427 /*! \fn QList::iterator QList::iterator::operator--(int)
1431 The postfix -- operator (\c{it--}) makes the preceding item
1432 current and returns an iterator to the previously current item.
1435 /*! \fn QList::iterator &QList::iterator::operator+=(int j)
1437 Advances the iterator by \a j items. (If \a j is negative, the
1438 iterator goes backward.)
1440 \sa operator-=(), operator+()
1443 /*! \fn QList::iterator &QList::iterator::operator-=(int j)
1445 Makes the iterator go back by \a j items. (If \a j is negative,
1446 the iterator goes forward.)
1448 \sa operator+=(), operator-()
1451 /*! \fn QList::iterator QList::iterator::operator+(int j) const
1453 Returns an iterator to the item at \a j positions forward from
1454 this iterator. (If \a j is negative, the iterator goes backward.)
1456 \sa operator-(), operator+=()
1459 /*! \fn QList::iterator QList::iterator::operator-(int j) const
1461 Returns an iterator to the item at \a j positions backward from
1462 this iterator. (If \a j is negative, the iterator goes forward.)
1464 \sa operator+(), operator-=()
1467 /*! \fn int QList::iterator::operator-(iterator other) const
1469 Returns the number of items between the item pointed to by \a
1470 other and the item pointed to by this iterator.
1473 /*! \class QList::const_iterator
1474 \brief The QList::const_iterator class provides an STL-style const iterator for QList and QQueue.
1476 QList provides both \l{STL-style iterators} and \l{Java-style
1477 iterators}. The STL-style iterators are more low-level and more
1478 cumbersome to use; on the other hand, they are slightly faster
1479 and, for developers who already know STL, have the advantage of
1482 QList\<T\>::const_iterator allows you to iterate over a
1483 QList\<T\> (or a QQueue\<T\>). If you want to modify the QList as
1484 you iterate over it, use QList::iterator instead. It is generally
1485 good practice to use QList::const_iterator on a non-const QList
1486 as well, unless you need to change the QList through the
1487 iterator. Const iterators are slightly faster, and can improve
1490 The default QList::const_iterator constructor creates an
1491 uninitialized iterator. You must initialize it using a QList
1492 function like QList::constBegin(), QList::constEnd(), or
1493 QList::insert() before you can start iterating. Here's a typical
1494 loop that prints all the items stored in a list:
1496 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 19
1498 Most QList functions accept an integer index rather than an
1499 iterator. For that reason, iterators are rarely useful in
1500 connection with QList. One place where STL-style iterators do
1501 make sense is as arguments to \l{generic algorithms}.
1503 For example, here's how to delete all the widgets stored in a
1506 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 20
1508 Multiple iterators can be used on the same list. However, be
1509 aware that any non-const function call performed on the QList
1510 will render all existing iterators undefined. If you need to keep
1511 iterators over a long period of time, we recommend that you use
1512 QLinkedList rather than QList.
1514 \sa QList::iterator, QListIterator
1517 /*! \fn QList::const_iterator::const_iterator()
1519 Constructs an uninitialized iterator.
1521 Functions like operator*() and operator++() should not be called
1522 on an uninitialized iterator. Use operator=() to assign a value
1523 to it before using it.
1525 \sa QList::constBegin() QList::constEnd()
1528 /*! \typedef QList::const_iterator::iterator_category
1530 A synonym for \e {std::random_access_iterator_tag} indicating
1531 this iterator is a random access iterator.
1534 /*! \typedef QList::const_iterator::difference_type
1539 /*! \typedef QList::const_iterator::value_type
1544 /*! \typedef QList::const_iterator::pointer
1549 /*! \typedef QList::const_iterator::reference
1554 /*! \fn QList::const_iterator::const_iterator(Node *node)
1559 /*! \fn QList::const_iterator::const_iterator(const const_iterator &other)
1561 Constructs a copy of \a other.
1564 /*! \fn QList::const_iterator::const_iterator(const iterator &other)
1566 Constructs a copy of \a other.
1569 /*! \fn const T &QList::const_iterator::operator*() const
1571 Returns the current item.
1576 /*! \fn const T *QList::const_iterator::operator->() const
1578 Returns a pointer to the current item.
1583 /*! \fn const T &QList::const_iterator::operator[](int j) const
1585 Returns the item at position *this + \a{j}.
1587 This function is provided to make QList iterators behave like C++
1593 /*! \fn bool QList::const_iterator::operator==(const const_iterator &other) const
1595 Returns true if \a other points to the same item as this
1596 iterator; otherwise returns false.
1601 /*! \fn bool QList::const_iterator::operator!=(const const_iterator &other) const
1603 Returns true if \a other points to a different item than this
1604 iterator; otherwise returns false.
1610 \fn bool QList::const_iterator::operator<(const const_iterator& other) const
1612 Returns true if the item pointed to by this iterator is less than
1613 the item pointed to by the \a other iterator.
1617 \fn bool QList::const_iterator::operator<=(const const_iterator& other) const
1619 Returns true if the item pointed to by this iterator is less than
1620 or equal to the item pointed to by the \a other iterator.
1624 \fn bool QList::const_iterator::operator>(const const_iterator& other) const
1626 Returns true if the item pointed to by this iterator is greater
1627 than the item pointed to by the \a other iterator.
1631 \fn bool QList::const_iterator::operator>=(const const_iterator& other) const
1633 Returns true if the item pointed to by this iterator is greater
1634 than or equal to the item pointed to by the \a other iterator.
1637 /*! \fn QList::const_iterator &QList::const_iterator::operator++()
1639 The prefix ++ operator (\c{++it}) advances the iterator to the
1640 next item in the list and returns an iterator to the new current
1643 Calling this function on QList::end() leads to undefined results.
1648 /*! \fn QList::const_iterator QList::const_iterator::operator++(int)
1652 The postfix ++ operator (\c{it++}) advances the iterator to the
1653 next item in the list and returns an iterator to the previously
1657 /*! \fn QList::const_iterator &QList::const_iterator::operator--()
1659 The prefix -- operator (\c{--it}) makes the preceding item
1660 current and returns an iterator to the new current item.
1662 Calling this function on QList::begin() leads to undefined results.
1667 /*! \fn QList::const_iterator QList::const_iterator::operator--(int)
1671 The postfix -- operator (\c{it--}) makes the preceding item
1672 current and returns an iterator to the previously current item.
1675 /*! \fn QList::const_iterator &QList::const_iterator::operator+=(int j)
1677 Advances the iterator by \a j items. (If \a j is negative, the
1678 iterator goes backward.)
1680 \sa operator-=(), operator+()
1683 /*! \fn QList::const_iterator &QList::const_iterator::operator-=(int j)
1685 Makes the iterator go back by \a j items. (If \a j is negative,
1686 the iterator goes forward.)
1688 \sa operator+=(), operator-()
1691 /*! \fn QList::const_iterator QList::const_iterator::operator+(int j) const
1693 Returns an iterator to the item at \a j positions forward from
1694 this iterator. (If \a j is negative, the iterator goes backward.)
1696 \sa operator-(), operator+=()
1699 /*! \fn QList::const_iterator QList::const_iterator::operator-(int j) const
1701 Returns an iterator to the item at \a j positions backward from
1702 this iterator. (If \a j is negative, the iterator goes forward.)
1704 \sa operator+(), operator-=()
1707 /*! \fn int QList::const_iterator::operator-(const_iterator other) const
1709 Returns the number of items between the item pointed to by \a
1710 other and the item pointed to by this iterator.
1713 /*! \fn QDataStream &operator<<(QDataStream &out, const QList<T> &list)
1716 Writes the list \a list to stream \a out.
1718 This function requires the value type to implement \c
1721 \sa \link datastreamformat.html Format of the QDataStream operators \endlink
1724 /*! \fn QDataStream &operator>>(QDataStream &in, QList<T> &list)
1727 Reads a list from stream \a in into \a list.
1729 This function requires the value type to implement \c
1732 \sa \link datastreamformat.html Format of the QDataStream operators \endlink
1735 /*! \fn QList<T> QList<T>::fromVector(const QVector<T> &vector)
1737 Returns a QList object with the data contained in \a vector.
1741 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 21
1743 \sa fromSet(), toVector(), QVector::toList()
1746 /*! \fn QVector<T> QList<T>::toVector() const
1748 Returns a QVector object with the data contained in this QList.
1752 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 22
1754 \sa toSet(), fromVector(), QVector::fromList()
1757 /*! \fn QList<T> QList<T>::fromSet(const QSet<T> &set)
1759 Returns a QList object with the data contained in \a set. The
1760 order of the elements in the QList is undefined.
1764 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 23
1766 \sa fromVector(), toSet(), QSet::toList(), qSort()
1769 /*! \fn QSet<T> QList<T>::toSet() const
1771 Returns a QSet object with the data contained in this QList.
1772 Since QSet doesn't allow duplicates, the resulting QSet might be
1773 smaller than the original list was.
1777 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 24
1779 \sa toVector(), fromSet(), QSet::fromList()
1782 /*! \fn QList<T> QList<T>::fromStdList(const std::list<T> &list)
1784 Returns a QList object with the data contained in \a list. The
1785 order of the elements in the QList is the same as in \a list.
1789 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 25
1791 \sa toStdList(), QVector::fromStdVector()
1794 /*! \fn std::list<T> QList<T>::toStdList() const
1796 Returns a std::list object with the data contained in this QList.
1799 \snippet doc/src/snippets/code/src_corelib_tools_qlistdata.cpp 26
1801 \sa fromStdList(), QVector::toStdVector()