← Back to branch summary

~oif-team/ubuntu/natty/qt4-x11/xi2.1

« back to all changes in this revision

Viewing changes to src/corelib/tools/qlinkedlist.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Adam Conrad
  • Date: 2005-08-24 04:09:09 UTC
  • Revision ID: james.westby@ubuntu.com-20050824040909-xmxe9jfr4a0w5671
Tags: upstream-4.0.0
Import upstream version 4.0.0

Show diffs side-by-side

added added

removed removed

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