src/corelib/tools/qlinkedlist.cpp

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