diff options
Diffstat (limited to 'src/corelib/tools/qalgorithms.qdoc')
| -rw-r--r-- | src/corelib/tools/qalgorithms.qdoc | 638 |
1 files changed, 11 insertions, 627 deletions
diff --git a/src/corelib/tools/qalgorithms.qdoc b/src/corelib/tools/qalgorithms.qdoc index d480f2b487..5fe0b3e8c3 100644 --- a/src/corelib/tools/qalgorithms.qdoc +++ b/src/corelib/tools/qalgorithms.qdoc @@ -1,32 +1,9 @@ -/**************************************************************************** -** -** Copyright (C) 2016 The Qt Company Ltd. -** Contact: https://www.qt.io/licensing/ -** -** This file is part of the documentation of the Qt Toolkit. -** -** $QT_BEGIN_LICENSE:FDL$ -** Commercial License Usage -** Licensees holding valid commercial Qt licenses may use this file in -** accordance with the commercial license agreement provided with the -** Software or, alternatively, in accordance with the terms contained in -** a written agreement between you and The Qt Company. For licensing terms -** and conditions see https://www.qt.io/terms-conditions. For further -** information use the contact form at https://www.qt.io/contact-us. -** -** GNU Free Documentation License Usage -** Alternatively, this file may be used under the terms of the GNU Free -** Documentation License version 1.3 as published by the Free Software -** Foundation and appearing in the file included in the packaging of -** this file. Please review the following information to ensure -** the GNU Free Documentation License version 1.3 requirements -** will be met: https://www.gnu.org/licenses/fdl-1.3.html. -** $QT_END_LICENSE$ -** -****************************************************************************/ +// Copyright (C) 2016 The Qt Company Ltd. +// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GFDL-1.3-no-invariants-only /*! \headerfile <QtAlgorithms> + \inmodule QtCore \title Generic Algorithms \ingroup funclists \keyword generic algorithms @@ -47,38 +24,22 @@ meet a certain set of requirements. 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 + iterators they accept. 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 Iterators}{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, - 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. + Some algorithms have special requirements on the value type stored + in the containers. For example, 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. 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 code/doc_src_qalgorithms.cpp 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 code/doc_src_qalgorithms.cpp 3 + plain arrays as containers and plain pointers as iterators. \section1 Types of Iterators @@ -145,553 +106,9 @@ QList's non-const iterator type is random access iterator. - \section1 Qt and the STL Algorithms - - Historically, Qt used to provide functions which were direct equivalents of - many STL algorithmic functions. Starting with Qt 5.0, you are instead - encouraged to use directly the implementations available in the STL; most - of the Qt ones have been deprecated (although they are still available to - keep the old code compiling). - - \section2 Porting guidelines - - Most of the time, an application using the deprecated Qt algorithmic functions - can be easily ported to use the equivalent STL functions. You need to: - - \list 1 - \li add the \c{#include <algorithm>} preprocessor directive; - \li replace the Qt functions with the STL counterparts, according to the table below. - \endlist - - \table - \header - \li Qt function - \li STL function - \row - \li qBinaryFind - \li \c std::binary_search or \c std::lower_bound - \row - \li qCopy - \li \c std::copy - \row - \li qCopyBackward - \li \c std::copy_backward - \row - \li qEqual - \li \c std::equal - \row - \li qFill - \li \c std::fill - \row - \li qFind - \li \c std::find - \row - \li qCount - \li \c std::count - \row - \li qSort - \li \c std::sort - \row - \li qStableSort - \li \c std::stable_sort - \row - \li qLowerBound - \li \c std::lower_bound - \row - \li qUpperBound - \li \c std::upper_bound - \row - \li qLess - \li \c std::less - \row - \li qGreater - \li \c std::greater - - \endtable - - The only cases in which the port may not be straightforward is if the old - code relied on template specializations of the qLess() and/or the qSwap() - functions, which were used internally by the implementations of the Qt - algorithmic functions, but are instead ignored by the STL ones. - - In case the old code relied on the specialization of the qLess() functor, - then a workaround is explicitly passing an instance of the qLess() class - to the STL function, for instance like this: - - \code - std::sort(container.begin(), container.end(), qLess<T>()); - \endcode - - Instead, since it's not possible to pass a custom swapper functor to STL - functions, the only workaround for a template specialization for qSwap() is - providing the same specialization for \c std::swap(). - \sa {container classes}, <QtGlobal> */ -/*! \fn template <typename InputIterator, typename OutputIterator> OutputIterator qCopy(InputIterator begin1, InputIterator end1, OutputIterator begin2) - \relates <QtAlgorithms> - \deprecated - - Use \c std::copy instead. - - 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 code/doc_src_qalgorithms.cpp 4 - - \sa qCopyBackward(), {input iterators}, {output iterators} -*/ - -/*! \fn template <typename BiIterator1, typename BiIterator2> BiIterator2 qCopyBackward(BiIterator1 begin1, BiIterator1 end1, BiIterator2 end2) - \relates <QtAlgorithms> - \deprecated - - Use \c std::copy_backward instead. - - 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 code/doc_src_qalgorithms.cpp 5 - - \sa qCopy(), {bidirectional iterators} -*/ - -/*! \fn template <typename InputIterator1, typename InputIterator2> bool qEqual(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2) - \relates <QtAlgorithms> - \deprecated - - Use \c std::equal instead. - - Compares the items in the range [\a begin1, \a end1) with the - items in the range [\a begin2, ...). Returns \c true if all the - items compare equal; otherwise returns \c false. - - Example: - \snippet code/doc_src_qalgorithms.cpp 6 - - This function requires the item type (in the example above, - QString) to implement \c operator==(). - - \sa {input iterators} -*/ - -/*! \fn template <typename ForwardIterator, typename T> void qFill(ForwardIterator begin, ForwardIterator end, const T &value) - \relates <QtAlgorithms> - \deprecated - - Use \c std::fill instead. - - Fills the range [\a begin, \a end) with \a value. - - Example: - \snippet code/doc_src_qalgorithms.cpp 7 - - \sa qCopy(), {forward iterators} -*/ - -/*! \fn template <typename Container, typename T> void qFill(Container &container, const T &value) - \relates <QtAlgorithms> - \deprecated - \overload - - Use \c std::fill instead. - - This is the same as qFill(\a{container}.begin(), \a{container}.end(), \a value); -*/ - -/*! \fn template <typename InputIterator, typename T> InputIterator qFind(InputIterator begin, InputIterator end, const T &value) - \relates <QtAlgorithms> - \deprecated - - Use \c std::find instead. - - 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 code/doc_src_qalgorithms.cpp 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 template <typename Container, typename T> void qFind(const Container &container, const T &value) - \relates <QtAlgorithms> - \deprecated - \overload - - Use \c std::find instead. - - This is the same as qFind(\a{container}.constBegin(), \a{container}.constEnd(), \a value); -*/ - -/*! \fn template <typename InputIterator, typename T, typename Size> void qCount(InputIterator begin, InputIterator end, const T &value, Size &n) - \relates <QtAlgorithms> - \deprecated - - Use \c std::count instead. - - 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 code/doc_src_qalgorithms.cpp 9 - - This function requires the item type (in the example above, - \c int) to implement \c operator==(). - - \sa {input iterators} -*/ - -/*! \fn template <typename Container, typename T, typename Size> void qCount(const Container &container, const T &value, Size &n) - \relates <QtAlgorithms> - \deprecated - \overload - - Use \c std::count instead. - - 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 template <typename T> void qSwap(T &var1, T &var2) - \relates <QtAlgorithms> - \deprecated - - Use \c std::swap instead. - - Exchanges the values of variables \a var1 and \a var2. - - Example: - \snippet code/doc_src_qalgorithms.cpp 10 -*/ - -/*! \fn template <typename RandomAccessIterator> void qSort(RandomAccessIterator begin, RandomAccessIterator end) - \relates <QtAlgorithms> - \deprecated - - Use \c std::sort instead. - - Sorts the items in range [\a begin, \a end) in ascending order - using the quicksort algorithm. - - Example: - \snippet code/doc_src_qalgorithms.cpp 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 template <typename RandomAccessIterator, typename LessThan> void qSort(RandomAccessIterator begin, RandomAccessIterator end, LessThan lessThan) - \relates <QtAlgorithms> - \deprecated - \overload - - Use \c std::sort instead. - - 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 code/doc_src_qalgorithms.cpp 12 - - To sort values in reverse order, pass - \l{qGreater()}{qGreater<T>()} as the \a lessThan parameter. For - example: - - \snippet code/doc_src_qalgorithms.cpp 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 code/doc_src_qalgorithms.cpp 14 - - \sa QMap -*/ - -/*! \fn template<typename Container> void qSort(Container &container) - \relates <QtAlgorithms> - \deprecated - \overload - - Use \c std::sort instead. - - This is the same as qSort(\a{container}.begin(), \a{container}.end()); -*/ - -/*! - \fn template <typename RandomAccessIterator> void qStableSort(RandomAccessIterator begin, RandomAccessIterator end) - \relates <QtAlgorithms> - \deprecated - - Use \c std::stable_sort instead. - - 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 code/doc_src_qalgorithms.cpp 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 template <typename RandomAccessIterator, typename LessThan> void qStableSort(RandomAccessIterator begin, RandomAccessIterator end, LessThan lessThan) - \relates <QtAlgorithms> - \deprecated - \overload - - Use \c std::stable_sort instead. - - 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 code/doc_src_qalgorithms.cpp 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 code/doc_src_qalgorithms.cpp 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 template <typename Container> void qStableSort(Container &container) - \relates <QtAlgorithms> - \deprecated - \overload - - Use \c std::stable_sort instead. - - This is the same as qStableSort(\a{container}.begin(), \a{container}.end()); -*/ - -/*! \fn template <typename RandomAccessIterator, typename T> RandomAccessIterator qLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value) - \relates <QtAlgorithms> - \deprecated - - Use \c std::lower_bound instead. - - Performs a binary search of the range [\a begin, \a end) and - returns the position of the first occurrence 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 code/doc_src_qalgorithms.cpp 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 code/doc_src_qalgorithms.cpp 19 - - \sa qUpperBound(), qBinaryFind() -*/ - -/*! - \fn template <typename RandomAccessIterator, typename T, typename LessThan> RandomAccessIterator qLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan) - \relates <QtAlgorithms> - \deprecated - \overload - - Use \c std::lower_bound instead. - - 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 template <typename Container, typename T> void qLowerBound(const Container &container, const T &value) - \relates <QtAlgorithms> - \deprecated - \overload - - Use \c std::lower_bound instead. - - 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 template <typename RandomAccessIterator, typename T> RandomAccessIterator qUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value) - \relates <QtAlgorithms> - \deprecated - - Use \c std::upper_bound instead. - - 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 code/doc_src_qalgorithms.cpp 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 code/doc_src_qalgorithms.cpp 21 - - \sa qLowerBound(), qBinaryFind() -*/ - -/*! - \fn template <typename RandomAccessIterator, typename T, typename LessThan> RandomAccessIterator qUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan) - \relates <QtAlgorithms> - \deprecated - \overload - - Use \c std::upper_bound instead. - - 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 template <typename Container, typename T> void qUpperBound(const Container &container, const T &value) - \relates <QtAlgorithms> - \deprecated - \overload - - Use \c std::upper_bound instead. - - This is the same as qUpperBound(\a{container}.begin(), \a{container}.end(), \a value); -*/ - - -/*! \fn template <typename RandomAccessIterator, typename T> RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value) - \relates <QtAlgorithms> - \deprecated - - Use \c std::binary_search or \c std::lower_bound instead. - - 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 code/doc_src_qalgorithms.cpp 22 - - This function requires the item type (in the example above, - QString) to implement \c operator<(). - - \sa qLowerBound(), qUpperBound(), {random access iterators} -*/ - -/*! \fn template <typename RandomAccessIterator, typename T, typename LessThan> RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan) - \relates <QtAlgorithms> - \deprecated - \overload - - Use \c std::binary_search or \c std::lower_bound instead. - - 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 template <typename Container, typename T> void qBinaryFind(const Container &container, const T &value) - \relates <QtAlgorithms> - \deprecated - \overload - - Use \c std::binary_search or \c std::lower_bound instead. - - This is the same as qBinaryFind(\a{container}.begin(), \a{container}.end(), \a value); -*/ - - /*! \fn template <typename ForwardIterator> void qDeleteAll(ForwardIterator begin, ForwardIterator end) \relates <QtAlgorithms> @@ -701,7 +118,7 @@ example, \c{QWidget *}). Example: - \snippet code/doc_src_qalgorithms.cpp 23 + \snippet code/doc_src_qalgorithms.cpp 1 Notice that qDeleteAll() doesn't remove the items from the container; it merely calls \c delete on them. In the example @@ -724,39 +141,6 @@ This is the same as qDeleteAll(\a{c}.begin(), \a{c}.end()). */ -/*! \fn template <typename LessThan> LessThan qLess() - \relates <QtAlgorithms> - \deprecated - - Use \c std::less instead. - - Returns a functional object, or functor, that can be passed to qSort() - or qStableSort(). - - Example: - - \snippet code/doc_src_qalgorithms.cpp 24 - - \sa {qGreater()}{qGreater<T>()} -*/ - -/*! \fn template <typename LessThan> LessThan qGreater() - \relates <QtAlgorithms> - \deprecated - - Use \c std::greater instead. - - Returns a functional object, or functor, that can be passed to qSort() - or qStableSort(). - - Example: - - \snippet code/doc_src_qalgorithms.cpp 25 - - \sa {qLess()}{qLess<T>()} -*/ - - /*! \fn uint qPopulationCount(quint8 v) \relates <QtAlgorithms> |