1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Copyright (C) 2016 Intel Corporation.
5** Contact: https://www.qt.io/licensing/
6**
7** This file is part of the QtCore module of the Qt Toolkit.
8**
9** $QT_BEGIN_LICENSE:LGPL$
10** Commercial License Usage
11** Licensees holding valid commercial Qt licenses may use this file in
12** accordance with the commercial license agreement provided with the
13** Software or, alternatively, in accordance with the terms contained in
14** a written agreement between you and The Qt Company. For licensing terms
15** and conditions see https://www.qt.io/terms-conditions. For further
16** information use the contact form at https://www.qt.io/contact-us.
17**
18** GNU Lesser General Public License Usage
19** Alternatively, this file may be used under the terms of the GNU Lesser
20** General Public License version 3 as published by the Free Software
21** Foundation and appearing in the file LICENSE.LGPL3 included in the
22** packaging of this file. Please review the following information to
23** ensure the GNU Lesser General Public License version 3 requirements
24** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
25**
26** GNU General Public License Usage
27** Alternatively, this file may be used under the terms of the GNU
28** General Public License version 2.0 or (at your option) the GNU General
29** Public license version 3 or any later version approved by the KDE Free
30** Qt Foundation. The licenses are as published by the Free Software
31** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
32** included in the packaging of this file. Please review the following
33** information to ensure the GNU General Public License requirements will
34** be met: https://www.gnu.org/licenses/gpl-2.0.html and
35** https://www.gnu.org/licenses/gpl-3.0.html.
36**
37** $QT_END_LICENSE$
38**
39****************************************************************************/
40
41#include <new>
42#include "qlist.h"
43#include "qtools_p.h"
44
45#include <string.h>
46#include <stdlib.h>
47
48QT_BEGIN_NAMESPACE
49
50/*
51 ### Qt 5:
52 ### This needs to be removed for next releases of Qt. It is a workaround for vc++ because
53 ### Qt exports QPolygon and QPolygonF that inherit QVector<QPoint> and
54 ### QVector<QPointF> respectively.
55*/
56
57#if defined(Q_CC_MSVC) && defined(QT_BUILD_CORE_LIB)
58QT_BEGIN_INCLUDE_NAMESPACE
59#include <QtCore/qpoint.h>
60QT_END_INCLUDE_NAMESPACE
61
62template class Q_CORE_EXPORT QVector<QPointF>;
63template class Q_CORE_EXPORT QVector<QPoint>;
64#endif
65
66
67/*
68 QList as an array-list combines the easy-of-use of a random
69 access interface with fast list operations and the low memory
70 management overhead of an array. Accessing elements by index,
71 appending, prepending, and removing elements from both the front
72 and the back all happen in constant time O(1). Inserting or
73 removing elements at random index positions \ai happens in linear
74 time, or more precisly in O(min{i,n-i}) <= O(n/2), with n being
75 the number of elements in the list.
76*/
77
78const QListData::Data QListData::shared_null = { Q_REFCOUNT_INITIALIZE_STATIC, 0, 0, 0, { nullptr } };
79
80/*!
81 * Detaches the QListData by allocating new memory for a list which will be bigger
82 * than the copied one and is expected to grow further.
83 * *idx is the desired insertion point and is clamped to the actual size of the list.
84 * num is the number of new elements to insert at the insertion point.
85 * Returns the old (shared) data, it is up to the caller to deref() and free().
86 * For the new data node_copy needs to be called.
87 *
88 * \internal
89 */
90QListData::Data *QListData::detach_grow(int *idx, int num)
91{
92 Data *x = d;
93 int l = x->end - x->begin;
94 int nl = l + num;
95 auto blockInfo = qCalculateGrowingBlockSize(nl, sizeof(void *), DataHeaderSize);
96 Data* t = static_cast<Data *>(::malloc(blockInfo.size));
97 Q_CHECK_PTR(t);
98 t->alloc = int(uint(blockInfo.elementCount));
99
100 t->ref.initializeOwned();
101 // The space reservation algorithm's optimization is biased towards appending:
102 // Something which looks like an append will put the data at the beginning,
103 // while something which looks like a prepend will put it in the middle
104 // instead of at the end. That's based on the assumption that prepending
105 // is uncommon and even an initial prepend will eventually be followed by
106 // at least some appends.
107 int bg;
108 if (*idx < 0) {
109 *idx = 0;
110 bg = (t->alloc - nl) >> 1;
111 } else if (*idx > l) {
112 *idx = l;
113 bg = 0;
114 } else if (*idx < (l >> 1)) {
115 bg = (t->alloc - nl) >> 1;
116 } else {
117 bg = 0;
118 }
119 t->begin = bg;
120 t->end = bg + nl;
121 d = t;
122
123 return x;
124}
125
126/*!
127 * Detaches the QListData by allocating new memory for a list which possibly
128 * has a different size than the copied one.
129 * Returns the old (shared) data, it is up to the caller to deref() and free()
130 * For the new data node_copy needs to be called.
131 *
132 * \internal
133 */
134QListData::Data *QListData::detach(int alloc)
135{
136 Data *x = d;
137 Data* t = static_cast<Data *>(::malloc(qCalculateBlockSize(alloc, sizeof(void*), DataHeaderSize)));
138 Q_CHECK_PTR(t);
139
140 t->ref.initializeOwned();
141 t->alloc = alloc;
142 if (!alloc) {
143 t->begin = 0;
144 t->end = 0;
145 } else {
146 t->begin = x->begin;
147 t->end = x->end;
148 }
149 d = t;
150
151 return x;
152}
153
154void QListData::realloc(int alloc)
155{
156 Q_ASSERT(!d->ref.isShared());
157 Data *x = static_cast<Data *>(::realloc(d, qCalculateBlockSize(alloc, sizeof(void *), DataHeaderSize)));
158 Q_CHECK_PTR(x);
159
160 d = x;
161 d->alloc = alloc;
162 if (!alloc)
163 d->begin = d->end = 0;
164}
165
166void QListData::realloc_grow(int growth)
167{
168 Q_ASSERT(!d->ref.isShared());
169 auto r = qCalculateGrowingBlockSize(d->alloc + growth, sizeof(void *), DataHeaderSize);
170 Data *x = static_cast<Data *>(::realloc(d, r.size));
171 Q_CHECK_PTR(x);
172
173 d = x;
174 d->alloc = int(uint(r.elementCount));
175}
176
177void QListData::dispose(Data *d)
178{
179 Q_ASSERT(!d->ref.isShared());
180 free(d);
181}
182
183// ensures that enough space is available to append n elements
184void **QListData::append(int n)
185{
186 Q_ASSERT(!d->ref.isShared());
187 int e = d->end;
188 if (e + n > d->alloc) {
189 int b = d->begin;
190 if (b - n >= 2 * d->alloc / 3) {
191 // we have enough space. Just not at the end -> move it.
192 e -= b;
193 ::memcpy(d->array, d->array + b, e * sizeof(void *));
194 d->begin = 0;
195 } else {
196 realloc_grow(n);
197 }
198 }
199 d->end = e + n;
200 return d->array + e;
201}
202
203// ensures that enough space is available to append one element
204void **QListData::append()
205{
206 return append(1);
207}
208
209// ensures that enough space is available to append the list
210void **QListData::append(const QListData& l)
211{
212 return append(l.d->end - l.d->begin);
213}
214
215void **QListData::prepend()
216{
217 Q_ASSERT(!d->ref.isShared());
218 if (d->begin == 0) {
219 if (d->end >= d->alloc / 3)
220 realloc_grow(1);
221
222 if (d->end < d->alloc / 3)
223 d->begin = d->alloc - 2 * d->end;
224 else
225 d->begin = d->alloc - d->end;
226
227 ::memmove(d->array + d->begin, d->array, d->end * sizeof(void *));
228 d->end += d->begin;
229 }
230 return d->array + --d->begin;
231}
232
233void **QListData::insert(int i)
234{
235 Q_ASSERT(!d->ref.isShared());
236 if (i <= 0)
237 return prepend();
238 int size = d->end - d->begin;
239 if (i >= size)
240 return append();
241
242 bool leftward = false;
243
244 if (d->begin == 0) {
245 if (d->end == d->alloc) {
246 // If the array is full, we expand it and move some items rightward
247 realloc_grow(1);
248 } else {
249 // If there is free space at the end of the array, we move some items rightward
250 }
251 } else {
252 if (d->end == d->alloc) {
253 // If there is free space at the beginning of the array, we move some items leftward
254 leftward = true;
255 } else {
256 // If there is free space at both ends, we move as few items as possible
257 leftward = (i < size - i);
258 }
259 }
260
261 if (leftward) {
262 --d->begin;
263 ::memmove(d->array + d->begin, d->array + d->begin + 1, i * sizeof(void *));
264 } else {
265 ::memmove(d->array + d->begin + i + 1, d->array + d->begin + i,
266 (size - i) * sizeof(void *));
267 ++d->end;
268 }
269 return d->array + d->begin + i;
270}
271
272void QListData::remove(int i)
273{
274 Q_ASSERT(!d->ref.isShared());
275 i += d->begin;
276 if (i - d->begin < d->end - i) {
277 if (int offset = i - d->begin)
278 ::memmove(d->array + d->begin + 1, d->array + d->begin, offset * sizeof(void *));
279 d->begin++;
280 } else {
281 if (int offset = d->end - i - 1)
282 ::memmove(d->array + i, d->array + i + 1, offset * sizeof(void *));
283 d->end--;
284 }
285}
286
287void QListData::remove(int i, int n)
288{
289 Q_ASSERT(!d->ref.isShared());
290 i += d->begin;
291 int middle = i + n/2;
292 if (middle - d->begin < d->end - middle) {
293 ::memmove(d->array + d->begin + n, d->array + d->begin,
294 (i - d->begin) * sizeof(void*));
295 d->begin += n;
296 } else {
297 ::memmove(d->array + i, d->array + i + n,
298 (d->end - i - n) * sizeof(void*));
299 d->end -= n;
300 }
301}
302
303void QListData::move(int from, int to)
304{
305 Q_ASSERT(!d->ref.isShared());
306 if (from == to)
307 return;
308
309 from += d->begin;
310 to += d->begin;
311 void *t = d->array[from];
312
313 if (from < to) {
314 if (d->end == d->alloc || 3 * (to - from) < 2 * (d->end - d->begin)) {
315 ::memmove(d->array + from, d->array + from + 1, (to - from) * sizeof(void *));
316 } else {
317 // optimization
318 if (int offset = from - d->begin)
319 ::memmove(d->array + d->begin + 1, d->array + d->begin, offset * sizeof(void *));
320 if (int offset = d->end - (to + 1))
321 ::memmove(d->array + to + 2, d->array + to + 1, offset * sizeof(void *));
322 ++d->begin;
323 ++d->end;
324 ++to;
325 }
326 } else {
327 if (d->begin == 0 || 3 * (from - to) < 2 * (d->end - d->begin)) {
328 ::memmove(d->array + to + 1, d->array + to, (from - to) * sizeof(void *));
329 } else {
330 // optimization
331 if (int offset = to - d->begin)
332 ::memmove(d->array + d->begin - 1, d->array + d->begin, offset * sizeof(void *));
333 if (int offset = d->end - (from + 1))
334 ::memmove(d->array + from, d->array + from + 1, offset * sizeof(void *));
335 --d->begin;
336 --d->end;
337 --to;
338 }
339 }
340 d->array[to] = t;
341}
342
343void **QListData::erase(void **xi)
344{
345 Q_ASSERT(!d->ref.isShared());
346 int i = xi - (d->array + d->begin);
347 remove(i);
348 return d->array + d->begin + i;
349}
350
351/*! \class QList
352 \inmodule QtCore
353 \brief The QList class is a template class that provides lists.
354
355 \ingroup tools
356 \ingroup shared
357
358 \reentrant
359
360 QList\<T\> is one of Qt's generic \l{container classes}. It
361 stores items in a list that provides fast index-based access
362 and index-based insertions and removals.
363
364 QList\<T\>, QLinkedList\<T\>, and QVector\<T\> provide similar
365 APIs and functionality. They are often interchangeable, but there
366 are performance consequences. Here is an overview of use cases:
367
368 \list
369 \li QVector should be your default first choice.
370 QVector\<T\> will usually give better performance than QList\<T\>,
371 because QVector\<T\> always stores its items sequentially in memory,
372 where QList\<T\> will allocate its items on the heap unless
373 \c {sizeof(T) <= sizeof(void*)} and T has been declared to be
374 either a \c{Q_MOVABLE_TYPE} or a \c{Q_PRIMITIVE_TYPE} using
375 \l {Q_DECLARE_TYPEINFO}. See the \l {Pros and Cons of Using QList}
376 for an explanation.
377 \li However, QList is used throughout the Qt APIs for passing
378 parameters and for returning values. Use QList to interface with
379 those APIs.
380 \li If you need a real linked list, which guarantees
381 \l {Algorithmic Complexity}{constant time} insertions mid-list and
382 uses iterators to items rather than indexes, use QLinkedList.
383 \endlist
384
385 \note QVector and QVarLengthArray both guarantee C-compatible
386 array layout. QList does not. This might be important if your
387 application must interface with a C API.
388
389 \note Iterators into a QLinkedList and references into
390 heap-allocating QLists remain valid as long as the referenced items
391 remain in the container. This is not true for iterators and
392 references into a QVector and non-heap-allocating QLists.
393
394 Internally, QList\<T\> is represented as an array of T if
395 \c{sizeof(T) <= sizeof(void*)} and T has been declared to be
396 either a \c{Q_MOVABLE_TYPE} or a \c{Q_PRIMITIVE_TYPE} using
397 \l {Q_DECLARE_TYPEINFO}. Otherwise, QList\<T\> is represented
398 as an array of T* and the items are allocated on the heap.
399
400 The array representation allows very fast insertions and
401 index-based access. The prepend() and append() operations are
402 also very fast because QList preallocates memory at both
403 ends of its internal array. (See \l{Algorithmic Complexity} for
404 details.
405
406 Note, however, that when the conditions specified above are not met,
407 each append or insert of a new item requires allocating the new item
408 on the heap, and this per item allocation will make QVector a better
409 choice for use cases that do a lot of appending or inserting, because
410 QVector can allocate memory for many items in a single heap allocation.
411
412 Note that the internal array only ever gets bigger over the life
413 of the list. It never shrinks. The internal array is deallocated
414 by the destructor and by the assignment operator, when one list
415 is assigned to another.
416
417 Here's an example of a QList that stores integers and
418 a QList that stores QDate values:
419
420 \snippet code/src_corelib_tools_qlistdata.cpp 0
421
422 Qt includes a QStringList class that inherits QList\<QString\>
423 and adds a few convenience functions, such as QStringList::join()
424 and QStringList::filter(). QString::split() creates QStringLists
425 from strings.
426
427 QList stores a list of items. The default constructor creates an
428 empty list. You can use the initializer-list constructor to create
429 a list with elements:
430
431 \snippet code/src_corelib_tools_qlistdata.cpp 1a
432
433 QList provides these basic functions to add, move, and remove
434 items: insert(), replace(), removeAt(), move(), and swap(). In
435 addition, it provides the following convenience functions:
436 append(), \l{operator<<()}, \l{operator+=()}, prepend(), removeFirst(),
437 and removeLast().
438
439 \l{operator<<()} allows to conveniently add multiple elements to a list:
440
441 \snippet code/src_corelib_tools_qlistdata.cpp 1b
442
443 QList uses 0-based indexes, just like C++ arrays. To access the
444 item at a particular index position, you can use operator[](). On
445 non-const lists, operator[]() returns a reference to the item and
446 can be used on the left side of an assignment:
447
448 \snippet code/src_corelib_tools_qlistdata.cpp 2
449
450 Because QList is implemented as an array of pointers for types
451 that are larger than a pointer or are not movable, this operation
452 requires (\l{Algorithmic Complexity}{constant time}). For read-only
453 access, an alternative syntax is to use at():
454
455 \snippet code/src_corelib_tools_qlistdata.cpp 3
456
457 at() can be faster than operator[](), because it never causes a
458 \l{deep copy} to occur.
459
460 A common requirement is to remove an item from a list and do
461 something with it. For this, QList provides takeAt(), takeFirst(),
462 and takeLast(). Here's a loop that removes the items from a list
463 one at a time and calls \c delete on them:
464
465 \snippet code/src_corelib_tools_qlistdata.cpp 4
466
467 Inserting and removing items at either end of the list is very
468 fast (\l{Algorithmic Complexity}{constant time} in most cases),
469 because QList preallocates extra space on both sides of its
470 internal buffer to allow for fast growth at both ends of the list.
471
472 If you want to find all occurrences of a particular value in a
473 list, use indexOf() or lastIndexOf(). The former searches forward
474 starting from a given index position, the latter searches
475 backward. Both return the index of a matching item if they find
476 it; otherwise, they return -1. For example:
477
478 \snippet code/src_corelib_tools_qlistdata.cpp 5
479
480 If you simply want to check whether a list contains a particular
481 value, use contains(). If you want to find out how many times a
482 particular value occurs in the list, use count(). If you want to
483 replace all occurrences of a particular value with another, use
484 replace().
485
486 QList's value type must be an \l{assignable data type}. This
487 covers most data types that are commonly used, but the compiler
488 won't let you, for example, store a QWidget as a value; instead,
489 store a QWidget *. A few functions have additional requirements;
490 for example, indexOf() and lastIndexOf() expect the value type to
491 support \c operator==(). These requirements are documented on a
492 per-function basis.
493
494 Like the other container classes, QList provides \l{Java-style
495 iterators} (QListIterator and QMutableListIterator) and
496 \l{STL-style iterators} (QList::const_iterator and
497 QList::iterator). In practice, these are rarely used, because you
498 can use indexes into the QList. QList is implemented in such a way
499 that direct index-based access is just as fast as using iterators.
500
501 QList does \e not support inserting, prepending, appending or
502 replacing with references to its own values. Doing so will cause
503 your application to abort with an error message.
504
505 To make QList as efficient as possible, its member functions don't
506 validate their input before using it. Except for isEmpty(), member
507 functions always assume the list is \e not empty. Member functions
508 that take index values as parameters always assume their index
509 value parameters are in the valid range. This means QList member
510 functions can fail. If you define QT_NO_DEBUG when you compile,
511 failures will not be detected. If you \e don't define QT_NO_DEBUG,
512 failures will be detected using Q_ASSERT() or Q_ASSERT_X() with an
513 appropriate message.
514
515 To avoid failures when your list can be empty, call isEmpty()
516 before calling other member functions. If you must pass an index
517 value that might not be in the valid range, check that it is less
518 than the value returned by size() but \e not less than 0.
519
520 \section1 More Members
521
522 If T is a QByteArray, this class has a couple more members that can be
523 used. See the documentation for QByteArrayList for more information.
524
525 If T is QString, this class has the following additional members:
526 \l{QStringList::filter()}{filter},
527 \l{QStringList::join()}{join},
528 \l{QStringList::removeDuplicates()}{removeDuplicates},
529 \l{QStringList::sort()}{sort}.
530
531 \section1 More Information on Using Qt Containers
532
533 For a detailed discussion comparing Qt containers with each other and
534 with STL containers, see \l {Understand the Qt Containers}.
535
536 \sa QListIterator, QMutableListIterator, QLinkedList, QVector
537*/
538
539/*!
540 \fn template <class T> QList<T>::QList(QList<T> &&other)
541
542 Move-constructs a QList instance, making it point at the same
543 object that \a other was pointing to.
544
545 \since 5.2
546*/
547
548/*! \fn template <class T> template<typename InputIterator> QList<T>::QList(InputIterator first, InputIterator last)
549 \since 5.14
550
551 Constructs a QList with the contents in the iterator range [\a first, \a last).
552
553 The value type of \c InputIterator must be convertible to \c T.
554*/
555
556/*!
557 \fn template <class T> QList<T> QList<T>::mid(int pos, int length) const
558
559 Returns a sub-list which includes elements from this list,
560 starting at position \a pos. If \a length is -1 (the default), all
561 elements from \a pos are included; otherwise \a length elements (or
562 all remaining elements if there are less than \a length elements)
563 are included.
564*/
565
566/*! \fn template <class T> QList<T>::QList()
567
568 Constructs an empty list.
569*/
570
571/*! \fn template <class T> QList<T>::QList(const QList<T> &other)
572
573 Constructs a copy of \a other.
574
575 This operation takes \l{Algorithmic Complexity}{constant time},
576 because QList is \l{implicitly shared}. This makes returning a
577 QList from a function very fast. If a shared instance is modified,
578 it will be copied (copy-on-write), and that takes
579 \l{Algorithmic Complexity}{linear time}.
580
581 \sa operator=()
582*/
583
584/*! \fn template <class T> QList<T>::QList(std::initializer_list<T> args)
585 \since 4.8
586
587 Construct a list from the std::initializer_list specified by \a args.
588
589 This constructor is only enabled if the compiler supports C++11 initializer
590 lists.
591*/
592
593/*! \fn template <class T> QList<T>::~QList()
594
595 Destroys the list. References to the values in the list and all
596 iterators of this list become invalid.
597*/
598
599/*! \fn template <class T> QList<T> &QList<T>::operator=(const QList<T> &other)
600
601 Assigns \a other to this list and returns a reference to this
602 list.
603*/
604
605/*!
606 \fn template <class T> QList &QList<T>::operator=(QList<T> &&other)
607
608 Move-assigns \a other to this QList instance.
609
610 \since 5.2
611*/
612
613/*! \fn template <class T> void QList<T>::swap(QList<T> &other)
614 \since 4.8
615
616 Swaps list \a other with this list. This operation is very
617 fast and never fails.
618*/
619
620/*! \fn template <class T> bool QList<T>::operator==(const QList<T> &other) const
621
622 Returns \c true if \a other is equal to this list; otherwise returns
623 false.
624
625 Two lists are considered equal if they contain the same values in
626 the same order.
627
628 This function requires the value type to have an implementation of
629 \c operator==().
630
631 \sa operator!=()
632*/
633
634/*! \fn template <class T> bool QList<T>::operator!=(const QList<T> &other) const
635
636 Returns \c true if \a other is not equal to this list; otherwise
637 returns \c false.
638
639 Two lists are considered equal if they contain the same values in
640 the same order.
641
642 This function requires the value type to have an implementation of
643 \c operator==().
644
645 \sa operator==()
646*/
647
648/*! \fn template <class T> bool operator<(const QList<T> &lhs, const QList<T> &rhs)
649 \since 5.6
650 \relates QList
651
652 Returns \c true if list \a lhs is
653 \l{http://en.cppreference.com/w/cpp/algorithm/lexicographical_compare}
654 {lexicographically less than} \a rhs; otherwise returns \c false.
655
656 This function requires the value type to have an implementation
657 of \c operator<().
658*/
659
660/*! \fn template <class T> bool operator<=(const QList<T> &lhs, const QList<T> &rhs)
661 \since 5.6
662 \relates QList
663
664 Returns \c true if list \a lhs is
665 \l{http://en.cppreference.com/w/cpp/algorithm/lexicographical_compare}
666 {lexicographically less than or equal to} \a rhs; otherwise returns \c false.
667
668 This function requires the value type to have an implementation
669 of \c operator<().
670*/
671
672/*! \fn template <class T> bool operator>(const QList<T> &lhs, const QList<T> &rhs)
673 \since 5.6
674 \relates QList
675
676 Returns \c true if list \a lhs is
677 \l{http://en.cppreference.com/w/cpp/algorithm/lexicographical_compare}
678 {lexicographically greater than} \a rhs; otherwise returns \c false.
679
680 This function requires the value type to have an implementation
681 of \c operator<().
682*/
683
684/*! \fn template <class T> bool operator>=(const QList<T> &lhs, const QList<T> &rhs)
685 \since 5.6
686 \relates QList
687
688 Returns \c true if list \a lhs is
689 \l{http://en.cppreference.com/w/cpp/algorithm/lexicographical_compare}
690 {lexicographically greater than or equal to} \a rhs; otherwise returns \c false.
691
692 This function requires the value type to have an implementation
693 of \c operator<().
694*/
695
696/*!
697 \fn template <class T> uint qHash(const QList<T> &key, uint seed = 0)
698 \since 5.6
699 \relates QList
700
701 Returns the hash value for \a key,
702 using \a seed to seed the calculation.
703
704 This function requires qHash() to be overloaded for the value type \c T.
705*/
706
707/*!
708 \fn template <class T> int QList<T>::size() const
709
710 Returns the number of items in the list.
711
712 \sa isEmpty(), count()
713*/
714
715/*! \fn template <class T> void QList<T>::detach()
716
717 \internal
718*/
719
720/*! \fn template <class T> void QList<T>::detachShared()
721
722 \internal
723
724 like detach(), but does nothing if we're shared_null.
725 This prevents needless mallocs, and makes QList more exception safe
726 in case of cleanup work done in destructors on empty lists.
727*/
728
729/*! \fn template <class T> bool QList<T>::isDetached() const
730
731 \internal
732*/
733
734/*! \fn template <class T> void QList<T>::setSharable(bool sharable)
735
736 \internal
737*/
738
739/*! \fn template <class T> bool QList<T>::isSharedWith(const QList<T> &other) const
740
741 \internal
742*/
743
744/*! \fn template <class T> bool QList<T>::isEmpty() const
745
746 Returns \c true if the list contains no items; otherwise returns
747 false.
748
749 \sa size()
750*/
751
752/*! \fn template <class T> void QList<T>::clear()
753
754 Removes all items from the list.
755
756 \sa removeAll()
757*/
758
759/*! \fn template <class T> const T &QList<T>::at(int i) const
760
761 Returns the item at index position \a i in the list. \a i must be
762 a valid index position in the list (i.e., 0 <= \a i < size()).
763
764 This function is very fast (\l{Algorithmic Complexity}{constant time}).
765
766 \sa value(), operator[]()
767*/
768
769/*! \fn template <class T> T &QList<T>::operator[](int i)
770
771 Returns the item at index position \a i as a modifiable reference.
772 \a i must be a valid index position in the list (i.e., 0 <= \a i <
773 size()).
774
775 If this function is called on a list that is currently being shared, it
776 will trigger a copy of all elements. Otherwise, this function runs in
777 \l{Algorithmic Complexity}{constant time}. If you do not want to modify
778 the list you should use QList::at().
779
780 \sa at(), value()
781*/
782
783/*! \fn template <class T> const T &QList<T>::operator[](int i) const
784
785 \overload
786
787 Same as at(). This function runs in \l{Algorithmic Complexity}{constant time}.
788*/
789
790/*! \fn template <class T> void QList<T>::reserve(int alloc)
791
792 Reserve space for \a alloc elements.
793
794 If \a alloc is smaller than the current size of the list, nothing will happen.
795
796 Use this function to avoid repetetive reallocation of QList's internal
797 data if you can predict how many elements will be appended.
798 Note that the reservation applies only to the internal pointer array.
799
800 \since 4.7
801*/
802
803/*! \fn template <class T> void QList<T>::append(const T &value)
804
805 Inserts \a value at the end of the list.
806
807 Example:
808 \snippet code/src_corelib_tools_qlistdata.cpp 6
809
810 This is the same as list.insert(size(), \a value).
811
812 If this list is not shared, this operation is typically
813 very fast (amortized \l{Algorithmic Complexity}{constant time}),
814 because QList preallocates extra space on both sides of its
815 internal buffer to allow for fast growth at both ends of the list.
816
817 \sa operator<<(), prepend(), insert()
818*/
819
820/*! \fn template <class T> void QList<T>::append(const QList<T> &value)
821
822 \overload
823
824 \since 4.5
825
826 Appends the items of the \a value list to this list.
827
828 \sa operator<<(), operator+=()
829*/
830
831/*! \fn template <class T> void QList<T>::prepend(const T &value)
832
833 Inserts \a value at the beginning of the list.
834
835 Example:
836 \snippet code/src_corelib_tools_qlistdata.cpp 7
837
838 This is the same as list.insert(0, \a value).
839
840 If this list is not shared, this operation is typically
841 very fast (amortized \l{Algorithmic Complexity}{constant time}),
842 because QList preallocates extra space on both sides of its
843 internal buffer to allow for fast growth at both ends of the list.
844
845 \sa append(), insert()
846*/
847
848/*! \fn template <class T> void QList<T>::insert(int i, const T &value)
849
850 Inserts \a value at index position \a i in the list. If \a i <= 0,
851 the value is prepended to the list. If \a i >= size(), the
852 value is appended to the list.
853
854 Example:
855 \snippet code/src_corelib_tools_qlistdata.cpp 8
856
857 \sa append(), prepend(), replace(), removeAt()
858*/
859
860/*! \fn template <class T> QList<T>::iterator QList<T>::insert(iterator before, const T &value)
861
862 \overload
863
864 Inserts \a value in front of the item pointed to by the
865 iterator \a before. Returns an iterator pointing at the inserted
866 item. Note that the iterator passed to the function will be
867 invalid after the call; the returned iterator should be used
868 instead.
869*/
870
871/*! \fn template <class T> void QList<T>::replace(int i, const T &value)
872
873 Replaces the item at index position \a i with \a value. \a i must
874 be a valid index position in the list (i.e., 0 <= \a i < size()).
875
876 \sa operator[](), removeAt()
877*/
878
879/*!
880 \fn template <class T> int QList<T>::removeAll(const T &value)
881
882 Removes all occurrences of \a value in the list and returns the
883 number of entries removed.
884
885 Example:
886 \snippet code/src_corelib_tools_qlistdata.cpp 9
887
888 This function requires the value type to have an implementation of
889 \c operator==().
890
891 \sa removeOne(), removeAt(), takeAt(), replace()
892*/
893
894/*!
895 \fn template <class T> bool QList<T>::removeOne(const T &value)
896 \since 4.4
897
898 Removes the first occurrence of \a value in the list and returns
899 true on success; otherwise returns \c false.
900
901 Example:
902 \snippet code/src_corelib_tools_qlistdata.cpp 10
903
904 This function requires the value type to have an implementation of
905 \c operator==().
906
907 \sa removeAll(), removeAt(), takeAt(), replace()
908*/
909
910/*! \fn template <class T> void QList<T>::removeAt(int i)
911
912 Removes the item at index position \a i. \a i must be a valid
913 index position in the list (i.e., 0 <= \a i < size()).
914
915 \sa takeAt(), removeFirst(), removeLast(), removeOne()
916*/
917
918/*! \fn template <class T> T QList<T>::takeAt(int i)
919
920 Removes the item at index position \a i and returns it. \a i must
921 be a valid index position in the list (i.e., 0 <= \a i < size()).
922
923 If you don't use the return value, removeAt() is more efficient.
924
925 \sa removeAt(), takeFirst(), takeLast()
926*/
927
928/*! \fn template <class T> T QList<T>::takeFirst()
929
930 Removes the first item in the list and returns it. This is the
931 same as takeAt(0). This function assumes the list is not empty. To
932 avoid failure, call isEmpty() before calling this function.
933
934 If this list is not shared, this operation takes
935 \l {Algorithmic Complexity}{constant time}.
936
937 If you don't use the return value, removeFirst() is more
938 efficient.
939
940 \sa takeLast(), takeAt(), removeFirst()
941*/
942
943/*! \fn template <class T> T QList<T>::takeLast()
944
945 Removes the last item in the list and returns it. This is the
946 same as takeAt(size() - 1). This function assumes the list is
947 not empty. To avoid failure, call isEmpty() before calling this
948 function.
949
950 If this list is not shared, this operation takes
951 \l {Algorithmic Complexity}{constant time}.
952
953 If you don't use the return value, removeLast() is more
954 efficient.
955
956 \sa takeFirst(), takeAt(), removeLast()
957*/
958
959/*! \fn template <class T> void QList<T>::move(int from, int to)
960
961 Moves the item at index position \a from to index position \a to.
962
963 Example:
964 \snippet code/src_corelib_tools_qlistdata.cpp 11
965
966 This is the same as insert(\a{to}, takeAt(\a{from})).This function
967 assumes that both \a from and \a to are at least 0 but less than
968 size(). To avoid failure, test that both \a from and \a to are at
969 least 0 and less than size().
970
971 \sa swap(), insert(), takeAt()
972*/
973
974/*! \fn template <class T> void QList<T>::swap(int i, int j)
975
976 \obsolete Use swapItemsAt()
977
978 \sa move(), swapItemsAt()
979*/
980
981/*! \fn template <class T> void QList<T>::swapItemsAt(int i, int j)
982 \since 5.13
983
984 Exchange the item at index position \a i with the item at index
985 position \a j. This function assumes that both \a i and \a j are
986 at least 0 but less than size(). To avoid failure, test that both
987 \a i and \a j are at least 0 and less than size().
988
989 Example:
990 \snippet code/src_corelib_tools_qlistdata.cpp 12
991
992 \sa move()
993*/
994
995/*! \fn template <class T> int QList<T>::indexOf(const T &value, int from = 0) const
996
997 Returns the index position of the first occurrence of \a value in
998 the list, searching forward from index position \a from. Returns
999 -1 if no item matched.
1000
1001 Example:
1002 \snippet code/src_corelib_tools_qlistdata.cpp 13
1003
1004 This function requires the value type to have an implementation of
1005 \c operator==().
1006
1007 Note that QList uses 0-based indexes, just like C++ arrays. Negative
1008 indexes are not supported with the exception of the value mentioned
1009 above.
1010
1011 \sa lastIndexOf(), contains()
1012*/
1013
1014/*! \fn template <class T> int QList<T>::lastIndexOf(const T &value, int from = -1) const
1015
1016 Returns the index position of the last occurrence of \a value in
1017 the list, searching backward from index position \a from. If \a
1018 from is -1 (the default), the search starts at the last item.
1019 Returns -1 if no item matched.
1020
1021 Example:
1022 \snippet code/src_corelib_tools_qlistdata.cpp 14
1023
1024 This function requires the value type to have an implementation of
1025 \c operator==().
1026
1027 Note that QList uses 0-based indexes, just like C++ arrays. Negative
1028 indexes are not supported with the exception of the value mentioned
1029 above.
1030
1031 \sa indexOf()
1032*/
1033
1034/*! \fn template <class T> bool QList<T>::contains(const T &value) const
1035
1036 Returns \c true if the list contains an occurrence of \a value;
1037 otherwise returns \c false.
1038
1039 This function requires the value type to have an implementation of
1040 \c operator==().
1041
1042 \sa indexOf(), count()
1043*/
1044
1045/*! \fn template <class T> int QList<T>::count(const T &value) const
1046
1047 Returns the number of occurrences of \a value in the list.
1048
1049 This function requires the value type to have an implementation of
1050 \c operator==().
1051
1052 \sa contains(), indexOf()
1053*/
1054
1055/*! \fn template <class T> bool QList<T>::startsWith(const T &value) const
1056 \since 4.5
1057
1058 Returns \c true if this list is not empty and its first
1059 item is equal to \a value; otherwise returns \c false.
1060
1061 \sa isEmpty(), contains()
1062*/
1063
1064/*! \fn template <class T> bool QList<T>::endsWith(const T &value) const
1065 \since 4.5
1066
1067 Returns \c true if this list is not empty and its last
1068 item is equal to \a value; otherwise returns \c false.
1069
1070 \sa isEmpty(), contains()
1071*/
1072
1073/*! \fn template <class T> QList<T>::iterator QList<T>::begin()
1074
1075 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in
1076 the list.
1077
1078 \sa constBegin(), end()
1079*/
1080
1081/*! \fn template <class T> QList<T>::const_iterator QList<T>::begin() const
1082
1083 \overload
1084*/
1085
1086/*! \fn template <class T> QList<T>::const_iterator QList<T>::cbegin() const
1087 \since 5.0
1088
1089 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
1090 in the list.
1091
1092 \sa begin(), cend()
1093*/
1094
1095/*! \fn template <class T> QList<T>::const_iterator QList<T>::constBegin() const
1096
1097 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
1098 in the list.
1099
1100 \sa begin(), constEnd()
1101*/
1102
1103/*! \fn template <class T> QList<T>::iterator QList<T>::end()
1104
1105 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item
1106 after the last item in the list.
1107
1108 \sa begin(), constEnd()
1109*/
1110
1111/*! \fn template <class T> const_iterator QList<T>::end() const
1112
1113 \overload
1114*/
1115
1116/*! \fn template <class T> QList<T>::const_iterator QList<T>::cend() const
1117 \since 5.0
1118
1119 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1120 item after the last item in the list.
1121
1122 \sa cbegin(), end()
1123*/
1124
1125/*! \fn template <class T> QList<T>::const_iterator QList<T>::constEnd() const
1126
1127 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1128 item after the last item in the list.
1129
1130 \sa constBegin(), end()
1131*/
1132
1133/*! \fn template <class T> QList<T>::reverse_iterator QList<T>::rbegin()
1134 \since 5.6
1135
1136 Returns a \l{STL-style iterators}{STL-style} reverse iterator pointing to the first
1137 item in the list, in reverse order.
1138
1139 \sa begin(), crbegin(), rend()
1140*/
1141
1142/*! \fn template <class T> QList<T>::const_reverse_iterator QList<T>::rbegin() const
1143 \since 5.6
1144 \overload
1145*/
1146
1147/*! \fn template <class T> QList<T>::const_reverse_iterator QList<T>::crbegin() const
1148 \since 5.6
1149
1150 Returns a const \l{STL-style iterators}{STL-style} reverse iterator pointing to the first
1151 item in the list, in reverse order.
1152
1153 \sa begin(), rbegin(), rend()
1154*/
1155
1156/*! \fn template <class T> QList<T>::reverse_iterator QList<T>::rend()
1157 \since 5.6
1158
1159 Returns a \l{STL-style iterators}{STL-style} reverse iterator pointing to one past
1160 the last item in the list, in reverse order.
1161
1162 \sa end(), crend(), rbegin()
1163*/
1164
1165/*! \fn template <class T> QList<T>::const_reverse_iterator QList<T>::rend() const
1166 \since 5.6
1167 \overload
1168*/
1169
1170/*! \fn template <class T> QList<T>::const_reverse_iterator QList<T>::crend() const
1171 \since 5.6
1172
1173 Returns a const \l{STL-style iterators}{STL-style} reverse iterator pointing to one
1174 past the last item in the list, in reverse order.
1175
1176 \sa end(), rend(), rbegin()
1177*/
1178
1179/*! \fn template <class T> QList<T>::iterator QList<T>::erase(iterator pos)
1180
1181 Removes the item associated with the iterator \a pos from the
1182 list, and returns an iterator to the next item in the list (which
1183 may be end()).
1184
1185 \sa insert(), removeAt()
1186*/
1187
1188/*! \fn template <class T> QList<T>::iterator QList<T>::erase(iterator begin, iterator end)
1189
1190 \overload
1191
1192 Removes all the items from \a begin up to (but not including) \a
1193 end. Returns an iterator to the same item that \a end referred to
1194 before the call.
1195*/
1196
1197/*! \typedef QList::Iterator
1198
1199 Qt-style synonym for QList::iterator.
1200*/
1201
1202/*! \typedef QList::ConstIterator
1203
1204 Qt-style synonym for QList::const_iterator.
1205*/
1206
1207/*!
1208 \typedef QList::size_type
1209
1210 Typedef for int. Provided for STL compatibility.
1211*/
1212
1213/*!
1214 \typedef QList::value_type
1215
1216 Typedef for T. Provided for STL compatibility.
1217*/
1218
1219/*!
1220 \typedef QList::difference_type
1221
1222 Typedef for ptrdiff_t. Provided for STL compatibility.
1223*/
1224
1225/*!
1226 \typedef QList::pointer
1227
1228 Typedef for T *. Provided for STL compatibility.
1229*/
1230
1231/*!
1232 \typedef QList::const_pointer
1233
1234 Typedef for const T *. Provided for STL compatibility.
1235*/
1236
1237/*!
1238 \typedef QList::reference
1239
1240 Typedef for T &. Provided for STL compatibility.
1241*/
1242
1243/*!
1244 \typedef QList::const_reference
1245
1246 Typedef for const T &. Provided for STL compatibility.
1247*/
1248
1249/*! \typedef QList::reverse_iterator
1250 \since 5.6
1251
1252 The QList::reverse_iterator typedef provides an STL-style non-const
1253 reverse iterator for QList.
1254
1255 It is simply a typedef for \c{std::reverse_iterator<iterator>}.
1256
1257 \warning Iterators on implicitly shared containers do not work
1258 exactly like STL-iterators. You should avoid copying a container
1259 while iterators are active on that container. For more information,
1260 read \l{Implicit sharing iterator problem}.
1261
1262 \sa QList::rbegin(), QList::rend(), QList::const_reverse_iterator, QList::iterator
1263*/
1264
1265/*! \typedef QList::const_reverse_iterator
1266 \since 5.6
1267
1268 The QList::const_reverse_iterator typedef provides an STL-style const
1269 reverse iterator for QList.
1270
1271 It is simply a typedef for \c{std::reverse_iterator<const_iterator>}.
1272
1273 \warning Iterators on implicitly shared containers do not work
1274 exactly like STL-iterators. You should avoid copying a container
1275 while iterators are active on that container. For more information,
1276 read \l{Implicit sharing iterator problem}.
1277
1278 \sa QList::rbegin(), QList::rend(), QList::reverse_iterator, QList::const_iterator
1279*/
1280
1281/*! \fn template <class T> int QList<T>::count() const
1282
1283 Returns the number of items in the list. This is effectively the
1284 same as size().
1285*/
1286
1287/*! \fn template <class T> int QList<T>::length() const
1288 \since 4.5
1289
1290 This function is identical to count().
1291
1292 \sa count()
1293*/
1294
1295/*! \fn template <class T> T& QList<T>::first()
1296
1297 Returns a reference to the first item in the list. The list must
1298 not be empty. If the list can be empty, call isEmpty() before
1299 calling this function.
1300
1301 \sa constFirst(), last(), isEmpty()
1302*/
1303
1304/*! \fn template <class T> const T& QList<T>::first() const
1305
1306 \overload
1307*/
1308
1309/*! \fn template <class T> const T& QList<T>::constFirst() const
1310 \since 5.6
1311
1312 Returns a const reference to the first item in the list. The list must
1313 not be empty. If the list can be empty, call isEmpty() before
1314 calling this function.
1315
1316 \sa constLast(), isEmpty(), first()
1317*/
1318
1319/*! \fn template <class T> T& QList<T>::last()
1320
1321 Returns a reference to the last item in the list. The list must
1322 not be empty. If the list can be empty, call isEmpty() before
1323 calling this function.
1324
1325 \sa constLast(), first(), isEmpty()
1326*/
1327
1328/*! \fn template <class T> const T& QList<T>::last() const
1329
1330 \overload
1331*/
1332
1333/*! \fn template <class T> const T& QList<T>::constLast() const
1334 \since 5.6
1335
1336 Returns a reference to the last item in the list. The list must
1337 not be empty. If the list can be empty, call isEmpty() before
1338 calling this function.
1339
1340 \sa constFirst(), isEmpty(), last()
1341*/
1342
1343/*! \fn template <class T> void QList<T>::removeFirst()
1344
1345 Removes the first item in the list. Calling this function is
1346 equivalent to calling removeAt(0). The list must not be empty. If
1347 the list can be empty, call isEmpty() before calling this
1348 function.
1349
1350 \sa removeAt(), takeFirst()
1351*/
1352
1353/*! \fn template <class T> void QList<T>::removeLast()
1354
1355 Removes the last item in the list. Calling this function is
1356 equivalent to calling removeAt(size() - 1). The list must not be
1357 empty. If the list can be empty, call isEmpty() before calling
1358 this function.
1359
1360 \sa removeAt(), takeLast()
1361*/
1362
1363/*! \fn template <class T> T QList<T>::value(int i) const
1364
1365 Returns the value at index position \a i in the list.
1366
1367 If the index \a i is out of bounds, the function returns a
1368 \l{default-constructed value}. If you are certain that the index
1369 is going to be within bounds, you can use at() instead, which is
1370 slightly faster.
1371
1372 \sa at(), operator[]()
1373*/
1374
1375/*! \fn template <class T> T QList<T>::value(int i, const T &defaultValue) const
1376
1377 \overload
1378
1379 If the index \a i is out of bounds, the function returns
1380 \a defaultValue.
1381*/
1382
1383/*! \fn template <class T> void QList<T>::push_back(const T &value)
1384
1385 This function is provided for STL compatibility. It is equivalent
1386 to \l{QList::append()}{append(\a value)}.
1387*/
1388
1389/*! \fn template <class T> void QList<T>::push_front(const T &value)
1390
1391 This function is provided for STL compatibility. It is equivalent
1392 to \l{QList::prepend()}{prepend(\a value)}.
1393*/
1394
1395/*! \fn template <class T> T& QList<T>::front()
1396
1397 This function is provided for STL compatibility. It is equivalent
1398 to first(). The list must not be empty. If the list can be empty,
1399 call isEmpty() before calling this function.
1400*/
1401
1402/*! \fn template <class T> const T& QList<T>::front() const
1403
1404 \overload
1405*/
1406
1407/*! \fn template <class T> T& QList<T>::back()
1408
1409 This function is provided for STL compatibility. It is equivalent
1410 to last(). The list must not be empty. If the list can be empty,
1411 call isEmpty() before calling this function.
1412*/
1413
1414/*! \fn template <class T> const T& QList<T>::back() const
1415
1416 \overload
1417*/
1418
1419/*! \fn template <class T> void QList<T>::pop_front()
1420
1421 This function is provided for STL compatibility. It is equivalent
1422 to removeFirst(). The list must not be empty. If the list can be
1423 empty, call isEmpty() before calling this function.
1424*/
1425
1426/*! \fn template <class T> void QList<T>::pop_back()
1427
1428 This function is provided for STL compatibility. It is equivalent
1429 to removeLast(). The list must not be empty. If the list can be
1430 empty, call isEmpty() before calling this function.
1431*/
1432
1433/*! \fn template <class T> bool QList<T>::empty() const
1434
1435 This function is provided for STL compatibility. It is equivalent
1436 to isEmpty() and returns \c true if the list is empty.
1437*/
1438
1439/*! \fn template <class T> QList<T> &QList<T>::operator+=(const QList<T> &other)
1440
1441 Appends the items of the \a other list to this list and returns a
1442 reference to this list.
1443
1444 \sa operator+(), append()
1445*/
1446
1447/*! \fn template <class T> void QList<T>::operator+=(const T &value)
1448
1449 \overload
1450
1451 Appends \a value to the list.
1452
1453 \sa append(), operator<<()
1454*/
1455
1456/*! \fn template <class T> QList<T> QList<T>::operator+(const QList<T> &other) const
1457
1458 Returns a list that contains all the items in this list followed
1459 by all the items in the \a other list.
1460
1461 \sa operator+=()
1462*/
1463
1464/*! \fn template <class T> QList<T> &QList<T>::operator<<(const QList<T> &other)
1465
1466 Appends the items of the \a other list to this list and returns a
1467 reference to this list.
1468
1469 \sa operator+=(), append()
1470*/
1471
1472/*! \fn template <class T> void QList<T>::operator<<(const T &value)
1473
1474 \overload
1475
1476 Appends \a value to the list.
1477*/
1478
1479/*! \class QList::iterator
1480 \inmodule QtCore
1481 \brief The QList::iterator class provides an STL-style non-const iterator for QList and QQueue.
1482
1483 QList features both \l{STL-style iterators} and \l{Java-style
1484 iterators}. The STL-style iterators are more low-level and more
1485 cumbersome to use; on the other hand, they are slightly faster
1486 and, for developers who already know STL, have the advantage of
1487 familiarity.
1488
1489 QList\<T\>::iterator allows you to iterate over a QList\<T\> (or
1490 QQueue\<T\>) and to modify the list item associated with the
1491 iterator. If you want to iterate over a const QList, use
1492 QList::const_iterator instead. It is generally good practice to
1493 use QList::const_iterator on a non-const QList as well, unless
1494 you need to change the QList through the iterator. Const
1495 iterators are slightly faster, and can improve code readability.
1496
1497 The default QList::iterator constructor creates an uninitialized
1498 iterator. You must initialize it using a QList function like
1499 QList::begin(), QList::end(), or QList::insert() before you can
1500 start iterating. Here's a typical loop that prints all the items
1501 stored in a list:
1502
1503 \snippet code/src_corelib_tools_qlistdata.cpp 15
1504
1505 Let's see a few examples of things we can do with a
1506 QList::iterator that we cannot do with a QList::const_iterator.
1507 Here's an example that increments every value stored in a
1508 QList\<int\> by 2:
1509
1510 \snippet code/src_corelib_tools_qlistdata.cpp 16
1511
1512 Most QList functions accept an integer index rather than an
1513 iterator. For that reason, iterators are rarely useful in
1514 connection with QList. One place where STL-style iterators do
1515 make sense is as arguments to \l{generic algorithms}.
1516
1517 For example, here's how to delete all the widgets stored in a
1518 QList\<QWidget *\>:
1519
1520 \snippet code/src_corelib_tools_qlistdata.cpp 17
1521
1522 Multiple iterators can be used on the same list. However, be
1523 aware that any non-const function call performed on the QList
1524 will render all existing iterators undefined. If you need to keep
1525 iterators over a long period of time, we recommend that you use
1526 QLinkedList rather than QList.
1527
1528 \warning Iterators on implicitly shared containers do not work
1529 exactly like STL-iterators. You should avoid copying a container
1530 while iterators are active on that container. For more information,
1531 read \l{Implicit sharing iterator problem}.
1532
1533 \sa QList::const_iterator, QMutableListIterator
1534*/
1535
1536/*! \typedef QList::iterator::iterator_category
1537
1538 A synonym for \e {std::random_access_iterator_tag} indicating
1539 this iterator is a random access iterator.
1540*/
1541
1542/*! \typedef QList::iterator::difference_type
1543
1544 \internal
1545*/
1546
1547/*! \typedef QList::iterator::value_type
1548
1549 \internal
1550*/
1551
1552/*! \typedef QList::iterator::pointer
1553
1554 \internal
1555*/
1556
1557/*! \typedef QList::iterator::reference
1558
1559 \internal
1560*/
1561
1562/*! \fn template <class T> QList<T>::iterator::iterator()
1563
1564 Constructs an uninitialized iterator.
1565
1566 Functions like operator*() and operator++() should not be called
1567 on an uninitialized iterator. Use operator=() to assign a value
1568 to it before using it.
1569
1570 \sa QList::begin(), QList::end()
1571*/
1572
1573/*! \fn template <class T> QList<T>::iterator::iterator(Node *node)
1574
1575 \internal
1576*/
1577
1578/*! \fn template <class T> QList<T>::iterator::iterator(const iterator &other)
1579
1580 Constructs a copy of \a other.
1581*/
1582
1583/*! \fn template <class T> T &QList<T>::iterator::operator*() const
1584
1585 Returns a modifiable reference to the current item.
1586
1587 You can change the value of an item by using operator*() on the
1588 left side of an assignment, for example:
1589
1590 \snippet code/src_corelib_tools_qlistdata.cpp 18
1591
1592 \sa operator->()
1593*/
1594
1595/*! \fn template <class T> T *QList<T>::iterator::operator->() const
1596
1597 Returns a pointer to the current item.
1598
1599 \sa operator*()
1600*/
1601
1602/*! \fn template <class T> T &QList<T>::iterator::operator[](difference_type j) const
1603
1604 Returns a modifiable reference to the item at position *this +
1605 \a{j}.
1606
1607 This function is provided to make QList iterators behave like C++
1608 pointers.
1609
1610 \sa operator+()
1611*/
1612
1613/*!
1614 \fn template <class T> bool QList<T>::iterator::operator==(const iterator &other) const
1615 \fn template <class T> bool QList<T>::iterator::operator==(const const_iterator &other) const
1616
1617 Returns \c true if \a other points to the same item as this
1618 iterator; otherwise returns \c false.
1619
1620 \sa operator!=()
1621*/
1622
1623/*!
1624 \fn template <class T> bool QList<T>::iterator::operator!=(const iterator &other) const
1625 \fn template <class T> bool QList<T>::iterator::operator!=(const const_iterator &other) const
1626
1627 Returns \c true if \a other points to a different item than this
1628 iterator; otherwise returns \c false.
1629
1630 \sa operator==()
1631*/
1632
1633/*!
1634 \fn template <class T> bool QList<T>::iterator::operator<(const iterator& other) const
1635 \fn template <class T> bool QList<T>::iterator::operator<(const const_iterator& other) const
1636
1637 Returns \c true if the item pointed to by this iterator is less than
1638 the item pointed to by the \a other iterator.
1639*/
1640
1641/*!
1642 \fn template <class T> bool QList<T>::iterator::operator<=(const iterator& other) const
1643 \fn template <class T> bool QList<T>::iterator::operator<=(const const_iterator& other) const
1644
1645 Returns \c true if the item pointed to by this iterator is less than
1646 or equal to the item pointed to by the \a other iterator.
1647*/
1648
1649/*!
1650 \fn template <class T> bool QList<T>::iterator::operator>(const iterator& other) const
1651 \fn template <class T> bool QList<T>::iterator::operator>(const const_iterator& other) const
1652
1653 Returns \c true if the item pointed to by this iterator is greater
1654 than the item pointed to by the \a other iterator.
1655*/
1656
1657/*!
1658 \fn template <class T> bool QList<T>::iterator::operator>=(const iterator& other) const
1659 \fn template <class T> bool QList<T>::iterator::operator>=(const const_iterator& other) const
1660
1661 Returns \c true if the item pointed to by this iterator is greater
1662 than or equal to the item pointed to by the \a other iterator.
1663*/
1664
1665/*! \fn template <class T> QList<T>::iterator &QList<T>::iterator::operator++()
1666
1667 The prefix ++ operator (\c{++it}) advances the iterator to the
1668 next item in the list and returns an iterator to the new current
1669 item.
1670
1671 Calling this function on QList::end() leads to undefined results.
1672
1673 \sa operator--()
1674*/
1675
1676/*! \fn template <class T> QList<T>::iterator QList<T>::iterator::operator++(int)
1677
1678 \overload
1679
1680 The postfix ++ operator (\c{it++}) advances the iterator to the
1681 next item in the list and returns an iterator to the previously
1682 current item.
1683*/
1684
1685/*! \fn template <class T> QList<T>::iterator &QList<T>::iterator::operator--()
1686
1687 The prefix -- operator (\c{--it}) makes the preceding item
1688 current and returns an iterator to the new current item.
1689
1690 Calling this function on QList::begin() leads to undefined results.
1691
1692 \sa operator++()
1693*/
1694
1695/*! \fn template <class T> QList<T>::iterator QList<T>::iterator::operator--(int)
1696
1697 \overload
1698
1699 The postfix -- operator (\c{it--}) makes the preceding item
1700 current and returns an iterator to the previously current item.
1701*/
1702
1703/*! \fn template <class T> QList<T>::iterator &QList<T>::iterator::operator+=(difference_type j)
1704
1705 Advances the iterator by \a j items. (If \a j is negative, the
1706 iterator goes backward.)
1707
1708 \sa operator-=(), operator+()
1709*/
1710
1711/*! \fn template <class T> QList<T>::iterator &QList<T>::iterator::operator-=(difference_type j)
1712
1713 Makes the iterator go back by \a j items. (If \a j is negative,
1714 the iterator goes forward.)
1715
1716 \sa operator+=(), operator-()
1717*/
1718
1719/*! \fn template <class T> QList<T>::iterator QList<T>::iterator::operator+(difference_type j) const
1720
1721 Returns an iterator to the item at \a j positions forward from
1722 this iterator. (If \a j is negative, the iterator goes backward.)
1723
1724 \sa operator-(), operator+=()
1725*/
1726
1727/*! \fn template <class T> QList<T>::iterator QList<T>::iterator::operator-(difference_type j) const
1728
1729 Returns an iterator to the item at \a j positions backward from
1730 this iterator. (If \a j is negative, the iterator goes forward.)
1731
1732 \sa operator+(), operator-=()
1733*/
1734
1735/*! \fn template <class T> int QList<T>::iterator::operator-(iterator other) const
1736
1737 Returns the number of items between the item pointed to by \a
1738 other and the item pointed to by this iterator.
1739*/
1740
1741/*! \class QList::const_iterator
1742 \inmodule QtCore
1743 \brief The QList::const_iterator class provides an STL-style const iterator for QList and QQueue.
1744
1745 QList provides both \l{STL-style iterators} and \l{Java-style
1746 iterators}. The STL-style iterators are more low-level and more
1747 cumbersome to use; on the other hand, they are slightly faster
1748 and, for developers who already know STL, have the advantage of
1749 familiarity.
1750
1751 QList\<T\>::const_iterator allows you to iterate over a
1752 QList\<T\> (or a QQueue\<T\>). If you want to modify the QList as
1753 you iterate over it, use QList::iterator instead. It is generally
1754 good practice to use QList::const_iterator on a non-const QList
1755 as well, unless you need to change the QList through the
1756 iterator. Const iterators are slightly faster, and can improve
1757 code readability.
1758
1759 The default QList::const_iterator constructor creates an
1760 uninitialized iterator. You must initialize it using a QList
1761 function like QList::constBegin(), QList::constEnd(), or
1762 QList::insert() before you can start iterating. Here's a typical
1763 loop that prints all the items stored in a list:
1764
1765 \snippet code/src_corelib_tools_qlistdata.cpp 19
1766
1767 Most QList functions accept an integer index rather than an
1768 iterator. For that reason, iterators are rarely useful in
1769 connection with QList. One place where STL-style iterators do
1770 make sense is as arguments to \l{generic algorithms}.
1771
1772 For example, here's how to delete all the widgets stored in a
1773 QList\<QWidget *\>:
1774
1775 \snippet code/src_corelib_tools_qlistdata.cpp 20
1776
1777 Multiple iterators can be used on the same list. However, be
1778 aware that any non-const function call performed on the QList
1779 will render all existing iterators undefined. If you need to keep
1780 iterators over a long period of time, we recommend that you use
1781 QLinkedList rather than QList.
1782
1783 \warning Iterators on implicitly shared containers do not work
1784 exactly like STL-iterators. You should avoid copying a container
1785 while iterators are active on that container. For more information,
1786 read \l{Implicit sharing iterator problem}.
1787
1788 \sa QList::iterator, QListIterator
1789*/
1790
1791/*! \fn template <class T> QList<T>::const_iterator::const_iterator()
1792
1793 Constructs an uninitialized iterator.
1794
1795 Functions like operator*() and operator++() should not be called
1796 on an uninitialized iterator. Use operator=() to assign a value
1797 to it before using it.
1798
1799 \sa QList::constBegin(), QList::constEnd()
1800*/
1801
1802/*! \typedef QList::const_iterator::iterator_category
1803
1804 A synonym for \e {std::random_access_iterator_tag} indicating
1805 this iterator is a random access iterator.
1806*/
1807
1808/*! \typedef QList::const_iterator::difference_type
1809
1810 \internal
1811*/
1812
1813/*! \typedef QList::const_iterator::value_type
1814
1815 \internal
1816*/
1817
1818/*! \typedef QList::const_iterator::pointer
1819
1820 \internal
1821*/
1822
1823/*! \typedef QList::const_iterator::reference
1824
1825 \internal
1826*/
1827
1828/*! \fn template <class T> QList<T>::const_iterator::const_iterator(Node *node)
1829
1830 \internal
1831*/
1832
1833/*! \fn template <class T> QList<T>::const_iterator::const_iterator(const const_iterator &other)
1834
1835 Constructs a copy of \a other.
1836*/
1837
1838/*! \fn template <class T> QList<T>::const_iterator::const_iterator(const iterator &other)
1839
1840 Constructs a copy of \a other.
1841*/
1842
1843/*! \fn template <class T> const T &QList<T>::const_iterator::operator*() const
1844
1845 Returns the current item.
1846
1847 \sa operator->()
1848*/
1849
1850/*! \fn template <class T> const T *QList<T>::const_iterator::operator->() const
1851
1852 Returns a pointer to the current item.
1853
1854 \sa operator*()
1855*/
1856
1857/*! \fn template <class T> const T &QList<T>::const_iterator::operator[](difference_type j) const
1858
1859 Returns the item at position *this + \a{j}.
1860
1861 This function is provided to make QList iterators behave like C++
1862 pointers.
1863
1864 \sa operator+()
1865*/
1866
1867/*! \fn template <class T> bool QList<T>::const_iterator::operator==(const const_iterator &other) const
1868
1869 Returns \c true if \a other points to the same item as this
1870 iterator; otherwise returns \c false.
1871
1872 \sa operator!=()
1873*/
1874
1875/*! \fn template <class T> bool QList<T>::const_iterator::operator!=(const const_iterator &other) const
1876
1877 Returns \c true if \a other points to a different item than this
1878 iterator; otherwise returns \c false.
1879
1880 \sa operator==()
1881*/
1882
1883/*!
1884 \fn template <class T> bool QList<T>::const_iterator::operator<(const const_iterator& other) const
1885
1886 Returns \c true if the item pointed to by this iterator is less than
1887 the item pointed to by the \a other iterator.
1888*/
1889
1890/*!
1891 \fn template <class T> bool QList<T>::const_iterator::operator<=(const const_iterator& other) const
1892
1893 Returns \c true if the item pointed to by this iterator is less than
1894 or equal to the item pointed to by the \a other iterator.
1895*/
1896
1897/*!
1898 \fn template <class T> bool QList<T>::const_iterator::operator>(const const_iterator& other) const
1899
1900 Returns \c true if the item pointed to by this iterator is greater
1901 than the item pointed to by the \a other iterator.
1902*/
1903
1904/*!
1905 \fn template <class T> bool QList<T>::const_iterator::operator>=(const const_iterator& other) const
1906
1907 Returns \c true if the item pointed to by this iterator is greater
1908 than or equal to the item pointed to by the \a other iterator.
1909*/
1910
1911/*! \fn template <class T> QList<T>::const_iterator &QList<T>::const_iterator::operator++()
1912
1913 The prefix ++ operator (\c{++it}) advances the iterator to the
1914 next item in the list and returns an iterator to the new current
1915 item.
1916
1917 Calling this function on QList::end() leads to undefined results.
1918
1919 \sa operator--()
1920*/
1921
1922/*! \fn template <class T> QList<T>::const_iterator QList<T>::const_iterator::operator++(int)
1923
1924 \overload
1925
1926 The postfix ++ operator (\c{it++}) advances the iterator to the
1927 next item in the list and returns an iterator to the previously
1928 current item.
1929*/
1930
1931/*! \fn template <class T> QList<T>::const_iterator &QList<T>::const_iterator::operator--()
1932
1933 The prefix -- operator (\c{--it}) makes the preceding item
1934 current and returns an iterator to the new current item.
1935
1936 Calling this function on QList::begin() leads to undefined results.
1937
1938 \sa operator++()
1939*/
1940
1941/*! \fn template <class T> QList<T>::const_iterator QList<T>::const_iterator::operator--(int)
1942
1943 \overload
1944
1945 The postfix -- operator (\c{it--}) makes the preceding item
1946 current and returns an iterator to the previously current item.
1947*/
1948
1949/*! \fn template <class T> QList<T>::const_iterator &QList<T>::const_iterator::operator+=(difference_type j)
1950
1951 Advances the iterator by \a j items. (If \a j is negative, the
1952 iterator goes backward.)
1953
1954 \sa operator-=(), operator+()
1955*/
1956
1957/*! \fn template <class T> QList<T>::const_iterator &QList<T>::const_iterator::operator-=(difference_type j)
1958
1959 Makes the iterator go back by \a j items. (If \a j is negative,
1960 the iterator goes forward.)
1961
1962 \sa operator+=(), operator-()
1963*/
1964
1965/*! \fn template <class T> QList<T>::const_iterator QList<T>::const_iterator::operator+(difference_type j) const
1966
1967 Returns an iterator to the item at \a j positions forward from
1968 this iterator. (If \a j is negative, the iterator goes backward.)
1969
1970 \sa operator-(), operator+=()
1971*/
1972
1973/*! \fn template <class T> QList<T>::const_iterator QList<T>::const_iterator::operator-(difference_type j) const
1974
1975 Returns an iterator to the item at \a j positions backward from
1976 this iterator. (If \a j is negative, the iterator goes forward.)
1977
1978 \sa operator+(), operator-=()
1979*/
1980
1981/*! \fn template <class T> int QList<T>::const_iterator::operator-(const_iterator other) const
1982
1983 Returns the number of items between the item pointed to by \a
1984 other and the item pointed to by this iterator.
1985*/
1986
1987/*! \fn template <class T> QDataStream &operator<<(QDataStream &out, const QList<T> &list)
1988 \relates QList
1989
1990 Writes the list \a list to stream \a out.
1991
1992 This function requires the value type to implement \c
1993 operator<<().
1994
1995 \sa{Serializing Qt Data Types}{Format of the QDataStream operators}
1996*/
1997
1998/*! \fn template <class T> QDataStream &operator>>(QDataStream &in, QList<T> &list)
1999 \relates QList
2000
2001 Reads a list from stream \a in into \a list.
2002
2003 This function requires the value type to implement \c
2004 operator>>().
2005
2006 \sa{Serializing Qt Data Types}{Format of the QDataStream operators}
2007*/
2008
2009/*! \fn template <class T> QList<T> QList<T>::fromVector(const QVector<T> &vector)
2010
2011 Returns a QList object with the data contained in \a vector.
2012
2013 Example:
2014
2015 \snippet code/src_corelib_tools_qlistdata.cpp 21
2016
2017 \sa fromSet(), toVector(), QVector::toList()
2018*/
2019
2020/*! \fn template <class T> QVector<T> QList<T>::toVector() const
2021
2022 Returns a QVector object with the data contained in this QList.
2023
2024 Example:
2025
2026 \snippet code/src_corelib_tools_qlistdata.cpp 22
2027
2028 \sa toSet(), fromVector(), QVector::fromList()
2029*/
2030
2031/*! \fn template <class T> QList<T> QList<T>::fromSet(const QSet<T> &set)
2032
2033 Returns a QList object with the data contained in \a set. The
2034 order of the elements in the QList is undefined.
2035
2036 Example:
2037
2038 \snippet code/src_corelib_tools_qlistdata.cpp 23
2039
2040 \sa fromVector(), toSet(), QSet::toList()
2041*/
2042
2043/*! \fn template <class T> QSet<T> QList<T>::toSet() const
2044
2045 Returns a QSet object with the data contained in this QList.
2046 Since QSet doesn't allow duplicates, the resulting QSet might be
2047 smaller than the original list was.
2048
2049 Example:
2050
2051 \snippet code/src_corelib_tools_qlistdata.cpp 24
2052
2053 \sa toVector(), fromSet(), QSet::fromList()
2054*/
2055
2056/*! \fn template <class T> QList<T> QList<T>::fromStdList(const std::list<T> &list)
2057
2058 Returns a QList object with the data contained in \a list. The
2059 order of the elements in the QList is the same as in \a list.
2060
2061 Example:
2062
2063 \snippet code/src_corelib_tools_qlistdata.cpp 25
2064
2065 \sa toStdList(), QVector::fromStdVector()
2066*/
2067
2068/*! \fn template <class T> std::list<T> QList<T>::toStdList() const
2069
2070 Returns a std::list object with the data contained in this QList.
2071 Example:
2072
2073 \snippet code/src_corelib_tools_qlistdata.cpp 26
2074
2075 \sa fromStdList(), QVector::toStdVector()
2076*/
2077
2078QT_END_NAMESPACE
2079