author | eckhart.koppen@nokia.com |
Wed, 31 Mar 2010 11:06:36 +0300 | |
changeset 7 | f7bc934e204c |
parent 0 | 1918ee327afb |
child 33 | 3e2da88830cd |
permissions | -rw-r--r-- |
0 | 1 |
/**************************************************************************** |
2 |
** |
|
7
f7bc934e204c
5cabc75a39ca2f064f70b40f72ed93c74c4dc19b
eckhart.koppen@nokia.com
parents:
0
diff
changeset
|
3 |
** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies). |
0 | 4 |
** All rights reserved. |
5 |
** Contact: Nokia Corporation (qt-info@nokia.com) |
|
6 |
** |
|
7 |
** This file is part of the documentation of the Qt Toolkit. |
|
8 |
** |
|
9 |
** $QT_BEGIN_LICENSE:LGPL$ |
|
10 |
** No Commercial Usage |
|
11 |
** This file contains pre-release code and may not be distributed. |
|
12 |
** You may use this file in accordance with the terms and conditions |
|
13 |
** contained in the Technology Preview License Agreement accompanying |
|
14 |
** this package. |
|
15 |
** |
|
16 |
** GNU Lesser General Public License Usage |
|
17 |
** Alternatively, this file may be used under the terms of the GNU Lesser |
|
18 |
** General Public License version 2.1 as published by the Free Software |
|
19 |
** Foundation and appearing in the file LICENSE.LGPL included in the |
|
20 |
** packaging of this file. Please review the following information to |
|
21 |
** ensure the GNU Lesser General Public License version 2.1 requirements |
|
22 |
** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. |
|
23 |
** |
|
24 |
** In addition, as a special exception, Nokia gives you certain additional |
|
25 |
** rights. These rights are described in the Nokia Qt LGPL Exception |
|
26 |
** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. |
|
27 |
** |
|
28 |
** If you have questions regarding the use of this file, please contact |
|
29 |
** Nokia at qt-info@nokia.com. |
|
30 |
** |
|
31 |
** |
|
32 |
** |
|
33 |
** |
|
34 |
** |
|
35 |
** |
|
36 |
** |
|
37 |
** |
|
38 |
** $QT_END_LICENSE$ |
|
39 |
** |
|
40 |
****************************************************************************/ |
|
41 |
||
42 |
/*! |
|
43 |
\headerfile <QtAlgorithms> |
|
44 |
\title Generic Algorithms |
|
45 |
\ingroup funclists |
|
46 |
||
47 |
\brief The <QtAlgorithms> header includes the 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 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 &) 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 |
||
308 |
Instead of operating on iterators, as in the other overload, this function |
|
309 |
operates on the specified \a container to obtain the number of instances |
|
310 |
of \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 |
|
359 |
example: |
|
360 |
||
361 |
\snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 13 |
|
362 |
||
363 |
If neither of the two items is "less than" the other, the items are |
|
364 |
taken to be equal. It is then undefined which one of the two |
|
365 |
items will appear before the other after the sort. |
|
366 |
||
367 |
An alternative to using qSort() is to put the items to sort in a |
|
368 |
QMap, using the sort key as the QMap key. This is often more |
|
369 |
convenient than defining a \a lessThan function. For example, the |
|
370 |
following code shows how to sort a list of strings case |
|
371 |
insensitively using QMap: |
|
372 |
||
373 |
\snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 14 |
|
374 |
||
375 |
\sa QMap |
|
376 |
*/ |
|
377 |
||
378 |
/*! \fn void qSort(Container &container) |
|
379 |
\relates <QtAlgorithms> |
|
380 |
||
381 |
\overload |
|
382 |
||
383 |
This is the same as qSort(\a{container}.begin(), \a{container}.end()); |
|
384 |
*/ |
|
385 |
||
386 |
/*! |
|
387 |
\fn void qStableSort(RandomAccessIterator begin, RandomAccessIterator end) |
|
388 |
\relates <QtAlgorithms> |
|
389 |
||
390 |
Sorts the items in range [\a begin, \a end) in ascending order |
|
391 |
using a stable sorting algorithm. |
|
392 |
||
393 |
If neither of the two items is "less than" the other, the items are |
|
394 |
taken to be equal. The item that appeared before the other in the |
|
395 |
original container will still appear first after the sort. This |
|
396 |
property is often useful when sorting user-visible data. |
|
397 |
||
398 |
Example: |
|
399 |
\snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 15 |
|
400 |
||
401 |
The sort algorithm is efficient on large data sets. It operates |
|
402 |
in \l {linear-logarithmic time}, O(\e{n} log \e{n}). |
|
403 |
||
404 |
This function requires the item type (in the example above, |
|
405 |
\c{int}) to implement \c operator<(). |
|
406 |
||
407 |
\sa qSort(), {random access iterators} |
|
408 |
*/ |
|
409 |
||
410 |
/*! |
|
411 |
\fn void qStableSort(RandomAccessIterator begin, RandomAccessIterator end, LessThan lessThan) |
|
412 |
\relates <QtAlgorithms> |
|
413 |
||
414 |
\overload |
|
415 |
||
416 |
Uses the \a lessThan function instead of \c operator<() to |
|
417 |
compare the items. |
|
418 |
||
419 |
For example, here's how to sort the strings in a QStringList |
|
420 |
in case-insensitive alphabetical order: |
|
421 |
||
422 |
\snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 16 |
|
423 |
||
424 |
Note that earlier versions of Qt allowed using a lessThan function that took its |
|
425 |
arguments by non-const reference. From 4.3 and on this is no longer possible, |
|
426 |
the arguments has to be passed by const reference or value. |
|
427 |
||
428 |
To sort values in reverse order, pass |
|
429 |
\l{qGreater()}{qGreater<T>()} as the \a lessThan parameter. For |
|
430 |
example: |
|
431 |
||
432 |
\snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 17 |
|
433 |
||
434 |
If neither of the two items is "less than" the other, the items are |
|
435 |
taken to be equal. The item that appeared before the other in the |
|
436 |
original container will still appear first after the sort. This |
|
437 |
property is often useful when sorting user-visible data. |
|
438 |
*/ |
|
439 |
||
440 |
/*! |
|
441 |
\fn void qStableSort(Container &container) |
|
442 |
\relates <QtAlgorithms> |
|
443 |
||
444 |
\overload |
|
445 |
||
446 |
This is the same as qStableSort(\a{container}.begin(), \a{container}.end()); |
|
447 |
*/ |
|
448 |
||
449 |
/*! \fn RandomAccessIterator qLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value) |
|
450 |
\relates <QtAlgorithms> |
|
451 |
||
452 |
Performs a binary search of the range [\a begin, \a end) and |
|
453 |
returns the position of the first ocurrence of \a value. If no |
|
454 |
such item is found, returns the position where it should be |
|
455 |
inserted. |
|
456 |
||
457 |
The items in the range [\a begin, \e end) must be sorted in |
|
458 |
ascending order; see qSort(). |
|
459 |
||
460 |
Example: |
|
461 |
\snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 18 |
|
462 |
||
463 |
This function requires the item type (in the example above, |
|
464 |
\c{int}) to implement \c operator<(). |
|
465 |
||
466 |
qLowerBound() can be used in conjunction with qUpperBound() to |
|
467 |
iterate over all occurrences of the same value: |
|
468 |
||
469 |
\snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 19 |
|
470 |
||
471 |
\sa qUpperBound(), qBinaryFind() |
|
472 |
*/ |
|
473 |
||
474 |
/*! |
|
475 |
\fn RandomAccessIterator qLowerBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan) |
|
476 |
\relates <QtAlgorithms> |
|
477 |
||
478 |
\overload |
|
479 |
||
480 |
Uses the \a lessThan function instead of \c operator<() to |
|
481 |
compare the items. |
|
482 |
||
483 |
Note that the items in the range must be sorted according to the order |
|
484 |
specified by the \a lessThan object. |
|
485 |
*/ |
|
486 |
||
487 |
/*! |
|
488 |
\fn void qLowerBound(const Container &container, const T &value) |
|
489 |
\relates <QtAlgorithms> |
|
490 |
||
491 |
\overload |
|
492 |
||
493 |
For read-only iteration over containers, this function is broadly equivalent to |
|
494 |
qLowerBound(\a{container}.begin(), \a{container}.end(), value). However, since it |
|
495 |
returns a const iterator, you cannot use it to modify the container; for example, |
|
496 |
to insert items. |
|
497 |
*/ |
|
498 |
||
499 |
/*! \fn RandomAccessIterator qUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value) |
|
500 |
\relates <QtAlgorithms> |
|
501 |
||
502 |
Performs a binary search of the range [\a begin, \a end) and |
|
503 |
returns the position of the one-past-the-last occurrence of \a |
|
504 |
value. If no such item is found, returns the position where the |
|
505 |
item should be inserted. |
|
506 |
||
507 |
The items in the range [\a begin, \e end) must be sorted in |
|
508 |
ascending order; see qSort(). |
|
509 |
||
510 |
Example: |
|
511 |
\snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 20 |
|
512 |
||
513 |
This function requires the item type (in the example above, |
|
514 |
\c{int}) to implement \c operator<(). |
|
515 |
||
516 |
qUpperBound() can be used in conjunction with qLowerBound() to |
|
517 |
iterate over all occurrences of the same value: |
|
518 |
||
519 |
\snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 21 |
|
520 |
||
521 |
\sa qLowerBound(), qBinaryFind() |
|
522 |
*/ |
|
523 |
||
524 |
/*! |
|
525 |
\fn RandomAccessIterator qUpperBound(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan) |
|
526 |
\relates <QtAlgorithms> |
|
527 |
||
528 |
\overload |
|
529 |
||
530 |
Uses the \a lessThan function instead of \c operator<() to |
|
531 |
compare the items. |
|
532 |
||
533 |
Note that the items in the range must be sorted according to the order |
|
534 |
specified by the \a lessThan object. |
|
535 |
*/ |
|
536 |
||
537 |
/*! |
|
538 |
\fn void qUpperBound(const Container &container, const T &value) |
|
539 |
\relates <QtAlgorithms> |
|
540 |
||
541 |
\overload |
|
542 |
||
543 |
This is the same as qUpperBound(\a{container}.begin(), \a{container}.end(), value); |
|
544 |
*/ |
|
545 |
||
546 |
||
547 |
/*! \fn RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value) |
|
548 |
\relates <QtAlgorithms> |
|
549 |
||
550 |
Performs a binary search of the range [\a begin, \a end) and |
|
551 |
returns the position of an occurrence of \a value. If there are |
|
552 |
no occurrences of \a value, returns \a end. |
|
553 |
||
554 |
The items in the range [\a begin, \a end) must be sorted in |
|
555 |
ascending order; see qSort(). |
|
556 |
||
557 |
If there are many occurrences of the same value, any one of them |
|
558 |
could be returned. Use qLowerBound() or qUpperBound() if you need |
|
559 |
finer control. |
|
560 |
||
561 |
Example: |
|
562 |
\snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 22 |
|
563 |
||
564 |
This function requires the item type (in the example above, |
|
565 |
QString) to implement \c operator<(). |
|
566 |
||
567 |
See the \l{<QtAlgorithms>#binaryFind example}{detailed |
|
568 |
description} for an example usage. |
|
569 |
||
570 |
\sa qLowerBound(), qUpperBound(), {random access iterators} |
|
571 |
*/ |
|
572 |
||
573 |
/*! \fn RandomAccessIterator qBinaryFind(RandomAccessIterator begin, RandomAccessIterator end, const T &value, LessThan lessThan) |
|
574 |
\relates <QtAlgorithms> |
|
575 |
||
576 |
\overload |
|
577 |
||
578 |
Uses the \a lessThan function instead of \c operator<() to |
|
579 |
compare the items. |
|
580 |
||
581 |
Note that the items in the range must be sorted according to the order |
|
582 |
specified by the \a lessThan object. |
|
583 |
*/ |
|
584 |
||
585 |
/*! |
|
586 |
\fn void qBinaryFind(const Container &container, const T &value) |
|
587 |
\relates <QtAlgorithms> |
|
588 |
||
589 |
\overload |
|
590 |
||
591 |
This is the same as qBinaryFind(\a{container}.begin(), \a{container}.end(), value); |
|
592 |
*/ |
|
593 |
||
594 |
||
595 |
/*! |
|
596 |
\fn void qDeleteAll(ForwardIterator begin, ForwardIterator end) |
|
597 |
\relates <QtAlgorithms> |
|
598 |
||
599 |
Deletes all the items in the range [\a begin, \a end) using the |
|
600 |
C++ \c delete operator. The item type must be a pointer type (for |
|
601 |
example, \c{QWidget *}). |
|
602 |
||
603 |
Example: |
|
604 |
\snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 23 |
|
605 |
||
606 |
Notice that qDeleteAll() doesn't remove the items from the |
|
607 |
container; it merely calls \c delete on them. In the example |
|
608 |
above, we call clear() on the container to remove the items. |
|
609 |
||
610 |
This function can also be used to delete items stored in |
|
611 |
associative containers, such as QMap and QHash. Only the objects |
|
612 |
stored in each container will be deleted by this function; objects |
|
613 |
used as keys will not be deleted. |
|
614 |
||
615 |
\sa {forward iterators} |
|
616 |
*/ |
|
617 |
||
618 |
/*! |
|
619 |
\fn void qDeleteAll(const Container &c) |
|
620 |
\relates <QtAlgorithms> |
|
621 |
||
622 |
\overload |
|
623 |
||
624 |
This is the same as qDeleteAll(\a{c}.begin(), \a{c}.end()). |
|
625 |
*/ |
|
626 |
||
627 |
/*! \fn LessThan qLess() |
|
628 |
\relates <QtAlgorithms> |
|
629 |
||
630 |
Returns a functional object, or functor, that can be passed to qSort() |
|
631 |
or qStableSort(). |
|
632 |
||
633 |
Example: |
|
634 |
||
635 |
\snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 24 |
|
636 |
||
637 |
\sa {qGreater()}{qGreater<T>()} |
|
638 |
*/ |
|
639 |
||
640 |
/*! \fn LessThan qGreater() |
|
641 |
\relates <QtAlgorithms> |
|
642 |
||
643 |
Returns a functional object, or functor, that can be passed to qSort() |
|
644 |
or qStableSort(). |
|
645 |
||
646 |
Example: |
|
647 |
||
648 |
\snippet doc/src/snippets/code/doc_src_qalgorithms.qdoc 25 |
|
649 |
||
650 |
\sa {qLess()}{qLess<T>()} |
|
651 |
*/ |