diff options
Diffstat (limited to 'doc/src/classes/qalgorithms.qdoc')
| -rw-r--r-- | doc/src/classes/qalgorithms.qdoc | 651 |
1 files changed, 0 insertions, 651 deletions
diff --git a/doc/src/classes/qalgorithms.qdoc b/doc/src/classes/qalgorithms.qdoc deleted file mode 100644 index 0b30879..0000000 --- a/doc/src/classes/qalgorithms.qdoc +++ /dev/null @@ -1,651 +0,0 @@ -/**************************************************************************** -** -** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). -** Contact: Nokia Corporation (qt-info@nokia.com) -** -** This file is part of the documentation of the Qt Toolkit. -** -** $QT_BEGIN_LICENSE:LGPL$ -** No Commercial Usage -** This file contains pre-release code and may not be distributed. -** You may use this file in accordance with the terms and conditions -** contained in the either Technology Preview License Agreement or the -** Beta Release License Agreement. -** -** GNU Lesser General Public License Usage -** Alternatively, this file may be used under the terms of the GNU Lesser -** General Public License version 2.1 as published by the Free Software -** Foundation and appearing in the file LICENSE.LGPL included in the -** packaging of this file. Please review the following information to -** ensure the GNU Lesser General Public License version 2.1 requirements -** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. -** -** In addition, as a special exception, Nokia gives you certain -** additional rights. These rights are described in the Nokia Qt LGPL -** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this -** package. -** -** GNU General Public License Usage -** Alternatively, this file may be used under the terms of the GNU -** General Public License version 3.0 as published by the Free Software -** Foundation and appearing in the file LICENSE.GPL included in the -** packaging of this file. Please review the following information to -** ensure the GNU General Public License version 3.0 requirements will be -** met: http://www.gnu.org/copyleft/gpl.html. -** -** If you are unsure which license is appropriate for your use, please -** contact the sales department at http://qt.nokia.com/contact. -** $QT_END_LICENSE$ -** -****************************************************************************/ - -/*! - \headerfile <QtAlgorithms> - \title Generic Algorithms - \ingroup architecture - - \brief The <QtAlgorithms> header provides generic template-based algorithms. - - Qt provides a number of global template functions in \c - <QtAlgorithms> that work on containers and perform well-know - algorithms. You can use these algorithms with any \l {container - class} that provides STL-style iterators, including Qt's QList, - QLinkedList, QVector, QMap, and QHash classes. - - These functions have taken their inspiration from similar - functions available in the STL \c <algorithm> header. Most of them - have a direct STL equivalent; for example, qCopyBackward() is the - same as STL's copy_backward() algorithm. - - If STL is available on all your target platforms, you can use the - STL algorithms instead of their Qt counterparts. One reason why - you might want to use the STL algorithms is that STL provides - dozens and dozens of algorithms, whereas Qt only provides the most - important ones, making no attempt to duplicate functionality that - is already provided by the C++ standard. - - Most algorithms take \l {STL-style iterators} as parameters. The - algorithms are generic in the sense that they aren't bound to a - specific iterator class; you can use them with any iterators that - meet a certain set of requirements. - - Let's take the qFill() algorithm as an example. Unlike QVector, - QList has no fill() function that can be used to fill a list with - a particular value. If you need that functionality, you can use - qFill(): - - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 0 - - qFill() takes a begin iterator, an end iterator, and a value. - In the example above, we pass \c list.begin() and \c list.end() - as the begin and end iterators, but this doesn't have to be - the case: - - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 1 - - Different algorithms can have different requirements for the - iterators they accept. For example, qFill() accepts two - \l {forward iterators}. The iterator types required are specified - for each algorithm. If an iterator of the wrong type is passed (for - example, if QList::ConstIterator is passed as an \l {output - iterator}), you will always get a compiler error, although not - necessarily a very informative one. - - Some algorithms have special requirements on the value type - stored in the containers. For example, qEqual() requires that the - value type supports operator==(), which it uses to compare items. - Similarly, qDeleteAll() requires that the value type is a - non-const pointer type (for example, QWidget *). The value type - requirements are specified for each algorithm, and the compiler - will produce an error if a requirement isn't met. - - \target binaryFind example - - The generic algorithms can be used on other container classes - than those provided by Qt and STL. The syntax of STL-style - iterators is modeled after C++ pointers, so it's possible to use - plain arrays as containers and plain pointers as iterators. A - common idiom is to use qBinaryFind() together with two static - arrays: one that contains a list of keys, and another that - contains a list of associated values. For example, the following - code will look up an HTML entity (e.g., \c &) in the \c - name_table array and return the corresponding Unicode value from - the \c value_table if the entity is recognized: - - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 2 - - This kind of code is for advanced users only; for most - applications, a QMap- or QHash-based approach would work just as - well: - - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 3 - - \section1 Types of Iterators - - The algorithms have certain requirements on the iterator types - they accept, and these are specified individually for each - function. The compiler will produce an error if a requirement - isn't met. - - \section2 Input Iterators - - An \e{input iterator} is an iterator that can be used for reading - data sequentially from a container. It must provide the following - operators: \c{==} and \c{!=} for comparing two iterators, unary - \c{*} for retrieving the value stored in the item, and prefix - \c{++} for advancing to the next item. - - The Qt containers' iterator types (const and non-const) are all - input iterators. - - \section2 Output Iterators - - An \e{output iterator} is an iterator that can be used for - writing data sequentially to a container or to some output - stream. It must provide the following operators: unary \c{*} for - writing a value (i.e., \c{*it = val}) and prefix \c{++} for - advancing to the next item. - - The Qt containers' non-const iterator types are all output - iterators. - - \section2 Forward Iterators - - A \e{forward iterator} is an iterator that meets the requirements - of both input iterators and output iterators. - - The Qt containers' non-const iterator types are all forward - iterators. - - \section2 Bidirectional Iterators - - A \e{bidirectional iterator} is an iterator that meets the - requirements of forward iterators but that in addition supports - prefix \c{--} for iterating backward. - - The Qt containers' non-const iterator types are all bidirectional - iterators. - - \section2 Random Access Iterators - - The last category, \e{random access iterators}, is the most - powerful type of iterator. It supports all the requirements of a - bidirectional iterator, and supports the following operations: - - \table - \row \i \c{i += n} \i advances iterator \c i by \c n positions - \row \i \c{i -= n} \i moves iterator \c i back by \c n positions - \row \i \c{i + n} or \c{n + i} \i returns the iterator for the item \c - n positions ahead of iterator \c i - \row \i \c{i - n} \i returns the iterator for the item \c n positions behind of iterator \c i - \row \i \c{i - j} \i returns the number of items between iterators \c i and \c j - \row \i \c{i[n]} \i same as \c{*(i + n)} - \row \i \c{i < j} \i returns true if iterator \c j comes after iterator \c i - \endtable - - QList and QVector's non-const iterator types are random access iterators. - - \sa {container classes}, <QtGlobal> -*/ - -/*! \fn OutputIterator qCopy(InputIterator begin1, InputIterator end1, OutputIterator begin2) - \relates <QtAlgorithms> - - Copies the items from range [\a begin1, \a end1) to range [\a - begin2, ...), in the order in which they appear. - - The item at position \a begin1 is assigned to that at position \a - begin2; the item at position \a begin1 + 1 is assigned to that at - position \a begin2 + 1; and so on. - - Example: - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 4 - - \sa qCopyBackward(), {input iterators}, {output iterators} -*/ - -/*! \fn BiIterator2 qCopyBackward(BiIterator1 begin1, BiIterator1 end1, BiIterator2 end2) - \relates <QtAlgorithms> - - Copies the items from range [\a begin1, \a end1) to range [..., - \a end2). - - The item at position \a end1 - 1 is assigned to that at position - \a end2 - 1; the item at position \a end1 - 2 is assigned to that - at position \a end2 - 2; and so on. - - Example: - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 5 - - \sa qCopy(), {bidirectional iterators} -*/ - -/*! \fn bool qEqual(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2) - \relates <QtAlgorithms> - - Compares the items in the range [\a begin1, \a end1) with the - items in the range [\a begin2, ...). Returns true if all the - items compare equal; otherwise returns false. - - Example: - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 6 - - This function requires the item type (in the example above, - QString) to implement \c operator==(). - - \sa {input iterators} -*/ - -/*! \fn void qFill(ForwardIterator begin, ForwardIterator end, const T &value) - \relates <QtAlgorithms> - - Fills the range [\a begin, \a end) with \a value. - - Example: - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 7 - - \sa qCopy(), {forward iterators} -*/ - -/*! \fn void qFill(Container &container, const T &value) - \relates <QtAlgorithms> - - \overload - - This is the same as qFill(\a{container}.begin(), \a{container}.end(), \a value); -*/ - -/*! \fn InputIterator qFind(InputIterator begin, InputIterator end, const T &value) - \relates <QtAlgorithms> - - Returns an iterator to the first occurrence of \a value in a - container in the range [\a begin, \a end). Returns \a end if \a - value isn't found. - - Example: - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 8 - - This function requires the item type (in the example above, - QString) to implement \c operator==(). - - If the items in the range are in ascending order, you can get - faster results by using qLowerBound() or qBinaryFind() instead of - qFind(). - - \sa qBinaryFind(), {input iterators} -*/ - -/*! \fn void qFind(const Container &container, const T &value) - \relates <QtAlgorithms> - - \overload - - This is the same as qFind(\a{container}.begin(), \a{container}.end(), value); -*/ - -/*! \fn void qCount(InputIterator begin, InputIterator end, const T &value, Size &n) - \relates <QtAlgorithms> - - Returns the number of occurrences of \a value in the range [\a begin, \a end), - which is returned in \a n. \a n is never initialized, the count is added to \a n. - It is the caller's responsibility to initialize \a n. - - Example: - - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 9 - - This function requires the item type (in the example above, - \c int) to implement \c operator==(). - - \sa {input iterators} -*/ - -/*! \fn void qCount(const Container &container, const T &value, Size &n) -\relates <QtAlgorithms> - -\overload - -Instead of operating on iterators, as in the other overload, this function -operates on the specified \a container to obtain the number of instances -of \a value in the variable passed as a reference in argument \a n. -*/ - -/*! \fn void qSwap(T &var1, T &var2) - \relates <QtAlgorithms> - - Exchanges the values of variables \a var1 and \a var2. - - Example: - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 10 -*/ - -/*! \fn void qSort(RandomAccessIterator begin, RandomAccessIterator end) - \relates <QtAlgorithms> - - Sorts the items in range [\a begin, \a end) in ascending order - using the quicksort algorithm. - - Example: - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 11 - - The sort algorithm is efficient on large data sets. It operates - in \l {linear-logarithmic time}, O(\e{n} log \e{n}). - - This function requires the item type (in the example above, - \c{int}) to implement \c operator<(). - - If neither of the two items is "less than" the other, the items are - taken to be equal. It is then undefined which one of the two - items will appear before the other after the sort. - - \sa qStableSort(), {random access iterators} -*/ - -/*! \fn void qSort(RandomAccessIterator begin, RandomAccessIterator end, LessThan lessThan) - \relates <QtAlgorithms> - - \overload - - Uses the \a lessThan function instead of \c operator<() to - compare the items. - - For example, here's how to sort the strings in a QStringList - in case-insensitive alphabetical order: - - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 12 - - To sort values in reverse order, pass - \l{qGreater()}{qGreater<T>()} as the \a lessThan parameter. For - example: - - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 13 - - If neither of the two items is "less than" the other, the items are - taken to be equal. It is then undefined which one of the two - items will appear before the other after the sort. - - An alternative to using qSort() is to put the items to sort in a - QMap, using the sort key as the QMap key. This is often more - convenient than defining a \a lessThan function. For example, the - following code shows how to sort a list of strings case - insensitively using QMap: - - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 14 - - \sa QMap -*/ - -/*! \fn void qSort(Container &container) - \relates <QtAlgorithms> - - \overload - - This is the same as qSort(\a{container}.begin(), \a{container}.end()); -*/ - -/*! - \fn void qStableSort(RandomAccessIterator begin, RandomAccessIterator end) - \relates <QtAlgorithms> - - Sorts the items in range [\a begin, \a end) in ascending order - using a stable sorting algorithm. - - If neither of the two items is "less than" the other, the items are - taken to be equal. The item that appeared before the other in the - original container will still appear first after the sort. This - property is often useful when sorting user-visible data. - - Example: - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 15 - - The sort algorithm is efficient on large data sets. It operates - in \l {linear-logarithmic time}, O(\e{n} log \e{n}). - - This function requires the item type (in the example above, - \c{int}) to implement \c operator<(). - - \sa qSort(), {random access iterators} -*/ - -/*! - \fn void qStableSort(RandomAccessIterator begin, RandomAccessIterator end, LessThan lessThan) - \relates <QtAlgorithms> - - \overload - - Uses the \a lessThan function instead of \c operator<() to - compare the items. - - For example, here's how to sort the strings in a QStringList - in case-insensitive alphabetical order: - - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 16 - - Note that earlier versions of Qt allowed using a lessThan function that took its - arguments by non-const reference. From 4.3 and on this is no longer possible, - the arguments has to be passed by const reference or value. - - To sort values in reverse order, pass - \l{qGreater()}{qGreater<T>()} as the \a lessThan parameter. For - example: - - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 17 - - If neither of the two items is "less than" the other, the items are - taken to be equal. The item that appeared before the other in the - original container will still appear first after the sort. This - property is often useful when sorting user-visible data. -*/ - -/*! - \fn void qStableSort(Container &container) - \relates <QtAlgorithms> - - \overload - - This is the same as qStableSort(\a{container}.begin(), \a{container}.end()); -*/ - -/*! \fn RandomAccessIterator qLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value) - \relates <QtAlgorithms> - - Performs a binary search of the range [\a begin, \a end) and - returns the position of the first ocurrence of \a value. If no - such item is found, returns the position where it should be - inserted. - - The items in the range [\a begin, \e end) must be sorted in - ascending order; see qSort(). - - Example: - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 18 - - This function requires the item type (in the example above, - \c{int}) to implement \c operator<(). - - qLowerBound() can be used in conjunction with qUpperBound() to - iterate over all occurrences of the same value: - - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 19 - - \sa qUpperBound(), qBinaryFind() -*/ - -/*! - \fn RandomAccessIterator qLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan) - \relates <QtAlgorithms> - - \overload - - Uses the \a lessThan function instead of \c operator<() to - compare the items. - - Note that the items in the range must be sorted according to the order - specified by the \a lessThan object. -*/ - -/*! - \fn void qLowerBound(const Container &container, const T &value) - \relates <QtAlgorithms> - - \overload - - For read-only iteration over containers, this function is broadly equivalent to - qLowerBound(\a{container}.begin(), \a{container}.end(), value). However, since it - returns a const iterator, you cannot use it to modify the container; for example, - to insert items. -*/ - -/*! \fn RandomAccessIterator qUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value) - \relates <QtAlgorithms> - - Performs a binary search of the range [\a begin, \a end) and - returns the position of the one-past-the-last occurrence of \a - value. If no such item is found, returns the position where the - item should be inserted. - - The items in the range [\a begin, \e end) must be sorted in - ascending order; see qSort(). - - Example: - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 20 - - This function requires the item type (in the example above, - \c{int}) to implement \c operator<(). - - qUpperBound() can be used in conjunction with qLowerBound() to - iterate over all occurrences of the same value: - - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 21 - - \sa qLowerBound(), qBinaryFind() -*/ - -/*! - \fn RandomAccessIterator qUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan) - \relates <QtAlgorithms> - - \overload - - Uses the \a lessThan function instead of \c operator<() to - compare the items. - - Note that the items in the range must be sorted according to the order - specified by the \a lessThan object. -*/ - -/*! - \fn void qUpperBound(const Container &container, const T &value) - \relates <QtAlgorithms> - - \overload - - This is the same as qUpperBound(\a{container}.begin(), \a{container}.end(), value); -*/ - - -/*! \fn RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value) - \relates <QtAlgorithms> - - Performs a binary search of the range [\a begin, \a end) and - returns the position of an occurrence of \a value. If there are - no occurrences of \a value, returns \a end. - - The items in the range [\a begin, \a end) must be sorted in - ascending order; see qSort(). - - If there are many occurrences of the same value, any one of them - could be returned. Use qLowerBound() or qUpperBound() if you need - finer control. - - Example: - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 22 - - This function requires the item type (in the example above, - QString) to implement \c operator<(). - - See the \l{<QtAlgorithms>#binaryFind example}{detailed - description} for an example usage. - - \sa qLowerBound(), qUpperBound(), {random access iterators} -*/ - -/*! \fn RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan) - \relates <QtAlgorithms> - - \overload - - Uses the \a lessThan function instead of \c operator<() to - compare the items. - - Note that the items in the range must be sorted according to the order - specified by the \a lessThan object. -*/ - -/*! - \fn void qBinaryFind(const Container &container, const T &value) - \relates <QtAlgorithms> - - \overload - - This is the same as qBinaryFind(\a{container}.begin(), \a{container}.end(), value); -*/ - - -/*! - \fn void qDeleteAll(ForwardIterator begin, ForwardIterator end) - \relates <QtAlgorithms> - - Deletes all the items in the range [\a begin, \a end) using the - C++ \c delete operator. The item type must be a pointer type (for - example, \c{QWidget *}). - - Example: - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 23 - - Notice that qDeleteAll() doesn't remove the items from the - container; it merely calls \c delete on them. In the example - above, we call clear() on the container to remove the items. - - This function can also be used to delete items stored in - associative containers, such as QMap and QHash. Only the objects - stored in each container will be deleted by this function; objects - used as keys will not be deleted. - - \sa {forward iterators} -*/ - -/*! - \fn void qDeleteAll(const Container &c) - \relates <QtAlgorithms> - - \overload - - This is the same as qDeleteAll(\a{c}.begin(), \a{c}.end()). -*/ - -/*! \fn LessThan qLess() - \relates <QtAlgorithms> - - Returns a functional object, or functor, that can be passed to qSort() - or qStableSort(). - - Example: - - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 24 - - \sa {qGreater()}{qGreater<T>()} -*/ - -/*! \fn LessThan qGreater() - \relates <QtAlgorithms> - - Returns a functional object, or functor, that can be passed to qSort() - or qStableSort(). - - Example: - - \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 25 - - \sa {qLess()}{qLess<T>()} -*/ |