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, .alloc: 0, .begin: 0, .end: 0, .array: { 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(elementCount: nl, elementSize: sizeof(void *), headerSize: DataHeaderSize);
96 Data* t = static_cast<Data *>(::malloc(size: 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(size: qCalculateBlockSize(elementCount: alloc, elementSize: sizeof(void*), headerSize: 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(ptr: d, size: qCalculateBlockSize(elementCount: alloc, elementSize: sizeof(void *), headerSize: 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(elementCount: d->alloc + growth, elementSize: sizeof(void *), headerSize: DataHeaderSize);
170 Data *x = static_cast<Data *>(::realloc(ptr: d, size: 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(ptr: 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(dest: d->array, src: d->array + b, n: e * sizeof(void *));
194 d->begin = 0;
195 } else {
196 realloc_grow(growth: 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(n: 1);
207}
208
209// ensures that enough space is available to append the list
210void **QListData::append(const QListData& l)
211{
212 return append(n: 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(growth: 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(dest: d->array + d->begin, src: d->array, n: 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(growth: 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(dest: d->array + d->begin, src: d->array + d->begin + 1, n: i * sizeof(void *));
264 } else {
265 ::memmove(dest: d->array + d->begin + i + 1, src: d->array + d->begin + i,
266 n: (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(dest: d->array + d->begin + 1, src: d->array + d->begin, n: offset * sizeof(void *));
279 d->begin++;
280 } else {
281 if (int offset = d->end - i - 1)
282 ::memmove(dest: d->array + i, src: d->array + i + 1, n: 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(dest: d->array + d->begin + n, src: d->array + d->begin,
294 n: (i - d->begin) * sizeof(void*));
295 d->begin += n;
296 } else {
297 ::memmove(dest: d->array + i, src: d->array + i + n,
298 n: (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(dest: d->array + from, src: d->array + from + 1, n: (to - from) * sizeof(void *));
316 } else {
317 // optimization
318 if (int offset = from - d->begin)
319 ::memmove(dest: d->array + d->begin + 1, src: d->array + d->begin, n: offset * sizeof(void *));
320 if (int offset = d->end - (to + 1))
321 ::memmove(dest: d->array + to + 2, src: d->array + to + 1, n: 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(dest: d->array + to + 1, src: d->array + to, n: (from - to) * sizeof(void *));
329 } else {
330 // optimization
331 if (int offset = to - d->begin)
332 ::memmove(dest: d->array + d->begin - 1, src: d->array + d->begin, n: offset * sizeof(void *));
333 if (int offset = d->end - (from + 1))
334 ::memmove(dest: d->array + from, src: d->array + from + 1, n: 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.
851
852 If \a i == 0, the value is prepended to the list. If \a i == size(),
853 the value is appended to the list.
854
855 Example:
856 \snippet code/src_corelib_tools_qlistdata.cpp 8
857
858 \sa append(), prepend(), replace(), removeAt()
859*/
860
861/*! \fn template <class T> QList<T>::iterator QList<T>::insert(iterator before, const T &value)
862
863 \overload
864
865 Inserts \a value in front of the item pointed to by the
866 iterator \a before. Returns an iterator pointing at the inserted
867 item. Note that the iterator passed to the function will be
868 invalid after the call; the returned iterator should be used
869 instead.
870*/
871
872/*! \fn template <class T> void QList<T>::replace(int i, const T &value)
873
874 Replaces the item at index position \a i with \a value. \a i must
875 be a valid index position in the list (i.e., 0 <= \a i < size()).
876
877 \sa operator[](), removeAt()
878*/
879
880/*!
881 \fn template <class T> int QList<T>::removeAll(const T &value)
882
883 Removes all occurrences of \a value in the list and returns the
884 number of entries removed.
885
886 Example:
887 \snippet code/src_corelib_tools_qlistdata.cpp 9
888
889 This function requires the value type to have an implementation of
890 \c operator==().
891
892 \sa removeOne(), removeAt(), takeAt(), replace()
893*/
894
895/*!
896 \fn template <class T> bool QList<T>::removeOne(const T &value)
897 \since 4.4
898
899 Removes the first occurrence of \a value in the list and returns
900 true on success; otherwise returns \c false.
901
902 Example:
903 \snippet code/src_corelib_tools_qlistdata.cpp 10
904
905 This function requires the value type to have an implementation of
906 \c operator==().
907
908 \sa removeAll(), removeAt(), takeAt(), replace()
909*/
910
911/*! \fn template <class T> void QList<T>::removeAt(int i)
912
913 Removes the item at index position \a i. \a i must be a valid
914 index position in the list (i.e., 0 <= \a i < size()).
915
916 \sa takeAt(), removeFirst(), removeLast(), removeOne()
917*/
918
919/*! \fn template <class T> T QList<T>::takeAt(int i)
920
921 Removes the item at index position \a i and returns it. \a i must
922 be a valid index position in the list (i.e., 0 <= \a i < size()).
923
924 If you don't use the return value, removeAt() is more efficient.
925
926 \sa removeAt(), takeFirst(), takeLast()
927*/
928
929/*! \fn template <class T> T QList<T>::takeFirst()
930
931 Removes the first item in the list and returns it. This is the
932 same as takeAt(0). This function assumes the list is not empty. To
933 avoid failure, call isEmpty() before calling this function.
934
935 If this list is not shared, this operation takes
936 \l {Algorithmic Complexity}{constant time}.
937
938 If you don't use the return value, removeFirst() is more
939 efficient.
940
941 \sa takeLast(), takeAt(), removeFirst()
942*/
943
944/*! \fn template <class T> T QList<T>::takeLast()
945
946 Removes the last item in the list and returns it. This is the
947 same as takeAt(size() - 1). This function assumes the list is
948 not empty. To avoid failure, call isEmpty() before calling this
949 function.
950
951 If this list is not shared, this operation takes
952 \l {Algorithmic Complexity}{constant time}.
953
954 If you don't use the return value, removeLast() is more
955 efficient.
956
957 \sa takeFirst(), takeAt(), removeLast()
958*/
959
960/*! \fn template <class T> void QList<T>::move(int from, int to)
961
962 Moves the item at index position \a from to index position \a to.
963
964 Example:
965 \snippet code/src_corelib_tools_qlistdata.cpp 11
966
967 This is the same as insert(\a{to}, takeAt(\a{from})).This function
968 assumes that both \a from and \a to are at least 0 but less than
969 size(). To avoid failure, test that both \a from and \a to are at
970 least 0 and less than size().
971
972 \sa swap(), insert(), takeAt()
973*/
974
975/*! \fn template <class T> void QList<T>::swap(int i, int j)
976
977 \obsolete Use swapItemsAt()
978
979 \sa move(), swapItemsAt()
980*/
981
982/*! \fn template <class T> void QList<T>::swapItemsAt(int i, int j)
983 \since 5.13
984
985 Exchange the item at index position \a i with the item at index
986 position \a j. This function assumes that both \a i and \a j are
987 at least 0 but less than size(). To avoid failure, test that both
988 \a i and \a j are at least 0 and less than size().
989
990 Example:
991 \snippet code/src_corelib_tools_qlistdata.cpp 12
992
993 \sa move()
994*/
995
996/*! \fn template <class T> int QList<T>::indexOf(const T &value, int from = 0) const
997
998 Returns the index position of the first occurrence of \a value in
999 the list, searching forward from index position \a from. Returns
1000 -1 if no item matched.
1001
1002 Example:
1003 \snippet code/src_corelib_tools_qlistdata.cpp 13
1004
1005 This function requires the value type to have an implementation of
1006 \c operator==().
1007
1008 Note that QList uses 0-based indexes, just like C++ arrays. Negative
1009 indexes are not supported with the exception of the value mentioned
1010 above.
1011
1012 \sa lastIndexOf(), contains()
1013*/
1014
1015/*! \fn template <class T> int QList<T>::lastIndexOf(const T &value, int from = -1) const
1016
1017 Returns the index position of the last occurrence of \a value in
1018 the list, searching backward from index position \a from. If \a
1019 from is -1 (the default), the search starts at the last item.
1020 Returns -1 if no item matched.
1021
1022 Example:
1023 \snippet code/src_corelib_tools_qlistdata.cpp 14
1024
1025 This function requires the value type to have an implementation of
1026 \c operator==().
1027
1028 Note that QList uses 0-based indexes, just like C++ arrays. Negative
1029 indexes are not supported with the exception of the value mentioned
1030 above.
1031
1032 \sa indexOf()
1033*/
1034
1035/*! \fn template <class T> bool QList<T>::contains(const T &value) const
1036
1037 Returns \c true if the list contains an occurrence of \a value;
1038 otherwise returns \c false.
1039
1040 This function requires the value type to have an implementation of
1041 \c operator==().
1042
1043 \sa indexOf(), count()
1044*/
1045
1046/*! \fn template <class T> int QList<T>::count(const T &value) const
1047
1048 Returns the number of occurrences of \a value in the list.
1049
1050 This function requires the value type to have an implementation of
1051 \c operator==().
1052
1053 \sa contains(), indexOf()
1054*/
1055
1056/*! \fn template <class T> bool QList<T>::startsWith(const T &value) const
1057 \since 4.5
1058
1059 Returns \c true if this list is not empty and its first
1060 item is equal to \a value; otherwise returns \c false.
1061
1062 \sa isEmpty(), contains()
1063*/
1064
1065/*! \fn template <class T> bool QList<T>::endsWith(const T &value) const
1066 \since 4.5
1067
1068 Returns \c true if this list is not empty and its last
1069 item is equal to \a value; otherwise returns \c false.
1070
1071 \sa isEmpty(), contains()
1072*/
1073
1074/*! \fn template <class T> QList<T>::iterator QList<T>::begin()
1075
1076 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in
1077 the list.
1078
1079 \sa constBegin(), end()
1080*/
1081
1082/*! \fn template <class T> QList<T>::const_iterator QList<T>::begin() const
1083
1084 \overload
1085*/
1086
1087/*! \fn template <class T> QList<T>::const_iterator QList<T>::cbegin() const
1088 \since 5.0
1089
1090 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
1091 in the list.
1092
1093 \sa begin(), cend()
1094*/
1095
1096/*! \fn template <class T> QList<T>::const_iterator QList<T>::constBegin() const
1097
1098 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
1099 in the list.
1100
1101 \sa begin(), constEnd()
1102*/
1103
1104/*! \fn template <class T> QList<T>::iterator QList<T>::end()
1105
1106 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item
1107 after the last item in the list.
1108
1109 \sa begin(), constEnd()
1110*/
1111
1112/*! \fn template <class T> const_iterator QList<T>::end() const
1113
1114 \overload
1115*/
1116
1117/*! \fn template <class T> QList<T>::const_iterator QList<T>::cend() const
1118 \since 5.0
1119
1120 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1121 item after the last item in the list.
1122
1123 \sa cbegin(), end()
1124*/
1125
1126/*! \fn template <class T> QList<T>::const_iterator QList<T>::constEnd() const
1127
1128 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
1129 item after the last item in the list.
1130
1131 \sa constBegin(), end()
1132*/
1133
1134/*! \fn template <class T> QList<T>::reverse_iterator QList<T>::rbegin()
1135 \since 5.6
1136
1137 Returns a \l{STL-style iterators}{STL-style} reverse iterator pointing to the first
1138 item in the list, in reverse order.
1139
1140 \sa begin(), crbegin(), rend()
1141*/
1142
1143/*! \fn template <class T> QList<T>::const_reverse_iterator QList<T>::rbegin() const
1144 \since 5.6
1145 \overload
1146*/
1147
1148/*! \fn template <class T> QList<T>::const_reverse_iterator QList<T>::crbegin() const
1149 \since 5.6
1150
1151 Returns a const \l{STL-style iterators}{STL-style} reverse iterator pointing to the first
1152 item in the list, in reverse order.
1153
1154 \sa begin(), rbegin(), rend()
1155*/
1156
1157/*! \fn template <class T> QList<T>::reverse_iterator QList<T>::rend()
1158 \since 5.6
1159
1160 Returns a \l{STL-style iterators}{STL-style} reverse iterator pointing to one past
1161 the last item in the list, in reverse order.
1162
1163 \sa end(), crend(), rbegin()
1164*/
1165
1166/*! \fn template <class T> QList<T>::const_reverse_iterator QList<T>::rend() const
1167 \since 5.6
1168 \overload
1169*/
1170
1171/*! \fn template <class T> QList<T>::const_reverse_iterator QList<T>::crend() const
1172 \since 5.6
1173
1174 Returns a const \l{STL-style iterators}{STL-style} reverse iterator pointing to one
1175 past the last item in the list, in reverse order.
1176
1177 \sa end(), rend(), rbegin()
1178*/
1179
1180/*! \fn template <class T> QList<T>::iterator QList<T>::erase(iterator pos)
1181
1182 Removes the item associated with the iterator \a pos from the
1183 list, and returns an iterator to the next item in the list (which
1184 may be end()).
1185
1186 \sa insert(), removeAt()
1187*/
1188
1189/*! \fn template <class T> QList<T>::iterator QList<T>::erase(iterator begin, iterator end)
1190
1191 \overload
1192
1193 Removes all the items from \a begin up to (but not including) \a
1194 end. Returns an iterator to the same item that \a end referred to
1195 before the call.
1196*/
1197
1198/*! \typedef QList::Iterator
1199
1200 Qt-style synonym for QList::iterator.
1201*/
1202
1203/*! \typedef QList::ConstIterator
1204
1205 Qt-style synonym for QList::const_iterator.
1206*/
1207
1208/*!
1209 \typedef QList::size_type
1210
1211 Typedef for int. Provided for STL compatibility.
1212*/
1213
1214/*!
1215 \typedef QList::value_type
1216
1217 Typedef for T. Provided for STL compatibility.
1218*/
1219
1220/*!
1221 \typedef QList::difference_type
1222
1223 Typedef for ptrdiff_t. Provided for STL compatibility.
1224*/
1225
1226/*!
1227 \typedef QList::pointer
1228
1229 Typedef for T *. Provided for STL compatibility.
1230*/
1231
1232/*!
1233 \typedef QList::const_pointer
1234
1235 Typedef for const T *. Provided for STL compatibility.
1236*/
1237
1238/*!
1239 \typedef QList::reference
1240
1241 Typedef for T &. Provided for STL compatibility.
1242*/
1243
1244/*!
1245 \typedef QList::const_reference
1246
1247 Typedef for const T &. Provided for STL compatibility.
1248*/
1249
1250/*! \typedef QList::reverse_iterator
1251 \since 5.6
1252
1253 The QList::reverse_iterator typedef provides an STL-style non-const
1254 reverse iterator for QList.
1255
1256 It is simply a typedef for \c{std::reverse_iterator<iterator>}.
1257
1258 \warning Iterators on implicitly shared containers do not work
1259 exactly like STL-iterators. You should avoid copying a container
1260 while iterators are active on that container. For more information,
1261 read \l{Implicit sharing iterator problem}.
1262
1263 \sa QList::rbegin(), QList::rend(), QList::const_reverse_iterator, QList::iterator
1264*/
1265
1266/*! \typedef QList::const_reverse_iterator
1267 \since 5.6
1268
1269 The QList::const_reverse_iterator typedef provides an STL-style const
1270 reverse iterator for QList.
1271
1272 It is simply a typedef for \c{std::reverse_iterator<const_iterator>}.
1273
1274 \warning Iterators on implicitly shared containers do not work
1275 exactly like STL-iterators. You should avoid copying a container
1276 while iterators are active on that container. For more information,
1277 read \l{Implicit sharing iterator problem}.
1278
1279 \sa QList::rbegin(), QList::rend(), QList::reverse_iterator, QList::const_iterator
1280*/
1281
1282/*! \fn template <class T> int QList<T>::count() const
1283
1284 Returns the number of items in the list. This is effectively the
1285 same as size().
1286*/
1287
1288/*! \fn template <class T> int QList<T>::length() const
1289 \since 4.5
1290
1291 This function is identical to count().
1292
1293 \sa count()
1294*/
1295
1296/*! \fn template <class T> T& QList<T>::first()
1297
1298 Returns a reference to the first item in the list. The list must
1299 not be empty. If the list can be empty, call isEmpty() before
1300 calling this function.
1301
1302 \sa constFirst(), last(), isEmpty()
1303*/
1304
1305/*! \fn template <class T> const T& QList<T>::first() const
1306
1307 \overload
1308*/
1309
1310/*! \fn template <class T> const T& QList<T>::constFirst() const
1311 \since 5.6
1312
1313 Returns a const reference to the first item in the list. The list must
1314 not be empty. If the list can be empty, call isEmpty() before
1315 calling this function.
1316
1317 \sa constLast(), isEmpty(), first()
1318*/
1319
1320/*! \fn template <class T> T& QList<T>::last()
1321
1322 Returns a reference to the last item in the list. The list must
1323 not be empty. If the list can be empty, call isEmpty() before
1324 calling this function.
1325
1326 \sa constLast(), first(), isEmpty()
1327*/
1328
1329/*! \fn template <class T> const T& QList<T>::last() const
1330
1331 \overload
1332*/
1333
1334/*! \fn template <class T> const T& QList<T>::constLast() const
1335 \since 5.6
1336
1337 Returns a reference to the last item in the list. The list must
1338 not be empty. If the list can be empty, call isEmpty() before
1339 calling this function.
1340
1341 \sa constFirst(), isEmpty(), last()
1342*/
1343
1344/*! \fn template <class T> void QList<T>::removeFirst()
1345
1346 Removes the first item in the list. Calling this function is
1347 equivalent to calling removeAt(0). The list must not be empty. If
1348 the list can be empty, call isEmpty() before calling this
1349 function.
1350
1351 \sa removeAt(), takeFirst()
1352*/
1353
1354/*! \fn template <class T> void QList<T>::removeLast()
1355
1356 Removes the last item in the list. Calling this function is
1357 equivalent to calling removeAt(size() - 1). The list must not be
1358 empty. If the list can be empty, call isEmpty() before calling
1359 this function.
1360
1361 \sa removeAt(), takeLast()
1362*/
1363
1364/*! \fn template <class T> T QList<T>::value(int i) const
1365
1366 Returns the value at index position \a i in the list.
1367
1368 If the index \a i is out of bounds, the function returns a
1369 \l{default-constructed value}. If you are certain that the index
1370 is going to be within bounds, you can use at() instead, which is
1371 slightly faster.
1372
1373 \sa at(), operator[]()
1374*/
1375
1376/*! \fn template <class T> T QList<T>::value(int i, const T &defaultValue) const
1377
1378 \overload
1379
1380 If the index \a i is out of bounds, the function returns
1381 \a defaultValue.
1382*/
1383
1384/*! \fn template <class T> void QList<T>::push_back(const T &value)
1385
1386 This function is provided for STL compatibility. It is equivalent
1387 to \l{QList::append()}{append(\a value)}.
1388*/
1389
1390/*! \fn template <class T> void QList<T>::push_front(const T &value)
1391
1392 This function is provided for STL compatibility. It is equivalent
1393 to \l{QList::prepend()}{prepend(\a value)}.
1394*/
1395
1396/*! \fn template <class T> T& QList<T>::front()
1397
1398 This function is provided for STL compatibility. It is equivalent
1399 to first(). The list must not be empty. If the list can be empty,
1400 call isEmpty() before calling this function.
1401*/
1402
1403/*! \fn template <class T> const T& QList<T>::front() const
1404
1405 \overload
1406*/
1407
1408/*! \fn template <class T> T& QList<T>::back()
1409
1410 This function is provided for STL compatibility. It is equivalent
1411 to last(). The list must not be empty. If the list can be empty,
1412 call isEmpty() before calling this function.
1413*/
1414
1415/*! \fn template <class T> const T& QList<T>::back() const
1416
1417 \overload
1418*/
1419
1420/*! \fn template <class T> void QList<T>::pop_front()
1421
1422 This function is provided for STL compatibility. It is equivalent
1423 to removeFirst(). The list must not be empty. If the list can be
1424 empty, call isEmpty() before calling this function.
1425*/
1426
1427/*! \fn template <class T> void QList<T>::pop_back()
1428
1429 This function is provided for STL compatibility. It is equivalent
1430 to removeLast(). The list must not be empty. If the list can be
1431 empty, call isEmpty() before calling this function.
1432*/
1433
1434/*! \fn template <class T> bool QList<T>::empty() const
1435
1436 This function is provided for STL compatibility. It is equivalent
1437 to isEmpty() and returns \c true if the list is empty.
1438*/
1439
1440/*! \fn template <class T> QList<T> &QList<T>::operator+=(const QList<T> &other)
1441
1442 Appends the items of the \a other list to this list and returns a
1443 reference to this list.
1444
1445 \sa operator+(), append()
1446*/
1447
1448/*! \fn template <class T> void QList<T>::operator+=(const T &value)
1449
1450 \overload
1451
1452 Appends \a value to the list.
1453
1454 \sa append(), operator<<()
1455*/
1456
1457/*! \fn template <class T> QList<T> QList<T>::operator+(const QList<T> &other) const
1458
1459 Returns a list that contains all the items in this list followed
1460 by all the items in the \a other list.
1461
1462 \sa operator+=()
1463*/
1464
1465/*! \fn template <class T> QList<T> &QList<T>::operator<<(const QList<T> &other)
1466
1467 Appends the items of the \a other list to this list and returns a
1468 reference to this list.
1469
1470 \sa operator+=(), append()
1471*/
1472
1473/*! \fn template <class T> void QList<T>::operator<<(const T &value)
1474
1475 \overload
1476
1477 Appends \a value to the list.
1478*/
1479
1480/*! \class QList::iterator
1481 \inmodule QtCore
1482 \brief The QList::iterator class provides an STL-style non-const iterator for QList and QQueue.
1483
1484 QList features both \l{STL-style iterators} and \l{Java-style
1485 iterators}. The STL-style iterators are more low-level and more
1486 cumbersome to use; on the other hand, they are slightly faster
1487 and, for developers who already know STL, have the advantage of
1488 familiarity.
1489
1490 QList\<T\>::iterator allows you to iterate over a QList\<T\> (or
1491 QQueue\<T\>) and to modify the list item associated with the
1492 iterator. If you want to iterate over a const QList, use
1493 QList::const_iterator instead. It is generally good practice to
1494 use QList::const_iterator on a non-const QList as well, unless
1495 you need to change the QList through the iterator. Const
1496 iterators are slightly faster, and can improve code readability.
1497
1498 The default QList::iterator constructor creates an uninitialized
1499 iterator. You must initialize it using a QList function like
1500 QList::begin(), QList::end(), or QList::insert() before you can
1501 start iterating. Here's a typical loop that prints all the items
1502 stored in a list:
1503
1504 \snippet code/src_corelib_tools_qlistdata.cpp 15
1505
1506 Let's see a few examples of things we can do with a
1507 QList::iterator that we cannot do with a QList::const_iterator.
1508 Here's an example that increments every value stored in a
1509 QList\<int\> by 2:
1510
1511 \snippet code/src_corelib_tools_qlistdata.cpp 16
1512
1513 Most QList functions accept an integer index rather than an
1514 iterator. For that reason, iterators are rarely useful in
1515 connection with QList. One place where STL-style iterators do
1516 make sense is as arguments to \l{generic algorithms}.
1517
1518 For example, here's how to delete all the widgets stored in a
1519 QList\<QWidget *\>:
1520
1521 \snippet code/src_corelib_tools_qlistdata.cpp 17
1522
1523 Multiple iterators can be used on the same list. However, be
1524 aware that any non-const function call performed on the QList
1525 will render all existing iterators undefined. If you need to keep
1526 iterators over a long period of time, we recommend that you use
1527 QLinkedList rather than QList.
1528
1529 \warning Iterators on implicitly shared containers do not work
1530 exactly like STL-iterators. You should avoid copying a container
1531 while iterators are active on that container. For more information,
1532 read \l{Implicit sharing iterator problem}.
1533
1534 \sa QList::const_iterator, QMutableListIterator
1535*/
1536
1537/*! \typedef QList::iterator::iterator_category
1538
1539 A synonym for \e {std::random_access_iterator_tag} indicating
1540 this iterator is a random access iterator.
1541*/
1542
1543/*! \typedef QList::iterator::difference_type
1544
1545 \internal
1546*/
1547
1548/*! \typedef QList::iterator::value_type
1549
1550 \internal
1551*/
1552
1553/*! \typedef QList::iterator::pointer
1554
1555 \internal
1556*/
1557
1558/*! \typedef QList::iterator::reference
1559
1560 \internal
1561*/
1562
1563/*! \fn template <class T> QList<T>::iterator::iterator()
1564
1565 Constructs an uninitialized iterator.
1566
1567 Functions like operator*() and operator++() should not be called
1568 on an uninitialized iterator. Use operator=() to assign a value
1569 to it before using it.
1570
1571 \sa QList::begin(), QList::end()
1572*/
1573
1574/*! \fn template <class T> QList<T>::iterator::iterator(Node *node)
1575
1576 \internal
1577*/
1578
1579/*! \fn template <class T> QList<T>::iterator::iterator(const iterator &other)
1580
1581 Constructs a copy of \a other.
1582*/
1583
1584/*! \fn template <class T> T &QList<T>::iterator::operator*() const
1585
1586 Returns a modifiable reference to the current item.
1587
1588 You can change the value of an item by using operator*() on the
1589 left side of an assignment, for example:
1590
1591 \snippet code/src_corelib_tools_qlistdata.cpp 18
1592
1593 \sa operator->()
1594*/
1595
1596/*! \fn template <class T> T *QList<T>::iterator::operator->() const
1597
1598 Returns a pointer to the current item.
1599
1600 \sa operator*()
1601*/
1602
1603/*! \fn template <class T> T &QList<T>::iterator::operator[](difference_type j) const
1604
1605 Returns a modifiable reference to the item at position *this +
1606 \a{j}.
1607
1608 This function is provided to make QList iterators behave like C++
1609 pointers.
1610
1611 \sa operator+()
1612*/
1613
1614/*!
1615 \fn template <class T> bool QList<T>::iterator::operator==(const iterator &other) const
1616 \fn template <class T> bool QList<T>::iterator::operator==(const const_iterator &other) const
1617
1618 Returns \c true if \a other points to the same item as this
1619 iterator; otherwise returns \c false.
1620
1621 \sa operator!=()
1622*/
1623
1624/*!
1625 \fn template <class T> bool QList<T>::iterator::operator!=(const iterator &other) const
1626 \fn template <class T> bool QList<T>::iterator::operator!=(const const_iterator &other) const
1627
1628 Returns \c true if \a other points to a different item than this
1629 iterator; otherwise returns \c false.
1630
1631 \sa operator==()
1632*/
1633
1634/*!
1635 \fn template <class T> bool QList<T>::iterator::operator<(const iterator& other) const
1636 \fn template <class T> bool QList<T>::iterator::operator<(const const_iterator& other) const
1637
1638 Returns \c true if the item pointed to by this iterator is less than
1639 the item pointed to by the \a other iterator.
1640*/
1641
1642/*!
1643 \fn template <class T> bool QList<T>::iterator::operator<=(const iterator& other) const
1644 \fn template <class T> bool QList<T>::iterator::operator<=(const const_iterator& other) const
1645
1646 Returns \c true if the item pointed to by this iterator is less than
1647 or equal to the item pointed to by the \a other iterator.
1648*/
1649
1650/*!
1651 \fn template <class T> bool QList<T>::iterator::operator>(const iterator& other) const
1652 \fn template <class T> bool QList<T>::iterator::operator>(const const_iterator& other) const
1653
1654 Returns \c true if the item pointed to by this iterator is greater
1655 than the item pointed to by the \a other iterator.
1656*/
1657
1658/*!
1659 \fn template <class T> bool QList<T>::iterator::operator>=(const iterator& other) const
1660 \fn template <class T> bool QList<T>::iterator::operator>=(const const_iterator& other) const
1661
1662 Returns \c true if the item pointed to by this iterator is greater
1663 than or equal to the item pointed to by the \a other iterator.
1664*/
1665
1666/*! \fn template <class T> QList<T>::iterator &QList<T>::iterator::operator++()
1667
1668 The prefix ++ operator (\c{++it}) advances the iterator to the
1669 next item in the list and returns an iterator to the new current
1670 item.
1671
1672 Calling this function on QList::end() leads to undefined results.
1673
1674 \sa operator--()
1675*/
1676
1677/*! \fn template <class T> QList<T>::iterator QList<T>::iterator::operator++(int)
1678
1679 \overload
1680
1681 The postfix ++ operator (\c{it++}) advances the iterator to the
1682 next item in the list and returns an iterator to the previously
1683 current item.
1684*/
1685
1686/*! \fn template <class T> QList<T>::iterator &QList<T>::iterator::operator--()
1687
1688 The prefix -- operator (\c{--it}) makes the preceding item
1689 current and returns an iterator to the new current item.
1690
1691 Calling this function on QList::begin() leads to undefined results.
1692
1693 \sa operator++()
1694*/
1695
1696/*! \fn template <class T> QList<T>::iterator QList<T>::iterator::operator--(int)
1697
1698 \overload
1699
1700 The postfix -- operator (\c{it--}) makes the preceding item
1701 current and returns an iterator to the previously current item.
1702*/
1703
1704/*! \fn template <class T> QList<T>::iterator &QList<T>::iterator::operator+=(difference_type j)
1705
1706 Advances the iterator by \a j items. (If \a j is negative, the
1707 iterator goes backward.)
1708
1709 \sa operator-=(), operator+()
1710*/
1711
1712/*! \fn template <class T> QList<T>::iterator &QList<T>::iterator::operator-=(difference_type j)
1713
1714 Makes the iterator go back by \a j items. (If \a j is negative,
1715 the iterator goes forward.)
1716
1717 \sa operator+=(), operator-()
1718*/
1719
1720/*! \fn template <class T> QList<T>::iterator QList<T>::iterator::operator+(difference_type j) const
1721
1722 Returns an iterator to the item at \a j positions forward from
1723 this iterator. (If \a j is negative, the iterator goes backward.)
1724
1725 \sa operator-(), operator+=()
1726*/
1727
1728/*! \fn template <class T> QList<T>::iterator QList<T>::iterator::operator-(difference_type j) const
1729
1730 Returns an iterator to the item at \a j positions backward from
1731 this iterator. (If \a j is negative, the iterator goes forward.)
1732
1733 \sa operator+(), operator-=()
1734*/
1735
1736/*! \fn template <class T> int QList<T>::iterator::operator-(iterator other) const
1737
1738 Returns the number of items between the item pointed to by \a
1739 other and the item pointed to by this iterator.
1740*/
1741
1742/*! \class QList::const_iterator
1743 \inmodule QtCore
1744 \brief The QList::const_iterator class provides an STL-style const iterator for QList and QQueue.
1745
1746 QList provides both \l{STL-style iterators} and \l{Java-style
1747 iterators}. The STL-style iterators are more low-level and more
1748 cumbersome to use; on the other hand, they are slightly faster
1749 and, for developers who already know STL, have the advantage of
1750 familiarity.
1751
1752 QList\<T\>::const_iterator allows you to iterate over a
1753 QList\<T\> (or a QQueue\<T\>). If you want to modify the QList as
1754 you iterate over it, use QList::iterator instead. It is generally
1755 good practice to use QList::const_iterator on a non-const QList
1756 as well, unless you need to change the QList through the
1757 iterator. Const iterators are slightly faster, and can improve
1758 code readability.
1759
1760 The default QList::const_iterator constructor creates an
1761 uninitialized iterator. You must initialize it using a QList
1762 function like QList::constBegin(), QList::constEnd(), or
1763 QList::insert() before you can start iterating. Here's a typical
1764 loop that prints all the items stored in a list:
1765
1766 \snippet code/src_corelib_tools_qlistdata.cpp 19
1767
1768 Most QList functions accept an integer index rather than an
1769 iterator. For that reason, iterators are rarely useful in
1770 connection with QList. One place where STL-style iterators do
1771 make sense is as arguments to \l{generic algorithms}.
1772
1773 For example, here's how to delete all the widgets stored in a
1774 QList\<QWidget *\>:
1775
1776 \snippet code/src_corelib_tools_qlistdata.cpp 20
1777
1778 Multiple iterators can be used on the same list. However, be
1779 aware that any non-const function call performed on the QList
1780 will render all existing iterators undefined. If you need to keep
1781 iterators over a long period of time, we recommend that you use
1782 QLinkedList rather than QList.
1783
1784 \warning Iterators on implicitly shared containers do not work
1785 exactly like STL-iterators. You should avoid copying a container
1786 while iterators are active on that container. For more information,
1787 read \l{Implicit sharing iterator problem}.
1788
1789 \sa QList::iterator, QListIterator
1790*/
1791
1792/*! \fn template <class T> QList<T>::const_iterator::const_iterator()
1793
1794 Constructs an uninitialized iterator.
1795
1796 Functions like operator*() and operator++() should not be called
1797 on an uninitialized iterator. Use operator=() to assign a value
1798 to it before using it.
1799
1800 \sa QList::constBegin(), QList::constEnd()
1801*/
1802
1803/*! \typedef QList::const_iterator::iterator_category
1804
1805 A synonym for \e {std::random_access_iterator_tag} indicating
1806 this iterator is a random access iterator.
1807*/
1808
1809/*! \typedef QList::const_iterator::difference_type
1810
1811 \internal
1812*/
1813
1814/*! \typedef QList::const_iterator::value_type
1815
1816 \internal
1817*/
1818
1819/*! \typedef QList::const_iterator::pointer
1820
1821 \internal
1822*/
1823
1824/*! \typedef QList::const_iterator::reference
1825
1826 \internal
1827*/
1828
1829/*! \fn template <class T> QList<T>::const_iterator::const_iterator(Node *node)
1830
1831 \internal
1832*/
1833
1834/*! \fn template <class T> QList<T>::const_iterator::const_iterator(const const_iterator &other)
1835
1836 Constructs a copy of \a other.
1837*/
1838
1839/*! \fn template <class T> QList<T>::const_iterator::const_iterator(const iterator &other)
1840
1841 Constructs a copy of \a other.
1842*/
1843
1844/*! \fn template <class T> const T &QList<T>::const_iterator::operator*() const
1845
1846 Returns the current item.
1847
1848 \sa operator->()
1849*/
1850
1851/*! \fn template <class T> const T *QList<T>::const_iterator::operator->() const
1852
1853 Returns a pointer to the current item.
1854
1855 \sa operator*()
1856*/
1857
1858/*! \fn template <class T> const T &QList<T>::const_iterator::operator[](difference_type j) const
1859
1860 Returns the item at position *this + \a{j}.
1861
1862 This function is provided to make QList iterators behave like C++
1863 pointers.
1864
1865 \sa operator+()
1866*/
1867
1868/*! \fn template <class T> bool QList<T>::const_iterator::operator==(const const_iterator &other) const
1869
1870 Returns \c true if \a other points to the same item as this
1871 iterator; otherwise returns \c false.
1872
1873 \sa operator!=()
1874*/
1875
1876/*! \fn template <class T> bool QList<T>::const_iterator::operator!=(const const_iterator &other) const
1877
1878 Returns \c true if \a other points to a different item than this
1879 iterator; otherwise returns \c false.
1880
1881 \sa operator==()
1882*/
1883
1884/*!
1885 \fn template <class T> bool QList<T>::const_iterator::operator<(const const_iterator& other) const
1886
1887 Returns \c true if the item pointed to by this iterator is less than
1888 the item pointed to by the \a other iterator.
1889*/
1890
1891/*!
1892 \fn template <class T> bool QList<T>::const_iterator::operator<=(const const_iterator& other) const
1893
1894 Returns \c true if the item pointed to by this iterator is less than
1895 or equal to the item pointed to by the \a other iterator.
1896*/
1897
1898/*!
1899 \fn template <class T> bool QList<T>::const_iterator::operator>(const const_iterator& other) const
1900
1901 Returns \c true if the item pointed to by this iterator is greater
1902 than the item pointed to by the \a other iterator.
1903*/
1904
1905/*!
1906 \fn template <class T> bool QList<T>::const_iterator::operator>=(const const_iterator& other) const
1907
1908 Returns \c true if the item pointed to by this iterator is greater
1909 than or equal to the item pointed to by the \a other iterator.
1910*/
1911
1912/*! \fn template <class T> QList<T>::const_iterator &QList<T>::const_iterator::operator++()
1913
1914 The prefix ++ operator (\c{++it}) advances the iterator to the
1915 next item in the list and returns an iterator to the new current
1916 item.
1917
1918 Calling this function on QList::end() leads to undefined results.
1919
1920 \sa operator--()
1921*/
1922
1923/*! \fn template <class T> QList<T>::const_iterator QList<T>::const_iterator::operator++(int)
1924
1925 \overload
1926
1927 The postfix ++ operator (\c{it++}) advances the iterator to the
1928 next item in the list and returns an iterator to the previously
1929 current item.
1930*/
1931
1932/*! \fn template <class T> QList<T>::const_iterator &QList<T>::const_iterator::operator--()
1933
1934 The prefix -- operator (\c{--it}) makes the preceding item
1935 current and returns an iterator to the new current item.
1936
1937 Calling this function on QList::begin() leads to undefined results.
1938
1939 \sa operator++()
1940*/
1941
1942/*! \fn template <class T> QList<T>::const_iterator QList<T>::const_iterator::operator--(int)
1943
1944 \overload
1945
1946 The postfix -- operator (\c{it--}) makes the preceding item
1947 current and returns an iterator to the previously current item.
1948*/
1949
1950/*! \fn template <class T> QList<T>::const_iterator &QList<T>::const_iterator::operator+=(difference_type j)
1951
1952 Advances the iterator by \a j items. (If \a j is negative, the
1953 iterator goes backward.)
1954
1955 \sa operator-=(), operator+()
1956*/
1957
1958/*! \fn template <class T> QList<T>::const_iterator &QList<T>::const_iterator::operator-=(difference_type j)
1959
1960 Makes the iterator go back by \a j items. (If \a j is negative,
1961 the iterator goes forward.)
1962
1963 \sa operator+=(), operator-()
1964*/
1965
1966/*! \fn template <class T> QList<T>::const_iterator QList<T>::const_iterator::operator+(difference_type j) const
1967
1968 Returns an iterator to the item at \a j positions forward from
1969 this iterator. (If \a j is negative, the iterator goes backward.)
1970
1971 \sa operator-(), operator+=()
1972*/
1973
1974/*! \fn template <class T> QList<T>::const_iterator QList<T>::const_iterator::operator-(difference_type j) const
1975
1976 Returns an iterator to the item at \a j positions backward from
1977 this iterator. (If \a j is negative, the iterator goes forward.)
1978
1979 \sa operator+(), operator-=()
1980*/
1981
1982/*! \fn template <class T> int QList<T>::const_iterator::operator-(const_iterator other) const
1983
1984 Returns the number of items between the item pointed to by \a
1985 other and the item pointed to by this iterator.
1986*/
1987
1988/*! \fn template <class T> QDataStream &operator<<(QDataStream &out, const QList<T> &list)
1989 \relates QList
1990
1991 Writes the list \a list to stream \a out.
1992
1993 This function requires the value type to implement \c
1994 operator<<().
1995
1996 \sa{Serializing Qt Data Types}{Format of the QDataStream operators}
1997*/
1998
1999/*! \fn template <class T> QDataStream &operator>>(QDataStream &in, QList<T> &list)
2000 \relates QList
2001
2002 Reads a list from stream \a in into \a list.
2003
2004 This function requires the value type to implement \c
2005 operator>>().
2006
2007 \sa{Serializing Qt Data Types}{Format of the QDataStream operators}
2008*/
2009
2010/*! \fn template <class T> QList<T> QList<T>::fromVector(const QVector<T> &vector)
2011
2012 Returns a QList object with the data contained in \a vector.
2013
2014 Example:
2015
2016 \snippet code/src_corelib_tools_qlistdata.cpp 21
2017
2018 \include containers-range-constructor.qdocinc
2019
2020 \sa toVector(), QVector::toList()
2021*/
2022
2023/*! \fn template <class T> QVector<T> QList<T>::toVector() const
2024
2025 Returns a QVector object with the data contained in this QList.
2026
2027 Example:
2028
2029 \snippet code/src_corelib_tools_qlistdata.cpp 22
2030
2031 \include containers-range-constructor.qdocinc
2032
2033 \sa fromVector(), QVector::fromList()
2034*/
2035
2036/*! \fn template <class T> QList<T> QList<T>::fromSet(const QSet<T> &set)
2037 \obsolete
2038
2039 Returns a QList object with the data contained in \a set. The
2040 order of the elements in the QList is undefined.
2041
2042 \include containers-range-constructor.qdocinc
2043
2044 \oldcode
2045 QSet<int> set;
2046 // ...
2047 QList<int> list = QList<int>::fromSet(set);
2048 \newcode
2049 QSet<int> set;
2050 // ...
2051 QList<int> list(set.begin(), set.end());
2052 \endcode
2053
2054 \sa QList(InputIterator, InputIterator), fromVector(), toSet(), QSet::toList()
2055*/
2056
2057/*! \fn template <class T> QSet<T> QList<T>::toSet() const
2058 \obsolete
2059
2060 Returns a QSet object with the data contained in this QList.
2061 Since QSet doesn't allow duplicates, the resulting QSet might be
2062 smaller than the original list was.
2063
2064 \include containers-range-constructor.qdocinc
2065
2066 \oldcode
2067 QStringList list;
2068 // ...
2069 QSet<QString> set = list.toSet();
2070 \newcode
2071 QStringList list;
2072 // ...
2073 QSet<QString> set(list.begin(), list.end());
2074 \endcode
2075
2076 \sa QSet::QSet(InputIterator, InputIterator), toVector(), fromSet(), QSet::fromList()
2077*/
2078
2079/*! \fn template <class T> QList<T> QList<T>::fromStdList(const std::list<T> &list)
2080 \obsolete
2081
2082 Returns a QList object with the data contained in \a list. The
2083 order of the elements in the QList is the same as in \a list.
2084
2085 \include containers-range-constructor.qdocinc
2086
2087 \oldcode
2088 std::list<double> stdlist;
2089 // ...
2090 QList<double> list = QList<double>::fromStdList(stdlist);
2091 \newcode
2092 std::list<double> stdlist;
2093 // ...
2094 QList<double> list(stdlist.begin(), stdlist.end());
2095 \endcode
2096
2097 \sa QList(InputIterator, InputIterator), toStdList(), QVector::fromStdVector()
2098*/
2099
2100/*! \fn template <class T> std::list<T> QList<T>::toStdList() const
2101 \obsolete
2102
2103 Returns a std::list object with the data contained in this QList.
2104 Example:
2105
2106 \include containers-range-constructor.qdocinc
2107
2108 \oldcode
2109 QList<double> list;
2110 // ...
2111 std::list<double> stdlist = list.toStdList();
2112 \newcode
2113 QList<double> list;
2114 // ...
2115 std::list<double> stdlist(list.begin(), list.end());
2116 \endcode
2117
2118 \sa fromStdList(), QVector::toStdVector()
2119*/
2120
2121QT_END_NAMESPACE
2122

source code of qtbase/src/corelib/tools/qlist.cpp