1// Copyright (C) 2016 The Qt Company Ltd.
2// SPDX-License-Identifier: LicenseRef-Qt-Commercial OR GFDL-1.3-no-invariants-only
5 \headerfile <QtAlgorithms>
7 \title Generic Algorithms
9 \keyword generic algorithms
11 \brief The <QtAlgorithms> header includes the generic, template-based algorithms.
13 Qt provides a number of global template functions in \c
14 <QtAlgorithms> that work on containers and perform small tasks to
15 make life easier, such as qDeleteAll(), which invokes \c{operator delete}
16 on all items in a given container or in a given range.
17 You can use these algorithms with any \l {container
18 class} that provides STL-style iterators, including Qt's QList,
19 QMap, and QHash classes.
21 Most algorithms take \l {STL-style iterators} as parameters. The
22 algorithms are generic in the sense that they aren't bound to a
23 specific iterator class; you can use them with any iterators that
24 meet a certain set of requirements.
26 Different algorithms can have different requirements for the
27 iterators they accept. The iterator types required are specified
28 for each algorithm. If an iterator of the wrong type is passed (for
29 example, if QList::ConstIterator is passed as an
30 \l {Output Iterators}{output iterator}), you will always get a
31 compiler error, although not necessarily a very informative one.
33 Some algorithms have special requirements on the value type stored
34 in the containers. For example, qDeleteAll() requires that the
35 value type is a non-const pointer type (for example, QWidget
36 *). The value type requirements are specified for each algorithm,
37 and the compiler will produce an error if a requirement isn't met.
39 The generic algorithms can be used on other container classes
40 than those provided by Qt and STL. The syntax of STL-style
41 iterators is modeled after C++ pointers, so it's possible to use
42 plain arrays as containers and plain pointers as iterators.
44 \section1 Types of Iterators
46 The algorithms have certain requirements on the iterator types
47 they accept, and these are specified individually for each
48 function. The compiler will produce an error if a requirement
51 \section2 Input Iterators
53 An \e{input iterator} is an iterator that can be used for reading
54 data sequentially from a container. It must provide the following
55 operators: \c{==} and \c{!=} for comparing two iterators, unary
56 \c{*} for retrieving the value stored in the item, and prefix
57 \c{++} for advancing to the next item.
59 The Qt containers' iterator types (const and non-const) are all
62 \section2 Output Iterators
64 An output iterator is an iterator that can be used for
65 writing data sequentially to a container or to some output
66 stream. It must provide the following operators: unary \c{*} for
67 writing a value (i.e., \c{*it = val}) and prefix \c{++} for
68 advancing to the next item.
70 The Qt containers' non-const iterator types are all output
73 \section2 Forward Iterators
75 A \e{forward iterator} is an iterator that meets the requirements
76 of both input iterators and output iterators.
78 The Qt containers' non-const iterator types are all forward
81 \section2 Bidirectional Iterators
83 A \e{bidirectional iterator} is an iterator that meets the
84 requirements of forward iterators but that in addition supports
85 prefix \c{--} for iterating backward.
87 The Qt containers' non-const iterator types are all bidirectional
90 \section2 Random Access Iterators
92 The last category, \e{random access iterators}, is the most
93 powerful type of iterator. It supports all the requirements of a
94 bidirectional iterator, and supports the following operations:
97 \row \li \c{i += n} \li advances iterator \c i by \c n positions
98 \row \li \c{i -= n} \li moves iterator \c i back by \c n positions
99 \row \li \c{i + n} or \c{n + i} \li returns the iterator for the item \c
100 n positions ahead of iterator \c i
101 \row \li \c{i - n} \li returns the iterator for the item \c n positions behind of iterator \c i
102 \row \li \c{i - j} \li returns the number of items between iterators \c i and \c j
103 \row \li \c{i[n]} \li same as \c{*(i + n)}
104 \row \li \c{i < j} \li returns \c true if iterator \c j comes after iterator \c i
107 QList's non-const iterator type is random access iterator.
109 \sa {container classes}, <QtGlobal>
113 \fn template <typename ForwardIterator> void qDeleteAll(ForwardIterator begin, ForwardIterator end)
114 \relates <QtAlgorithms>
116 Deletes all the items in the range [\a begin, \a end) using the
117 C++ \c delete operator. The item type must be a pointer type (for
118 example, \c{QWidget *}).
121 \snippet code/doc_src_qalgorithms.cpp 1
123 Notice that qDeleteAll() doesn't remove the items from the
124 container; it merely calls \c delete on them. In the example
125 above, we call clear() on the container to remove the items.
127 This function can also be used to delete items stored in
128 associative containers, such as QMap and QHash. Only the objects
129 stored in each container will be deleted by this function; objects
130 used as keys will not be deleted.
132 \sa {forward iterators}
136 \fn template <typename Container> void qDeleteAll(const Container &c)
137 \relates <QtAlgorithms>
141 This is the same as qDeleteAll(\a{c}.begin(), \a{c}.end()).
145 \fn uint qPopulationCount(quint8 v)
146 \relates <QtAlgorithms>
149 Returns the number of bits set in \a v. This number is also called
150 the Hamming Weight of \a v.
154 \fn uint qPopulationCount(quint16 v)
155 \relates <QtAlgorithms>
161 \fn uint qPopulationCount(quint32 v)
162 \relates <QtAlgorithms>
168 \fn uint qPopulationCount(quint64 v)
169 \relates <QtAlgorithms>
175 \fn uint qCountTrailingZeroBits(quint8 v)
176 \relates <QtAlgorithms>
179 Returns the number of consecutive zero bits in \a v, when searching from the LSB.
180 For example, qCountTrailingZeroBits(1) returns 0 and qCountTrailingZeroBits(8) returns 3.
184 \fn uint qCountTrailingZeroBits(quint16 v)
185 \relates <QtAlgorithms>
191 \fn uint qCountTrailingZeroBits(quint32 v)
192 \relates <QtAlgorithms>
198 \fn uint qCountTrailingZeroBits(quint64 v)
199 \relates <QtAlgorithms>
205 \fn uint qCountLeadingZeroBits(quint8 v)
206 \relates <QtAlgorithms>
209 Returns the number of consecutive zero bits in \a v, when searching from the MSB.
210 For example, qCountLeadingZeroBits(quint8(1)) returns 7 and
211 qCountLeadingZeroBits(quint8(8)) returns 4.
215 \fn uint qCountLeadingZeroBits(quint16 v)
216 \relates <QtAlgorithms>
219 Returns the number of consecutive zero bits in \a v, when searching from the MSB.
220 For example, qCountLeadingZeroBits(quint16(1)) returns 15 and
221 qCountLeadingZeroBits(quint16(8)) returns 12.
225 \fn uint qCountLeadingZeroBits(quint32 v)
226 \relates <QtAlgorithms>
229 Returns the number of consecutive zero bits in \a v, when searching from the MSB.
230 For example, qCountLeadingZeroBits(quint32(1)) returns 31 and
231 qCountLeadingZeroBits(quint32(8)) returns 28.
235 \fn uint qCountLeadingZeroBits(quint64 v)
236 \relates <QtAlgorithms>
239 Returns the number of consecutive zero bits in \a v, when searching from the MSB.
240 For example, qCountLeadingZeroBits(quint64(1)) returns 63 and
241 qCountLeadingZeroBits(quint64(8)) returns 60.