src/corelib/tools/qalgorithms.qdoc

   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 documentation of the Qt Toolkit.
   7 **
   8 ** $QT_BEGIN_LICENSE:FDL$
   9 ** GNU Free Documentation License
  10 ** Alternatively, this file may be used under the terms of the GNU Free
  11 ** Documentation License version 1.3 as published by the Free Software
  12 ** Foundation and appearing in the file included in the packaging of
  13 ** this file.
  14 **
  15 ** Other Usage
  16 ** Alternatively, this file may be used in accordance with the terms
  17 ** and conditions contained in a signed written agreement between you
  18 ** and Nokia.
  19 **
  20 **
  21 **
  22 **
  23 **
  24 ** $QT_END_LICENSE$
  25 **
  26 ****************************************************************************/
  27
  28 /*!
  29     \headerfile <QtAlgorithms>
  30     \title Generic Algorithms
  31     \ingroup funclists
  32
  33     \brief The <QtAlgorithms> header includes the generic, template-based algorithms.
  34
  35     Qt provides a number of global template functions in \c
  36     <QtAlgorithms> that work on containers and perform well-know
  37     algorithms. You can use these algorithms with any \l {container
  38     class} that provides STL-style iterators, including Qt's QList,
  39     QLinkedList, QVector, QMap, and QHash classes.
  40
  41     These functions have taken their inspiration from similar
  42     functions available in the STL \c <algorithm> header. Most of them
  43     have a direct STL equivalent; for example, qCopyBackward() is the
  44     same as STL's copy_backward() algorithm.
  45
  46     If STL is available on all your target platforms, you can use the
  47     STL algorithms instead of their Qt counterparts. One reason why
  48     you might want to use the STL algorithms is that STL provides
  49     dozens and dozens of algorithms, whereas Qt only provides the most
  50     important ones, making no attempt to duplicate functionality that
  51     is already provided by the C++ standard.
  52
  53     Most algorithms take \l {STL-style iterators} as parameters. The
  54     algorithms are generic in the sense that they aren't bound to a
  55     specific iterator class; you can use them with any iterators that
  56     meet a certain set of requirements.
  57
  58     Let's take the qFill() algorithm as an example. Unlike QVector,
  59     QList has no fill() function that can be used to fill a list with
  60     a particular value. If you need that functionality, you can use
  61     qFill():
  62
  63     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 0
  64
  65     qFill() takes a begin iterator, an end iterator, and a value.
  66     In the example above, we pass \c list.begin() and \c list.end()
  67     as the begin and end iterators, but this doesn't have to be
  68     the case:
  69
  70     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 1
  71
  72     Different algorithms can have different requirements for the
  73     iterators they accept. For example, qFill() accepts two
  74     \l {forward iterators}. The iterator types required are specified
  75     for each algorithm. If an iterator of the wrong type is passed (for
  76     example, if QList::ConstIterator is passed as an \l {output
  77     iterator}), you will always get a compiler error, although not
  78     necessarily a very informative one.
  79
  80     Some algorithms have special requirements on the value type
  81     stored in the containers. For example, qEqual() requires that the
  82     value type supports operator==(), which it uses to compare items.
  83     Similarly, qDeleteAll() requires that the value type is a
  84     non-const pointer type (for example, QWidget *). The value type
  85     requirements are specified for each algorithm, and the compiler
  86     will produce an error if a requirement isn't met.
  87
  88     \target binaryFind example
  89
  90     The generic algorithms can be used on other container classes
  91     than those provided by Qt and STL. The syntax of STL-style
  92     iterators is modeled after C++ pointers, so it's possible to use
  93     plain arrays as containers and plain pointers as iterators. A
  94     common idiom is to use qBinaryFind() together with two static
  95     arrays: one that contains a list of keys, and another that
  96     contains a list of associated values. For example, the following
  97     code will look up an HTML entity (e.g., \c &amp;) in the \c
  98     name_table array and return the corresponding Unicode value from
  99     the \c value_table if the entity is recognized:
 100
 101     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 2
 102
 103     This kind of code is for advanced users only; for most
 104     applications, a QMap- or QHash-based approach would work just as
 105     well:
 106
 107     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 3
 108
 109     \section1 Types of Iterators
 110
 111     The algorithms have certain requirements on the iterator types
 112     they accept, and these are specified individually for each
 113     function. The compiler will produce an error if a requirement
 114     isn't met.
 115
 116     \section2 Input Iterators
 117
 118     An \e{input iterator} is an iterator that can be used for reading
 119     data sequentially from a container. It must provide the following
 120     operators: \c{==} and \c{!=} for comparing two iterators, unary
 121     \c{*} for retrieving the value stored in the item, and prefix
 122     \c{++} for advancing to the next item.
 123
 124     The Qt containers' iterator types (const and non-const) are all
 125     input iterators.
 126
 127     \section2 Output Iterators
 128
 129     An \e{output iterator} is an iterator that can be used for
 130     writing data sequentially to a container or to some output
 131     stream. It must provide the following operators: unary \c{*} for
 132     writing a value (i.e., \c{*it = val}) and prefix \c{++} for
 133     advancing to the next item.
 134
 135     The Qt containers' non-const iterator types are all output
 136     iterators.
 137
 138     \section2 Forward Iterators
 139
 140     A \e{forward iterator} is an iterator that meets the requirements
 141     of both input iterators and output iterators.
 142
 143     The Qt containers' non-const iterator types are all forward
 144     iterators.
 145
 146     \section2 Bidirectional Iterators
 147
 148     A \e{bidirectional iterator} is an iterator that meets the
 149     requirements of forward iterators but that in addition supports
 150     prefix \c{--} for iterating backward.
 151
 152     The Qt containers' non-const iterator types are all bidirectional
 153     iterators.
 154
 155     \section2 Random Access Iterators
 156
 157     The last category, \e{random access iterators}, is the most
 158     powerful type of iterator. It supports all the requirements of a
 159     bidirectional iterator, and supports the following operations:
 160
 161     \table
 162     \row \li \c{i += n} \li advances iterator \c i by \c n positions
 163     \row \li \c{i -= n} \li moves iterator \c i back by \c n positions
 164     \row \li \c{i + n} or \c{n + i} \li returns the iterator for the item \c
 165        n positions ahead of iterator \c i
 166     \row \li \c{i - n} \li returns the iterator for the item \c n positions behind of iterator \c i
 167     \row \li \c{i - j} \li returns the number of items between iterators \c i and \c j
 168     \row \li \c{i[n]} \li same as \c{*(i + n)}
 169     \row \li \c{i < j} \li returns true if iterator \c j comes after iterator \c i
 170     \endtable
 171
 172     QList and QVector's non-const iterator types are random access iterators.
 173
 174     \sa {container classes}, <QtGlobal>
 175 */
 176
 177 /*! \fn OutputIterator qCopy(InputIterator begin1, InputIterator end1, OutputIterator begin2)
 178     \relates <QtAlgorithms>
 179
 180     Copies the items from range [\a begin1, \a end1) to range [\a
 181     begin2, ...), in the order in which they appear.
 182
 183     The item at position \a begin1 is assigned to that at position \a
 184     begin2; the item at position \a begin1 + 1 is assigned to that at
 185     position \a begin2 + 1; and so on.
 186
 187     Example:
 188     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 4
 189
 190     \sa qCopyBackward(), {input iterators}, {output iterators}
 191 */
 192
 193 /*! \fn BiIterator2 qCopyBackward(BiIterator1 begin1, BiIterator1 end1, BiIterator2 end2)
 194     \relates <QtAlgorithms>
 195
 196     Copies the items from range [\a begin1, \a end1) to range [...,
 197     \a end2).
 198
 199     The item at position \a end1 - 1 is assigned to that at position
 200     \a end2 - 1; the item at position \a end1 - 2 is assigned to that
 201     at position \a end2 - 2; and so on.
 202
 203     Example:
 204     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 5
 205
 206     \sa qCopy(), {bidirectional iterators}
 207 */
 208
 209 /*! \fn bool qEqual(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
 210     \relates <QtAlgorithms>
 211
 212     Compares the items in the range [\a begin1, \a end1) with the
 213     items in the range [\a begin2, ...). Returns true if all the
 214     items compare equal; otherwise returns false.
 215
 216     Example:
 217     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 6
 218
 219     This function requires the item type (in the example above,
 220     QString) to implement \c operator==().
 221
 222     \sa {input iterators}
 223 */
 224
 225 /*! \fn void qFill(ForwardIterator begin, ForwardIterator end, const T &value)
 226     \relates <QtAlgorithms>
 227
 228     Fills the range [\a begin, \a end) with \a value.
 229
 230     Example:
 231     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 7
 232
 233     \sa qCopy(), {forward iterators}
 234 */
 235
 236 /*! \fn void qFill(Container &container, const T &value)
 237     \relates <QtAlgorithms>
 238
 239     \overload
 240
 241     This is the same as qFill(\a{container}.begin(), \a{container}.end(), \a value);
 242 */
 243
 244 /*! \fn InputIterator qFind(InputIterator begin, InputIterator end, const T &value)
 245     \relates <QtAlgorithms>
 246
 247     Returns an iterator to the first occurrence of \a value in a
 248     container in the range [\a begin, \a end). Returns \a end if \a
 249     value isn't found.
 250
 251     Example:
 252     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 8
 253
 254     This function requires the item type (in the example above,
 255     QString) to implement \c operator==().
 256
 257     If the items in the range are in ascending order, you can get
 258     faster results by using qLowerBound() or qBinaryFind() instead of
 259     qFind().
 260
 261     \sa qBinaryFind(), {input iterators}
 262 */
 263
 264 /*! \fn void qFind(const Container &container, const T &value)
 265     \relates <QtAlgorithms>
 266
 267     \overload
 268
 269     This is the same as qFind(\a{container}.constBegin(), \a{container}.constEnd(), value);
 270 */
 271
 272 /*! \fn void qCount(InputIterator begin, InputIterator end, const T &value, Size &n)
 273     \relates <QtAlgorithms>
 274
 275     Returns the number of occurrences of \a value in the range [\a begin, \a end),
 276     which is returned in \a n. \a n is never initialized, the count is added to \a n.
 277     It is the caller's responsibility to initialize \a n.
 278
 279     Example:
 280
 281     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 9
 282
 283     This function requires the item type (in the example above,
 284     \c int) to implement \c operator==().
 285
 286     \sa {input iterators}
 287 */
 288
 289 /*! \fn void qCount(const Container &container, const T &value, Size &n)
 290 \relates <QtAlgorithms>
 291
 292 \overload
 293
 294 Instead of operating on iterators, as in the other overload, this function
 295 operates on the specified \a container to obtain the number of instances
 296 of \a value in the variable passed as a reference in argument \a n.
 297 */
 298
 299 /*! \fn void qSwap(T &var1, T &var2)
 300     \relates <QtAlgorithms>
 301
 302     Exchanges the values of variables \a var1 and \a var2.
 303
 304     Example:
 305     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 10
 306 */
 307
 308 /*! \fn void qSort(RandomAccessIterator begin, RandomAccessIterator end)
 309     \relates <QtAlgorithms>
 310
 311     Sorts the items in range [\a begin, \a end) in ascending order
 312     using the quicksort algorithm.
 313
 314     Example:
 315     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 11
 316
 317     The sort algorithm is efficient on large data sets. It operates
 318     in \l {linear-logarithmic time}, O(\e{n} log \e{n}).
 319
 320     This function requires the item type (in the example above,
 321     \c{int}) to implement \c operator<().
 322
 323     If neither of the two items is "less than" the other, the items are
 324     taken to be equal. It is then undefined which one of the two
 325     items will appear before the other after the sort.
 326
 327     \sa qStableSort(), {random access iterators}
 328 */
 329
 330 /*! \fn void qSort(RandomAccessIterator begin, RandomAccessIterator end, LessThan lessThan)
 331     \relates <QtAlgorithms>
 332
 333     \overload
 334
 335     Uses the \a lessThan function instead of \c operator<() to
 336     compare the items.
 337
 338     For example, here's how to sort the strings in a QStringList
 339     in case-insensitive alphabetical order:
 340
 341     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 12
 342
 343     To sort values in reverse order, pass
 344     \l{qGreater()}{qGreater<T>()} as the \a lessThan parameter. For
 345     example:
 346
 347     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 13
 348
 349     If neither of the two items is "less than" the other, the items are
 350     taken to be equal. It is then undefined which one of the two
 351     items will appear before the other after the sort.
 352
 353     An alternative to using qSort() is to put the items to sort in a
 354     QMap, using the sort key as the QMap key. This is often more
 355     convenient than defining a \a lessThan function. For example, the
 356     following code shows how to sort a list of strings case
 357     insensitively using QMap:
 358
 359     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 14
 360
 361     \sa QMap
 362 */
 363
 364 /*! \fn void qSort(Container &container)
 365     \relates <QtAlgorithms>
 366
 367     \overload
 368
 369     This is the same as qSort(\a{container}.begin(), \a{container}.end());
 370 */
 371
 372 /*!
 373     \fn void qStableSort(RandomAccessIterator begin, RandomAccessIterator end)
 374     \relates <QtAlgorithms>
 375
 376     Sorts the items in range [\a begin, \a end) in ascending order
 377     using a stable sorting algorithm.
 378
 379     If neither of the two items is "less than" the other, the items are
 380     taken to be equal. The item that appeared before the other in the
 381     original container will still appear first after the sort. This
 382     property is often useful when sorting user-visible data.
 383
 384     Example:
 385     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 15
 386
 387     The sort algorithm is efficient on large data sets. It operates
 388     in \l {linear-logarithmic time}, O(\e{n} log \e{n}).
 389
 390     This function requires the item type (in the example above,
 391     \c{int}) to implement \c operator<().
 392
 393     \sa qSort(), {random access iterators}
 394 */
 395
 396 /*!
 397     \fn void qStableSort(RandomAccessIterator begin, RandomAccessIterator end, LessThan lessThan)
 398     \relates <QtAlgorithms>
 399
 400     \overload
 401
 402     Uses the \a lessThan function instead of \c operator<() to
 403     compare the items.
 404
 405     For example, here's how to sort the strings in a QStringList
 406     in case-insensitive alphabetical order:
 407
 408     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 16
 409
 410     Note that earlier versions of Qt allowed using a lessThan function that took its
 411     arguments by non-const reference. From 4.3 and on this is no longer possible,
 412     the arguments has to be passed by const reference or value.
 413
 414     To sort values in reverse order, pass
 415     \l{qGreater()}{qGreater<T>()} as the \a lessThan parameter. For
 416     example:
 417
 418     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 17
 419
 420     If neither of the two items is "less than" the other, the items are
 421     taken to be equal. The item that appeared before the other in the
 422     original container will still appear first after the sort. This
 423     property is often useful when sorting user-visible data.
 424 */
 425
 426 /*!
 427     \fn void qStableSort(Container &container)
 428     \relates <QtAlgorithms>
 429
 430     \overload
 431
 432     This is the same as qStableSort(\a{container}.begin(), \a{container}.end());
 433 */
 434
 435 /*! \fn RandomAccessIterator qLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
 436     \relates <QtAlgorithms>
 437
 438     Performs a binary search of the range [\a begin, \a end) and
 439     returns the position of the first ocurrence of \a value. If no
 440     such item is found, returns the position where it should be
 441     inserted.
 442
 443     The items in the range [\a begin, \e end) must be sorted in
 444     ascending order; see qSort().
 445
 446     Example:
 447     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 18
 448
 449     This function requires the item type (in the example above,
 450     \c{int}) to implement \c operator<().
 451
 452     qLowerBound() can be used in conjunction with qUpperBound() to
 453     iterate over all occurrences of the same value:
 454
 455     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 19
 456
 457     \sa qUpperBound(), qBinaryFind()
 458 */
 459
 460 /*!
 461     \fn RandomAccessIterator qLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
 462     \relates <QtAlgorithms>
 463
 464     \overload
 465
 466     Uses the \a lessThan function instead of \c operator<() to
 467     compare the items.
 468
 469     Note that the items in the range must be sorted according to the order
 470     specified by the \a lessThan object.
 471 */
 472
 473 /*!
 474     \fn void qLowerBound(const Container &container, const T &value)
 475     \relates <QtAlgorithms>
 476
 477     \overload
 478
 479     For read-only iteration over containers, this function is broadly equivalent to
 480     qLowerBound(\a{container}.begin(), \a{container}.end(), value). However, since it
 481     returns a const iterator, you cannot use it to modify the container; for example,
 482     to insert items.
 483 */
 484
 485 /*! \fn RandomAccessIterator qUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
 486     \relates <QtAlgorithms>
 487
 488     Performs a binary search of the range [\a begin, \a end) and
 489     returns the position of the one-past-the-last occurrence of \a
 490     value. If no such item is found, returns the position where the
 491     item should be inserted.
 492
 493     The items in the range [\a begin, \e end) must be sorted in
 494     ascending order; see qSort().
 495
 496     Example:
 497     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 20
 498
 499     This function requires the item type (in the example above,
 500     \c{int}) to implement \c operator<().
 501
 502     qUpperBound() can be used in conjunction with qLowerBound() to
 503     iterate over all occurrences of the same value:
 504
 505     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 21
 506
 507     \sa qLowerBound(), qBinaryFind()
 508 */
 509
 510 /*!
 511     \fn RandomAccessIterator qUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
 512     \relates <QtAlgorithms>
 513
 514     \overload
 515
 516     Uses the \a lessThan function instead of \c operator<() to
 517     compare the items.
 518
 519     Note that the items in the range must be sorted according to the order
 520     specified by the \a lessThan object.
 521 */
 522
 523 /*!
 524     \fn void qUpperBound(const Container &container, const T &value)
 525     \relates <QtAlgorithms>
 526
 527     \overload
 528
 529     This is the same as qUpperBound(\a{container}.begin(), \a{container}.end(), value);
 530 */
 531
 532
 533 /*! \fn RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value)
 534     \relates <QtAlgorithms>
 535
 536     Performs a binary search of the range [\a begin, \a end) and
 537     returns the position of an occurrence of \a value. If there are
 538     no occurrences of \a value, returns \a end.
 539
 540     The items in the range [\a begin, \a end) must be sorted in
 541     ascending order; see qSort().
 542
 543     If there are many occurrences of the same value, any one of them
 544     could be returned. Use qLowerBound() or qUpperBound() if you need
 545     finer control.
 546
 547     Example:
 548     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 22
 549
 550     This function requires the item type (in the example above,
 551     QString) to implement \c operator<().
 552
 553     See the \l{<QtAlgorithms>#binaryFind example}{detailed
 554     description} for an example usage.
 555
 556     \sa qLowerBound(), qUpperBound(), {random access iterators}
 557 */
 558
 559 /*! \fn RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan)
 560     \relates <QtAlgorithms>
 561
 562     \overload
 563
 564     Uses the \a lessThan function instead of \c operator<() to
 565     compare the items.
 566
 567     Note that the items in the range must be sorted according to the order
 568     specified by the \a lessThan object.
 569 */
 570
 571 /*!
 572     \fn void qBinaryFind(const Container &container, const T &value)
 573     \relates <QtAlgorithms>
 574
 575     \overload
 576
 577     This is the same as qBinaryFind(\a{container}.begin(), \a{container}.end(), value);
 578 */
 579
 580
 581 /*!
 582     \fn void qDeleteAll(ForwardIterator begin, ForwardIterator end)
 583     \relates <QtAlgorithms>
 584
 585     Deletes all the items in the range [\a begin, \a end) using the
 586     C++ \c delete operator. The item type must be a pointer type (for
 587     example, \c{QWidget *}).
 588
 589     Example:
 590     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 23
 591
 592     Notice that qDeleteAll() doesn't remove the items from the
 593     container; it merely calls \c delete on them. In the example
 594     above, we call clear() on the container to remove the items.
 595
 596     This function can also be used to delete items stored in
 597     associative containers, such as QMap and QHash. Only the objects
 598     stored in each container will be deleted by this function; objects
 599     used as keys will not be deleted.
 600
 601     \sa {forward iterators}
 602 */
 603
 604 /*!
 605     \fn void qDeleteAll(const Container &c)
 606     \relates <QtAlgorithms>
 607
 608     \overload
 609
 610     This is the same as qDeleteAll(\a{c}.begin(), \a{c}.end()).
 611 */
 612
 613 /*! \fn LessThan qLess()
 614     \relates <QtAlgorithms>
 615
 616     Returns a functional object, or functor, that can be passed to qSort()
 617     or qStableSort().
 618
 619     Example:
 620
 621     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 24
 622
 623     \sa {qGreater()}{qGreater<T>()}
 624 */
 625
 626 /*! \fn LessThan qGreater()
 627     \relates <QtAlgorithms>
 628
 629     Returns a functional object, or functor, that can be passed to qSort()
 630     or qStableSort().
 631
 632     Example:
 633
 634     \snippet doc/src/snippets/code/doc_src_qalgorithms.cpp 25
 635
 636     \sa {qLess()}{qLess<T>()}
 637 */