1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtCore module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39
40#ifdef QT_NO_LINKED_LIST
41# undef QT_NO_LINKED_LIST
42#endif
43
44#include "qlinkedlist.h"
45
46QT_BEGIN_NAMESPACE
47
48const QLinkedListData QLinkedListData::shared_null = {
49 const_cast<QLinkedListData *>(&QLinkedListData::shared_null),
50 const_cast<QLinkedListData *>(&QLinkedListData::shared_null),
51 Q_REFCOUNT_INITIALIZE_STATIC, 0, true
52};
53
54/*! \class QLinkedList
55 \inmodule QtCore
56 \brief The QLinkedList class is a template class that provides linked lists.
57
58 \ingroup tools
59 \ingroup shared
60
61 \reentrant
62
63 QLinkedList\<T\> is one of Qt's generic \l{container classes}. It
64 stores a list of values and provides iterator-based access as
65 well as \l{constant time} insertions and removals.
66
67 QList\<T\>, QLinkedList\<T\>, and QVector\<T\> provide similar
68 functionality. Here's an overview:
69
70 \list
71 \li For most purposes, QList is the right class to use. Its
72 index-based API is more convenient than QLinkedList's
73 iterator-based API, and it is usually faster than
74 QVector because of the way it stores its items in
75 memory (see \l{Algorithmic Complexity} for details).
76 It also expands to less code in your executable.
77 \li If you need a real linked list, with guarantees of \l{constant
78 time} insertions in the middle of the list and iterators to
79 items rather than indexes, use QLinkedList.
80 \li If you want the items to occupy adjacent memory positions,
81 use QVector.
82 \endlist
83
84 Here's an example of a QLinkedList that stores integers and a
85 QLinkedList that stores QTime values:
86
87 \snippet code/src_corelib_tools_qlinkedlist.cpp 0
88
89 QLinkedList stores a list of items. The default constructor
90 creates an empty list. To insert items into the list, you can use
91 operator<<():
92
93 \snippet code/src_corelib_tools_qlinkedlist.cpp 1
94
95 If you want to get the first or last item in a linked list, use
96 first() or last(). If you want to remove an item from either end
97 of the list, use removeFirst() or removeLast(). If you want to
98 remove all occurrences of a given value in the list, use
99 removeAll().
100
101 A common requirement is to remove the first or last item in the
102 list and do something with it. For this, QLinkedList provides
103 takeFirst() and takeLast(). Here's a loop that removes the items
104 from a list one at a time and calls \c delete on them:
105 \snippet code/src_corelib_tools_qlinkedlist.cpp 2
106
107 QLinkedList's value type must be an \l {assignable data type}. This
108 covers most data types that are commonly used, but the compiler
109 won't let you, for example, store a QWidget as a value; instead,
110 store a QWidget *. A few functions have additional requirements;
111 for example, contains() and removeAll() expect the value type to
112 support \c operator==(). These requirements are documented on a
113 per-function basis.
114
115 If you want to insert, modify, or remove items in the middle of
116 the list, you must use an iterator. QLinkedList provides both
117 \l{Java-style iterators} (QLinkedListIterator and
118 QMutableLinkedListIterator) and \l{STL-style iterators}
119 (QLinkedList::const_iterator and QLinkedList::iterator). See the
120 documentation for these classes for details.
121
122 \sa QLinkedListIterator, QMutableLinkedListIterator, QList, QVector
123*/
124
125/*! \fn template <class T> QLinkedList<T>::QLinkedList()
126
127 Constructs an empty list.
128*/
129
130/*!
131 \fn template <class T> QLinkedList<T>::QLinkedList(QLinkedList<T> &&other)
132
133 Move-constructs a QLinkedList instance, making it point at the same
134 object that \a other was pointing to.
135
136 \since 5.2
137*/
138
139/*! \fn template <class T> QLinkedList<T>::QLinkedList(const QLinkedList<T> &other)
140
141 Constructs a copy of \a other.
142
143 This operation occurs in \l{constant time}, because QLinkedList
144 is \l{implicitly shared}. This makes returning a QLinkedList from
145 a function very fast. If a shared instance is modified, it will
146 be copied (copy-on-write), and this takes \l{linear time}.
147
148 \sa operator=()
149*/
150
151/*! \fn template <class T> QLinkedList<T>::QLinkedList(std::initializer_list<T> list)
152 \since 5.2
153
154 Constructs a list from the std::initializer_list specified by \a list.
155
156 This constructor is only enabled if the compiler supports C++11
157 initializer lists.
158*/
159
160/*! \fn template <class T> template<typename InputIterator> QLinkedList<T>::QLinkedList(InputIterator first, InputIterator last)
161 \since 5.14
162
163 Constructs a list with the contents in the iterator range [\a first, \a last).
164
165 The value type of \c InputIterator must be convertible to \c T.
166*/
167
168/*! \fn template <class T> QLinkedList<T>::~QLinkedList()
169
170 Destroys the list. References to the values in the list, and all
171 iterators over this list, become invalid.
172*/
173
174/*! \fn template <class T> QLinkedList<T> &QLinkedList<T>::operator=(const QLinkedList<T> &other)
175
176 Assigns \a other to this list and returns a reference to this
177 list.
178*/
179
180/*! \fn template <class T> void QLinkedList<T>::swap(QLinkedList<T> &other)
181 \since 4.8
182
183 Swaps list \a other with this list. This operation is very
184 fast and never fails.
185*/
186
187/*! \fn template <class T> bool QLinkedList<T>::operator==(const QLinkedList<T> &other) const
188
189 Returns \c true if \a other is equal to this list; otherwise returns
190 false.
191
192 Two lists are considered equal if they contain the same values in
193 the same order.
194
195 This function requires the value type to implement \c
196 operator==().
197
198 \sa operator!=()
199*/
200
201/*! \fn template <class T> bool QLinkedList<T>::operator!=(const QLinkedList<T> &other) const
202
203 Returns \c true if \a other is not equal to this list; otherwise
204 returns \c false.
205
206 Two lists are considered equal if they contain the same values in
207 the same order.
208
209 This function requires the value type to implement \c
210 operator==().
211
212 \sa operator==()
213*/
214
215/*! \fn template <class T> int QLinkedList<T>::size() const
216
217 Returns the number of items in the list.
218
219 \sa isEmpty(), count()
220*/
221
222/*! \fn template <class T> void QLinkedList<T>::detach()
223
224 \internal
225*/
226
227/*! \fn template <class T> bool QLinkedList<T>::isDetached() const
228
229 \internal
230*/
231
232/*! \fn template <class T> void QLinkedList<T>::setSharable(bool sharable)
233
234 \internal
235*/
236
237/*! \fn template <class T> bool QLinkedList<T>::isSharedWith(const QLinkedList<T> &other) const
238
239 \internal
240*/
241
242/*! \fn template <class T> bool QLinkedList<T>::isEmpty() const
243
244 Returns \c true if the list contains no items; otherwise returns
245 false.
246
247 \sa size()
248*/
249
250/*! \fn template <class T> void QLinkedList<T>::clear()
251
252 Removes all the items in the list.
253
254 \sa removeAll()
255*/
256
257/*! \fn template <class T> void QLinkedList<T>::append(const T &value)
258
259 Inserts \a value at the end of the list.
260
261 Example:
262 \snippet code/src_corelib_tools_qlinkedlist.cpp 3
263
264 This is the same as list.insert(end(), \a value).
265
266 \sa operator<<(), prepend(), insert()
267*/
268
269/*! \fn template <class T> void QLinkedList<T>::prepend(const T &value)
270
271 Inserts \a value at the beginning of the list.
272
273 Example:
274 \snippet code/src_corelib_tools_qlinkedlist.cpp 4
275
276 This is the same as list.insert(begin(), \a value).
277
278 \sa append(), insert()
279*/
280
281/*! \fn template <class T> int QLinkedList<T>::removeAll(const T &value)
282
283 Removes all occurrences of \a value in the list.
284
285 Example:
286 \snippet code/src_corelib_tools_qlinkedlist.cpp 5
287
288 This function requires the value type to have an implementation of
289 \c operator==().
290
291 \sa insert()
292*/
293
294/*!
295 \fn template <class T> bool QLinkedList<T>::removeOne(const T &value)
296 \since 4.4
297
298 Removes the first occurrences of \a value in the list. Returns \c true on
299 success; otherwise returns \c false.
300
301 Example:
302 \snippet code/src_corelib_tools_qlinkedlist.cpp 6
303
304 This function requires the value type to have an implementation of
305 \c operator==().
306
307 \sa insert()
308*/
309
310/*! \fn template <class T> bool QLinkedList<T>::contains(const T &value) const
311
312 Returns \c true if the list contains an occurrence of \a value;
313 otherwise returns \c false.
314
315 This function requires the value type to have an implementation of
316 \c operator==().
317
318 \sa QLinkedListIterator::findNext(), QLinkedListIterator::findPrevious()
319*/
320
321/*! \fn template <class T> int QLinkedList<T>::count(const T &value) const
322
323 Returns the number of occurrences of \a value in the list.
324
325 This function requires the value type to have an implementation of
326 \c operator==().
327
328 \sa contains()
329*/
330
331/*! \fn template <class T> bool QLinkedList<T>::startsWith(const T &value) const
332 \since 4.5
333
334 Returns \c true if the list is not empty and its first
335 item is equal to \a value; otherwise returns \c false.
336
337 \sa isEmpty(), first()
338*/
339
340/*! \fn template <class T> bool QLinkedList<T>::endsWith(const T &value) const
341 \since 4.5
342
343 Returns \c true if the list is not empty and its last
344 item is equal to \a value; otherwise returns \c false.
345
346 \sa isEmpty(), last()
347*/
348
349/*! \fn template <class T> QLinkedList<T>::iterator QLinkedList<T>::begin()
350
351 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the first item in
352 the list.
353
354 \sa constBegin(), end()
355*/
356
357/*! \fn template <class T> QLinkedList<T>::const_iterator QLinkedList<T>::begin() const
358
359 \overload
360*/
361
362/*! \fn template <class T> QLinkedList<T>::const_iterator QLinkedList<T>::cbegin() const
363 \since 5.0
364
365 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
366 in the list.
367
368 \sa begin(), cend()
369*/
370
371/*! \fn template <class T> QLinkedList<T>::const_iterator QLinkedList<T>::constBegin() const
372
373 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the first item
374 in the list.
375
376 \sa begin(), constEnd()
377*/
378
379/*! \fn template <class T> QLinkedList<T>::iterator QLinkedList<T>::end()
380
381 Returns an \l{STL-style iterators}{STL-style iterator} pointing to the imaginary item
382 after the last item in the list.
383
384 \sa begin(), constEnd()
385*/
386
387/*! \fn template <class T> QLinkedList<T>::const_iterator QLinkedList<T>::end() const
388
389 \overload
390*/
391
392/*! \fn template <class T> QLinkedList<T>::const_iterator QLinkedList<T>::cend() const
393 \since 5.0
394
395 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
396 item after the last item in the list.
397
398 \sa cbegin(), end()
399*/
400
401/*! \fn template <class T> QLinkedList<T>::const_iterator QLinkedList<T>::constEnd() const
402
403 Returns a const \l{STL-style iterators}{STL-style iterator} pointing to the imaginary
404 item after the last item in the list.
405
406 \sa constBegin(), end()
407*/
408
409/*! \fn template <class T> QLinkedList<T>::reverse_iterator QLinkedList<T>::rbegin()
410 \since 5.6
411
412 Returns a \l{STL-style iterators}{STL-style} reverse iterator pointing to the first
413 item in the list, in reverse order.
414
415 \sa begin(), crbegin(), rend()
416*/
417
418/*! \fn template <class T> QLinkedList<T>::const_reverse_iterator QLinkedList<T>::rbegin() const
419 \since 5.6
420 \overload
421*/
422
423/*! \fn template <class T> QLinkedList<T>::const_reverse_iterator QLinkedList<T>::crbegin() const
424 \since 5.6
425
426 Returns a const \l{STL-style iterators}{STL-style} reverse iterator pointing to the first
427 item in the list, in reverse order.
428
429 \sa begin(), rbegin(), rend()
430*/
431
432/*! \fn template <class T> QLinkedList<T>::reverse_iterator QLinkedList<T>::rend()
433 \since 5.6
434
435 Returns a \l{STL-style iterators}{STL-style} reverse iterator pointing to one past
436 the last item in the list, in reverse order.
437
438 \sa end(), crend(), rbegin()
439*/
440
441/*! \fn template <class T> QLinkedList<T>::const_reverse_iterator QLinkedList<T>::rend() const
442 \since 5.6
443 \overload
444*/
445
446/*! \fn template <class T> QLinkedList<T>::const_reverse_iterator QLinkedList<T>::crend() const
447 \since 5.6
448
449 Returns a const \l{STL-style iterators}{STL-style} reverse iterator pointing to one
450 past the last item in the list, in reverse order.
451
452 \sa end(), rend(), rbegin()
453*/
454
455/*! \fn template <class T> QLinkedList<T>::iterator QLinkedList<T>::insert(iterator before, const T &value)
456
457 Inserts \a value in front of the item pointed to by the iterator
458 \a before. Returns an iterator pointing at the inserted item.
459
460 \sa erase()
461*/
462
463/*! \fn template <class T> QLinkedList<T>::iterator QLinkedList<T>::erase(iterator pos)
464
465 Removes the item pointed to by the iterator \a pos from the list,
466 and returns an iterator to the next item in the list (which may be
467 end()).
468
469 \sa insert()
470*/
471
472/*! \fn template <class T> QLinkedList<T>::iterator QLinkedList<T>::erase(iterator begin, iterator end)
473
474 \overload
475
476 Removes all the items from \a begin up to (but not including) \a
477 end.
478*/
479
480/*! \typedef QLinkedList::Iterator
481
482 Qt-style synonym for QLinkedList::iterator.
483*/
484
485/*! \typedef QLinkedList::ConstIterator
486
487 Qt-style synonym for QLinkedList::const_iterator.
488*/
489
490/*! \typedef QLinkedList::reverse_iterator
491 \since 5.6
492
493 The QLinkedList::reverse_iterator typedef provides an STL-style non-const
494 reverse iterator for QLinkedList.
495
496 It is simply a typedef for \c{std::reverse_iterator<QLinkedList::iterator>}.
497
498 \warning Iterators on implicitly shared containers do not work
499 exactly like STL-iterators. You should avoid copying a container
500 while iterators are active on that container. For more information,
501 read \l{Implicit sharing iterator problem}.
502
503 \sa QLinkedList::rbegin(), QLinkedList::rend(), QLinkedList::const_reverse_iterator, QLinkedList::iterator
504*/
505
506/*! \typedef QLinkedList::const_reverse_iterator
507 \since 5.6
508
509 The QLinkedList::const_reverse_iterator typedef provides an STL-style const
510 reverse iterator for QLinkedList.
511
512 It is simply a typedef for \c{std::reverse_iterator<QLinkedList::const_iterator>}.
513
514 \warning Iterators on implicitly shared containers do not work
515 exactly like STL-iterators. You should avoid copying a container
516 while iterators are active on that container. For more information,
517 read \l{Implicit sharing iterator problem}.
518
519 \sa QLinkedList::rbegin(), QLinkedList::rend(), QLinkedList::reverse_iterator, QLinkedList::const_iterator
520*/
521
522/*!
523 \typedef QLinkedList::size_type
524
525 Typedef for int. Provided for STL compatibility.
526*/
527
528/*!
529 \typedef QLinkedList::value_type
530
531 Typedef for T. Provided for STL compatibility.
532*/
533
534/*!
535 \typedef QLinkedList::pointer
536
537 Typedef for T *. Provided for STL compatibility.
538*/
539
540/*!
541 \typedef QLinkedList::const_pointer
542
543 Typedef for const T *. Provided for STL compatibility.
544*/
545
546/*!
547 \typedef QLinkedList::reference
548
549 Typedef for T &. Provided for STL compatibility.
550*/
551
552/*!
553 \typedef QLinkedList::const_reference
554
555 Typedef for const T &. Provided for STL compatibility.
556*/
557
558/*!
559 \typedef QLinkedList::difference_type
560
561 Typedef for ptrdiff_t. Provided for STL compatibility.
562*/
563
564/*! \fn template <class T> int QLinkedList<T>::count() const
565
566 Same as size().
567*/
568
569/*! \fn template <class T> T& QLinkedList<T>::first()
570
571 Returns a reference to the first item in the list. This function
572 assumes that the list isn't empty.
573
574 \sa last(), isEmpty()
575*/
576
577/*! \fn template <class T> const T& QLinkedList<T>::first() const
578
579 \overload
580*/
581
582/*! \fn template <class T> T& QLinkedList<T>::last()
583
584 Returns a reference to the last item in the list. This function
585 assumes that the list isn't empty.
586
587 \sa first(), isEmpty()
588*/
589
590/*! \fn template <class T> const T& QLinkedList<T>::last() const
591
592 \overload
593*/
594
595/*! \fn template <class T> void QLinkedList<T>::removeFirst()
596
597 Removes the first item in the list.
598
599 This is the same as erase(begin()).
600
601 \sa removeLast(), erase()
602*/
603
604/*! \fn template <class T> void QLinkedList<T>::removeLast()
605
606 Removes the last item in the list.
607
608 \sa removeFirst(), erase()
609*/
610
611/*! \fn template <class T> T QLinkedList<T>::takeFirst()
612
613 Removes the first item in the list and returns it.
614
615 If you don't use the return value, removeFirst() is more
616 efficient.
617
618 \sa takeLast(), removeFirst()
619*/
620
621/*! \fn template <class T> T QLinkedList<T>::takeLast()
622
623 Removes the last item in the list and returns it.
624
625 If you don't use the return value, removeLast() is more
626 efficient.
627
628 \sa takeFirst(), removeLast()
629*/
630
631/*! \fn template <class T> void QLinkedList<T>::push_back(const T &value)
632
633 This function is provided for STL compatibility. It is equivalent
634 to append(\a value).
635*/
636
637/*! \fn template <class T> void QLinkedList<T>::push_front(const T &value)
638
639 This function is provided for STL compatibility. It is equivalent
640 to prepend(\a value).
641*/
642
643/*! \fn template <class T> T& QLinkedList<T>::front()
644
645 This function is provided for STL compatibility. It is equivalent
646 to first().
647*/
648
649/*! \fn template <class T> const T& QLinkedList<T>::front() const
650
651 \overload
652*/
653
654/*! \fn template <class T> T& QLinkedList<T>::back()
655
656 This function is provided for STL compatibility. It is equivalent
657 to last().
658*/
659
660/*! \fn template <class T> const T& QLinkedList<T>::back() const
661
662 \overload
663*/
664
665/*! \fn template <class T> void QLinkedList<T>::pop_front()
666
667 This function is provided for STL compatibility. It is equivalent
668 to removeFirst().
669*/
670
671/*! \fn template <class T> void QLinkedList<T>::pop_back()
672
673 This function is provided for STL compatibility. It is equivalent
674 to removeLast().
675*/
676
677/*! \fn template <class T> bool QLinkedList<T>::empty() const
678
679 This function is provided for STL compatibility. It is equivalent
680 to isEmpty() and returns \c true if the list is empty.
681*/
682
683/*! \fn template <class T> QLinkedList<T> &QLinkedList<T>::operator+=(const QLinkedList<T> &other)
684
685 Appends the items of the \a other list to this list and returns a
686 reference to this list.
687
688 \sa operator+(), append()
689*/
690
691/*! \fn template <class T> void QLinkedList<T>::operator+=(const T &value)
692
693 \overload
694
695 Appends \a value to the list.
696*/
697
698/*! \fn template <class T> QLinkedList<T> QLinkedList<T>::operator+(const QLinkedList<T> &other) const
699
700 Returns a list that contains all the items in this list followed
701 by all the items in the \a other list.
702
703 \sa operator+=()
704*/
705
706/*! \fn template <class T> QLinkedList<T> &QLinkedList<T>::operator<<(const QLinkedList<T> &other)
707
708 Appends the items of the \a other list to this list and returns a
709 reference to this list.
710
711 \sa operator+=(), append()
712*/
713
714/*! \fn template <class T> QLinkedList<T> &QLinkedList<T>::operator<<(const T &value)
715
716 \overload
717
718 Appends \a value to the list.
719*/
720
721/*! \class QLinkedList::iterator
722 \inmodule QtCore
723 \brief The QLinkedList::iterator class provides an STL-style non-const iterator for QLinkedList.
724
725 QLinkedList features both \l{STL-style iterators} and
726 \l{Java-style iterators}. The STL-style iterators are more
727 low-level and more cumbersome to use; on the other hand, they are
728 slightly faster and, for developers who already know STL, have
729 the advantage of familiarity.
730
731 QLinkedList\<T\>::iterator allows you to iterate over a
732 QLinkedList\<T\> and to modify the list item associated with the
733 iterator. If you want to iterate over a const QLinkedList, use
734 QLinkedList::const_iterator instead. It is generally good
735 practice to use QLinkedList::const_iterator on a non-const
736 QLinkedList as well, unless you need to change the QLinkedList
737 through the iterator. Const iterators are slightly faster, and
738 can improve code readability.
739
740 The default QLinkedList::iterator constructor creates an
741 uninitialized iterator. You must initialize it using a
742 function like QLinkedList::begin(), QLinkedList::end(), or
743 QLinkedList::insert() before you can start iterating. Here's a
744 typical loop that prints all the items stored in a list:
745
746 \snippet code/src_corelib_tools_qlinkedlist.cpp 7
747
748 STL-style iterators can be used as arguments to \l{generic
749 algorithms}. For example, here's how to find an item in the list:
750
751 \snippet code/src_corelib_tools_qlinkedlist.cpp 8
752
753 Let's see a few examples of things we can do with a
754 QLinkedList::iterator that we cannot do with a QLinkedList::const_iterator.
755 Here's an example that increments every value stored in a
756 QLinkedList\<int\> by 2:
757
758 \snippet code/src_corelib_tools_qlinkedlist.cpp 9
759
760 Here's an example that removes all the items that start with an
761 underscore character in a QLinkedList\<QString\>:
762
763 \snippet code/src_corelib_tools_qlinkedlist.cpp 10
764
765 The call to QLinkedList::erase() removes the item pointed to by
766 the iterator from the list, and returns an iterator to the next
767 item. Here's another way of removing an item while iterating:
768
769 \snippet code/src_corelib_tools_qlinkedlist.cpp 11
770
771 It might be tempting to write code like this:
772
773 \snippet code/src_corelib_tools_qlinkedlist.cpp 12
774
775 However, this will potentially crash in \c{++i}, because \c i is
776 a dangling iterator after the call to erase().
777
778 Multiple iterators can be used on the same list. If you add items
779 to the list, existing iterators will remain valid. If you remove
780 items from the list, iterators that point to the removed items
781 will become dangling iterators.
782
783 \warning Iterators on implicitly shared containers do not work
784 exactly like STL-iterators. You should avoid copying a container
785 while iterators are active on that container. For more information,
786 read \l{Implicit sharing iterator problem}.
787
788 \sa QLinkedList::const_iterator, QMutableLinkedListIterator
789*/
790
791/*! \fn template <class T> QLinkedList<T>::iterator::iterator()
792
793 Constructs an uninitialized iterator.
794
795 Functions like operator*() and operator++() should not be called
796 on an uninitialized iterator. Use operator=() to assign a value
797 to it before using it.
798
799 \sa QLinkedList::begin(), QLinkedList::end()
800*/
801
802/*! \fn template <class T> QLinkedList<T>::iterator::iterator(Node *node)
803
804 \internal
805*/
806
807/*! \typedef QLinkedList::iterator::iterator_category
808
809 \internal
810*/
811
812/*! \typedef QLinkedList::iterator::difference_type
813
814 \internal
815*/
816
817/*! \typedef QLinkedList::iterator::value_type
818
819 \internal
820*/
821
822/*! \typedef QLinkedList::iterator::pointer
823
824 \internal
825*/
826
827/*! \typedef QLinkedList::iterator::reference
828
829 \internal
830*/
831
832/*! \fn template <class T> QLinkedList<T>::iterator::iterator(const iterator &other)
833
834 Constructs a copy of \a other.
835*/
836
837/*! \fn template <class T> QLinkedList<T>::iterator &QLinkedList<T>::iterator::operator=(const iterator &other)
838
839 Assigns \a other to this iterator.
840*/
841
842/*!
843 \fn template <class T> QLinkedList<T> &QLinkedList<T>::operator=(QLinkedList<T> &&other)
844
845 Move-assigns \a other to this QLinkedList instance.
846
847 \since 5.2
848*/
849
850/*! \fn template <class T> T &QLinkedList<T>::iterator::operator*() const
851
852 Returns a modifiable reference to the current item.
853
854 You can change the value of an item by using operator*() on the
855 left side of an assignment, for example:
856
857 \snippet code/src_corelib_tools_qlinkedlist.cpp 13
858
859 \sa operator->()
860*/
861
862/*! \fn template <class T> T *QLinkedList<T>::iterator::operator->() const
863
864 Returns a pointer to the current item.
865
866 \sa operator*()
867*/
868
869/*!
870 \fn template <class T> bool QLinkedList<T>::iterator::operator==(const iterator &other) const
871 \fn template <class T> bool QLinkedList<T>::iterator::operator==(const const_iterator &other) const
872
873 Returns \c true if \a other points to the same item as this
874 iterator; otherwise returns \c false.
875
876 \sa operator!=()
877*/
878
879/*!
880 \fn template <class T> bool QLinkedList<T>::iterator::operator!=(const iterator &other) const
881 \fn template <class T> bool QLinkedList<T>::iterator::operator!=(const const_iterator &other) const
882
883 Returns \c true if \a other points to a different item than this
884 iterator; otherwise returns \c false.
885
886 \sa operator==()
887*/
888
889/*! \fn template <class T> QLinkedList<T>::iterator &QLinkedList<T>::iterator::operator++()
890
891 The prefix ++ operator (\c{++it}) advances the iterator to the
892 next item in the list and returns an iterator to the new current
893 item.
894
895 Calling this function on QLinkedList::end() leads to undefined
896 results.
897
898 \sa operator--()
899*/
900
901/*! \fn template <class T> QLinkedList<T>::iterator QLinkedList<T>::iterator::operator++(int)
902
903 \overload
904
905 The postfix ++ operator (\c{it++}) advances the iterator to the
906 next item in the list and returns an iterator to the previously
907 current item.
908*/
909
910/*! \fn template <class T> QLinkedList<T>::iterator &QLinkedList<T>::iterator::operator--()
911
912 The prefix -- operator (\c{--it}) makes the preceding item
913 current and returns an iterator to the new current item.
914
915 Calling this function on QLinkedList::begin() leads to undefined
916 results.
917
918 \sa operator++()
919*/
920
921/*! \fn template <class T> QLinkedList<T>::iterator QLinkedList<T>::iterator::operator--(int)
922
923 \overload
924
925 The postfix -- operator (\c{it--}) makes the preceding item
926 current and returns an iterator to the previously current item.
927*/
928
929/*! \fn template <class T> QLinkedList<T>::iterator QLinkedList<T>::iterator::operator+(int j) const
930
931 Returns an iterator to the item at \a j positions forward from
932 this iterator. (If \a j is negative, the iterator goes backward.)
933
934 This operation can be slow for large \a j values.
935
936 \sa operator-()
937
938*/
939
940/*! \fn template <class T> QLinkedList<T>::iterator QLinkedList<T>::iterator::operator-(int j) const
941
942 Returns an iterator to the item at \a j positions backward from
943 this iterator. (If \a j is negative, the iterator goes forward.)
944
945 This operation can be slow for large \a j values.
946
947 \sa operator+()
948*/
949
950/*! \fn template <class T> QLinkedList<T>::iterator &QLinkedList<T>::iterator::operator+=(int j)
951
952 Advances the iterator by \a j items. (If \a j is negative, the
953 iterator goes backward.)
954
955 \sa operator-=(), operator+()
956*/
957
958/*! \fn template <class T> QLinkedList<T>::iterator &QLinkedList<T>::iterator::operator-=(int j)
959
960 Makes the iterator go back by \a j items. (If \a j is negative,
961 the iterator goes forward.)
962
963 \sa operator+=(), operator-()
964*/
965
966/*! \class QLinkedList::const_iterator
967 \inmodule QtCore
968 \brief The QLinkedList::const_iterator class provides an STL-style const iterator for QLinkedList.
969
970 QLinkedList features both \l{STL-style iterators} and
971 \l{Java-style iterators}. The STL-style iterators are more
972 low-level and more cumbersome to use; on the other hand, they are
973 slightly faster and, for developers who already know STL, have
974 the advantage of familiarity.
975
976 QLinkedList\<T\>::const_iterator allows you to iterate over a
977 QLinkedList\<T\>. If you want modify the QLinkedList as you iterate
978 over it, you must use QLinkedList::iterator instead. It is
979 generally good practice to use QLinkedList::const_iterator on a
980 non-const QLinkedList as well, unless you need to change the
981 QLinkedList through the iterator. Const iterators are slightly
982 faster, and can improve code readability.
983
984 The default QLinkedList::const_iterator constructor creates an
985 uninitialized iterator. You must initialize it using a function
986 like QLinkedList::constBegin(), QLinkedList::constEnd(), or
987 QLinkedList::insert() before you can start iterating. Here's a
988 typical loop that prints all the items stored in a list:
989
990 \snippet code/src_corelib_tools_qlinkedlist.cpp 14
991
992 STL-style iterators can be used as arguments to \l{generic
993 algorithms}. For example, here's how to find an item in the list:
994
995 \snippet code/src_corelib_tools_qlinkedlist.cpp 15
996
997 Multiple iterators can be used on the same list. If you add items
998 to the list, existing iterators will remain valid. If you remove
999 items from the list, iterators that point to the removed items
1000 will become dangling iterators.
1001
1002 \warning Iterators on implicitly shared containers do not work
1003 exactly like STL-iterators. You should avoid copying a container
1004 while iterators are active on that container. For more information,
1005 read \l{Implicit sharing iterator problem}.
1006
1007 \sa QLinkedList::iterator, QLinkedListIterator
1008*/
1009
1010/*! \fn template <class T> QLinkedList<T>::const_iterator::const_iterator()
1011
1012 Constructs an uninitialized iterator.
1013
1014 Functions like operator*() and operator++() should not be called
1015 on an uninitialized iterator. Use operator=() to assign a value
1016 to it before using it.
1017
1018 \sa QLinkedList::constBegin(), QLinkedList::constEnd()
1019*/
1020
1021/*! \fn template <class T> QLinkedList<T>::const_iterator::const_iterator(Node *node)
1022
1023 \internal
1024*/
1025
1026/*! \typedef QLinkedList::const_iterator::iterator_category
1027
1028 \internal
1029*/
1030
1031/*! \typedef QLinkedList::const_iterator::difference_type
1032
1033 \internal
1034*/
1035
1036/*! \typedef QLinkedList::const_iterator::value_type
1037
1038 \internal
1039*/
1040
1041/*! \typedef QLinkedList::const_iterator::pointer
1042
1043 \internal
1044*/
1045
1046/*! \typedef QLinkedList::const_iterator::reference
1047
1048 \internal
1049*/
1050
1051/*! \fn template <class T> QLinkedList<T>::const_iterator::const_iterator(const const_iterator &other)
1052
1053 Constructs a copy of \a other.
1054*/
1055
1056/*! \fn template <class T> QLinkedList<T>::const_iterator::const_iterator(iterator other)
1057
1058 Constructs a copy of \a other.
1059*/
1060
1061/*! \fn template <class T> typename QLinkedList<T>::const_iterator &QLinkedList<T>::const_iterator::operator=(const const_iterator &other)
1062
1063 Assigns \a other to this iterator.
1064*/
1065
1066/*! \fn template <class T> const T &QLinkedList<T>::const_iterator::operator*() const
1067
1068 Returns a reference to the current item.
1069
1070 \sa operator->()
1071*/
1072
1073/*! \fn template <class T> const T *QLinkedList<T>::const_iterator::operator->() const
1074
1075 Returns a pointer to the current item.
1076
1077 \sa operator*()
1078*/
1079
1080/*! \fn template <class T> bool QLinkedList<T>::const_iterator::operator==(const const_iterator &other) const
1081
1082 Returns \c true if \a other points to the same item as this
1083 iterator; otherwise returns \c false.
1084
1085 \sa operator!=()
1086*/
1087
1088/*! \fn template <class T> bool QLinkedList<T>::const_iterator::operator!=(const const_iterator &other) const
1089
1090 Returns \c true if \a other points to a different item than this
1091 iterator; otherwise returns \c false.
1092
1093 \sa operator==()
1094*/
1095
1096/*! \fn template <class T> QLinkedList<T>::const_iterator &QLinkedList<T>::const_iterator::operator++()
1097
1098 The prefix ++ operator (\c{++it}) advances the iterator to the
1099 next item in the list and returns an iterator to the new current
1100 item.
1101
1102 Calling this function on QLinkedList<T>::constEnd() leads to
1103 undefined results.
1104
1105 \sa operator--()
1106*/
1107
1108/*! \fn template <class T> QLinkedList<T>::const_iterator QLinkedList<T>::const_iterator::operator++(int)
1109
1110 \overload
1111
1112 The postfix ++ operator (\c{it++}) advances the iterator to the
1113 next item in the list and returns an iterator to the previously
1114 current item.
1115*/
1116
1117/*! \fn template <class T> QLinkedList<T>::const_iterator &QLinkedList<T>::const_iterator::operator--()
1118
1119 The prefix -- operator (\c{--it}) makes the preceding item
1120 current and returns an iterator to the new current item.
1121
1122 Calling this function on QLinkedList::begin() leads to undefined
1123 results.
1124
1125 \sa operator++()
1126*/
1127
1128/*! \fn template <class T> QLinkedList<T>::const_iterator QLinkedList<T>::const_iterator::operator--(int)
1129
1130 \overload
1131
1132 The postfix -- operator (\c{it--}) makes the preceding item
1133 current and returns an iterator to the previously current item.
1134*/
1135
1136/*! \fn template <class T> QLinkedList<T>::const_iterator QLinkedList<T>::const_iterator::operator+(int j) const
1137
1138 Returns an iterator to the item at \a j positions forward from
1139 this iterator. (If \a j is negative, the iterator goes backward.)
1140
1141 This operation can be slow for large \a j values.
1142
1143 \sa operator-()
1144*/
1145
1146/*! \fn template <class T> QLinkedList<T>::const_iterator QLinkedList<T>::const_iterator::operator-(int j) const
1147
1148 This function returns an iterator to the item at \a j positions backward from
1149 this iterator. (If \a j is negative, the iterator goes forward.)
1150
1151 This operation can be slow for large \a j values.
1152
1153 \sa operator+()
1154*/
1155
1156/*! \fn template <class T> QLinkedList<T>::const_iterator &QLinkedList<T>::const_iterator::operator+=(int j)
1157
1158 Advances the iterator by \a j items. (If \a j is negative, the
1159 iterator goes backward.)
1160
1161 This operation can be slow for large \a j values.
1162
1163 \sa operator-=(), operator+()
1164*/
1165
1166/*! \fn template <class T> QLinkedList<T>::const_iterator &QLinkedList<T>::const_iterator::operator-=(int j)
1167
1168 Makes the iterator go back by \a j items. (If \a j is negative,
1169 the iterator goes forward.)
1170
1171 This operation can be slow for large \a j values.
1172
1173 \sa operator+=(), operator-()
1174*/
1175
1176/*! \fn template <class T> QDataStream &operator<<(QDataStream &out, const QLinkedList<T> &list)
1177 \relates QLinkedList
1178
1179 Writes the linked list \a list to stream \a out.
1180
1181 This function requires the value type to implement \c
1182 operator<<().
1183
1184 \sa{Serializing Qt Data Types}{Format of the QDataStream operators}
1185*/
1186
1187/*! \fn template <class T> QDataStream &operator>>(QDataStream &in, QLinkedList<T> &list)
1188 \relates QLinkedList
1189
1190 Reads a linked list from stream \a in into \a list.
1191
1192 This function requires the value type to implement \c operator>>().
1193
1194 \sa{Serializing Qt Data Types}{Format of the QDataStream operators}
1195*/
1196
1197/*!
1198 \since 4.1
1199 \fn template <class T> QLinkedList<T> QLinkedList<T>::fromStdList(const std::list<T> &list)
1200
1201 Returns a QLinkedList object with the data contained in \a list.
1202 The order of the elements in the QLinkedList is the same as in \a
1203 list.
1204
1205 Example:
1206
1207 \snippet code/src_corelib_tools_qlinkedlist.cpp 16
1208
1209 \sa toStdList()
1210*/
1211
1212/*!
1213 \since 4.1
1214 \fn template <class T> std::list<T> QLinkedList<T>::toStdList() const
1215
1216 Returns a std::list object with the data contained in this
1217 QLinkedList. Example:
1218
1219 \snippet code/src_corelib_tools_qlinkedlist.cpp 17
1220
1221 \sa fromStdList()
1222*/
1223
1224QT_END_NAMESPACE
1225