source: trunk/doc/src/qalgorithms.qdoc@ 172

Last change on this file since 172 was 2, checked in by Dmitry A. Kuminov, 16 years ago

Initially imported qt-all-opensource-src-4.5.1 from Trolltech.

File size: 22.1 KB
Line 
1/****************************************************************************
2**
3** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
4** Contact: Qt Software Information ([email protected])
5**
6** This file is part of the documentation of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial Usage
10** Licensees holding valid Qt Commercial licenses may use this file in
11** accordance with the Qt Commercial License Agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and Nokia.
14**
15** GNU Lesser General Public License Usage
16** Alternatively, this file may be used under the terms of the GNU Lesser
17** General Public License version 2.1 as published by the Free Software
18** Foundation and appearing in the file LICENSE.LGPL included in the
19** packaging of this file. Please review the following information to
20** ensure the GNU Lesser General Public License version 2.1 requirements
21** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
22**
23** In addition, as a special exception, Nokia gives you certain
24** additional rights. These rights are described in the Nokia Qt LGPL
25** Exception version 1.0, included in the file LGPL_EXCEPTION.txt in this
26** package.
27**
28** GNU General Public License Usage
29** Alternatively, this file may be used under the terms of the GNU
30** General Public License version 3.0 as published by the Free Software
31** Foundation and appearing in the file LICENSE.GPL included in the
32** packaging of this file. Please review the following information to
33** ensure the GNU General Public License version 3.0 requirements will be
34** met: http://www.gnu.org/copyleft/gpl.html.
35**
36** If you are unsure which license is appropriate for your use, please
37** contact the sales department at [email protected].
38** $QT_END_LICENSE$
39**
40****************************************************************************/
41
42/*!
43 \headerfile <QtAlgorithms>
44 \title Generic Algorithms
45 \ingroup architecture
46
47 \brief The <QtAlgorithms> header provides generic template-based algorithms.
48
49 Qt provides a number of global template functions in \c
50 <QtAlgorithms> that work on containers and perform well-know
51 algorithms. You can use these algorithms with any \l {container
52 class} that provides STL-style iterators, including Qt's QList,
53 QLinkedList, QVector, QMap, and QHash classes.
54
55 These functions have taken their inspiration from similar
56 functions available in the STL \c <algorithm> header. Most of them
57 have a direct STL equivalent; for example, qCopyBackward() is the
58 same as STL's copy_backward() algorithm.
59
60 If STL is available on all your target platforms, you can use the
61 STL algorithms instead of their Qt counterparts. One reason why
62 you might want to use the the STL algorithms is that STL provides
63 dozens and dozens of algorithms, whereas Qt only provides the most
64 important ones, making no attempt to duplicate functionality that
65 is already provided by the C++ standard.
66
67 Most algorithms take \l {STL-style iterators} as parameters. The
68 algorithms are generic in the sense that they aren't bound to a
69 specific iterator class; you can use them with any iterators that
70 meet a certain set of requirements.
71
72 Let's take the qFill() algorithm as an example. Unlike QVector,
73 QList has no fill() function that can be used to fill a list with
74 a particular value. If you need that functionality, you can use
75 qFill():
76
77 \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 0
78
79 qFill() takes a begin iterator, an end iterator, and a value.
80 In the example above, we pass \c list.begin() and \c list.end()
81 as the begin and end iterators, but this doesn't have to be
82 the case:
83
84 \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 1
85
86 Different algorithms can have different requirements for the
87 iterators they accept. For example, qFill() accepts two
88 \l {forward iterators}. The iterator types required are specified
89 for each algorithm. If an iterator of the wrong type is passed (for
90 example, if QList::ConstIterator is passed as an \l {output
91 iterator}), you will always get a compiler error, although not
92 necessarily a very informative one.
93
94 Some algorithms have special requirements on the value type
95 stored in the containers. For example, qEqual() requires that the
96 value type supports operator==(), which it uses to compare items.
97 Similarly, qDeleteAll() requires that the value type is a
98 non-const pointer type (for example, QWidget *). The value type
99 requirements are specified for each algorithm, and the compiler
100 will produce an error if a requirement isn't met.
101
102 \target binaryFind example
103
104 The generic algorithms can be used on other container classes
105 than those provided by Qt and STL. The syntax of STL-style
106 iterators is modeled after C++ pointers, so it's possible to use
107 plain arrays as containers and plain pointers as iterators. A
108 common idiom is to use qBinaryFind() together with two static
109 arrays: one that contains a list of keys, and another that
110 contains a list of associated values. For example, the following
111 code will look up an HTML entity (e.g., \c &amp;) in the \c
112 name_table array and return the corresponding Unicode value from
113 the \c value_table if the entity is recognized:
114
115 \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 2
116
117 This kind of code is for advanced users only; for most
118 applications, a QMap- or QHash-based approach would work just as
119 well:
120
121 \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 3
122
123 \section1 Types of Iterators
124
125 The algorithms have certain requirements on the iterator types
126 they accept, and these are specified individually for each
127 function. The compiler will produce an error if a requirement
128 isn't met.
129
130 \section2 Input Iterators
131
132 An \e{input iterator} is an iterator that can be used for reading
133 data sequentially from a container. It must provide the following
134 operators: \c{==} and \c{!=} for comparing two iterators, unary
135 \c{*} for retrieving the value stored in the item, and prefix
136 \c{++} for advancing to the next item.
137
138 The Qt containers' iterator types (const and non-const) are all
139 input iterators.
140
141 \section2 Output Iterators
142
143 An \e{output iterator} is an iterator that can be used for
144 writing data sequentially to a container or to some output
145 stream. It must provide the following operators: unary \c{*} for
146 writing a value (i.e., \c{*it = val}) and prefix \c{++} for
147 advancing to the next item.
148
149 The Qt containers' non-const iterator types are all output
150 iterators.
151
152 \section2 Forward Iterators
153
154 A \e{forward iterator} is an iterator that meets the requirements
155 of both input iterators and output iterators.
156
157 The Qt containers' non-const iterator types are all forward
158 iterators.
159
160 \section2 Bidirectional Iterators
161
162 A \e{bidirectional iterator} is an iterator that meets the
163 requirements of forward iterators but that in addition supports
164 prefix \c{--} for iterating backward.
165
166 The Qt containers' non-const iterator types are all bidirectional
167 iterators.
168
169 \section2 Random Access Iterators
170
171 The last category, \e{random access iterators}, is the most
172 powerful type of iterator. It supports all the requirements of a
173 bidirectional iterator, and supports the following operations:
174
175 \table
176 \row \i \c{i += n} \i advances iterator \c i by \c n positions
177 \row \i \c{i -= n} \i moves iterator \c i back by \c n positions
178 \row \i \c{i + n} or \c{n + i} \i returns the iterator for the item \c
179 n positions ahead of iterator \c i
180 \row \i \c{i - n} \i returns the iterator for the item \c n positions behind of iterator \c i
181 \row \i \c{i - j} \i returns the number of items between iterators \c i and \c j
182 \row \i \c{i[n]} \i same as \c{*(i + n)}
183 \row \i \c{i < j} \i returns true if iterator \c j comes after iterator \c i
184 \endtable
185
186 QList and QVector's non-const iterator types are random access iterators.
187
188 \sa {container classes}, <QtGlobal>
189*/
190
191/*! \fn OutputIterator qCopy(InputIterator begin1, InputIterator end1, OutputIterator begin2)
192 \relates <QtAlgorithms>
193
194 Copies the items from range [\a begin1, \a end1) to range [\a
195 begin2, ...), in the order in which they appear.
196
197 The item at position \a begin1 is assigned to that at position \a
198 begin2; the item at position \a begin1 + 1 is assigned to that at
199 position \a begin2 + 1; and so on.
200
201 Example:
202 \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 4
203
204 \sa qCopyBackward(), {input iterators}, {output iterators}
205*/
206
207/*! \fn BiIterator2 qCopyBackward(BiIterator1 begin1, BiIterator1 end1, BiIterator2 end2)
208 \relates <QtAlgorithms>
209
210 Copies the items from range [\a begin1, \a end1) to range [...,
211 \a end2).
212
213 The item at position \a end1 - 1 is assigned to that at position
214 \a end2 - 1; the item at position \a end1 - 2 is assigned to that
215 at position \a end2 - 2; and so on.
216
217 Example:
218 \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 5
219
220 \sa qCopy(), {bidirectional iterators}
221*/
222
223/*! \fn bool qEqual(InputIterator1 begin1, InputIterator1 end1, InputIterator2 begin2)
224 \relates <QtAlgorithms>
225
226 Compares the items in the range [\a begin1, \a end1) with the
227 items in the range [\a begin2, ...). Returns true if all the
228 items compare equal; otherwise returns false.
229
230 Example:
231 \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 6
232
233 This function requires the item type (in the example above,
234 QString) to implement \c operator==().
235
236 \sa {input iterators}
237*/
238
239/*! \fn void qFill(ForwardIterator begin, ForwardIterator end, const T &value)
240 \relates <QtAlgorithms>
241
242 Fills the range [\a begin, \a end) with \a value.
243
244 Example:
245 \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 7
246
247 \sa qCopy(), {forward iterators}
248*/
249
250/*! \fn void qFill(Container &container, const T &value)
251 \relates <QtAlgorithms>
252
253 \overload
254
255 This is the same as qFill(\a{container}.begin(), \a{container}.end(), \a value);
256*/
257
258/*! \fn InputIterator qFind(InputIterator begin, InputIterator end, const T &value)
259 \relates <QtAlgorithms>
260
261 Returns an iterator to the first occurrence of \a value in a
262 container in the range [\a begin, \a end). Returns \a end if \a
263 value isn't found.
264
265 Example:
266 \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 8
267
268 This function requires the item type (in the example above,
269 QString) to implement \c operator==().
270
271 If the items in the range are in ascending order, you can get
272 faster results by using qLowerBound() or qBinaryFind() instead of
273 qFind().
274
275 \sa qBinaryFind(), {input iterators}
276*/
277
278/*! \fn void qFind(const Container &container, const T &value)
279 \relates <QtAlgorithms>
280
281 \overload
282
283 This is the same as qFind(\a{container}.begin(), \a{container}.end(), value);
284*/
285
286/*! \fn void qCount(InputIterator begin, InputIterator end, const T &value, Size &n)
287 \relates <QtAlgorithms>
288
289 Returns the number of occurrences of \a value in the range [\a begin, \a end),
290 which is returned in \a n. \a n is never initialized, the count is added to \a n.
291 It is the caller's responsibility to initialize \a n.
292
293 Example:
294
295 \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 9
296
297 This function requires the item type (in the example above,
298 \c int) to implement \c operator==().
299
300 \sa {input iterators}
301*/
302
303/*! \fn void qCount(const Container &container, const T &value, Size &n)
304\relates <QtAlgorithms>
305
306\overload
307
308Instead of operating on iterators, as in the other overload, this function
309operates on the specified \a container to obtain the number of instances
310of \a value in the variable passed as a reference in argument \a n.
311*/
312
313/*! \fn void qSwap(T &var1, T &var2)
314 \relates <QtAlgorithms>
315
316 Exchanges the values of variables \a var1 and \a var2.
317
318 Example:
319 \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 10
320*/
321
322/*! \fn void qSort(RandomAccessIterator begin, RandomAccessIterator end)
323 \relates <QtAlgorithms>
324
325 Sorts the items in range [\a begin, \a end) in ascending order
326 using the quicksort algorithm.
327
328 Example:
329 \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 11
330
331 The sort algorithm is efficient on large data sets. It operates
332 in \l {linear-logarithmic time}, O(\e{n} log \e{n}).
333
334 This function requires the item type (in the example above,
335 \c{int}) to implement \c operator<().
336
337 If neither of the two items is "less than" the other, the items are
338 taken to be equal. It is then undefined which one of the two
339 items will appear before the other after the sort.
340
341 \sa qStableSort(), {random access iterators}
342*/
343
344/*! \fn void qSort(RandomAccessIterator begin, RandomAccessIterator end, LessThan lessThan)
345 \relates <QtAlgorithms>
346
347 \overload
348
349 Uses the \a lessThan function instead of \c operator<() to
350 compare the items.
351
352 For example, here's how to sort the strings in a QStringList
353 in case-insensitive alphabetical order:
354
355 \snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 12
356
357 To sort values in reverse order, pass
358 \l{qGreater()}{qGreater<T>()} as the \a lessThan parameter. For