]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | [/ QuickBook Document version 1.5 ] |
2 | [section:is_sorted is_sorted ] | |
3 | ||
4 | [/license | |
5 | ||
6 | Copyright (c) 2010-2012 Marshall Clow | |
7 | ||
8 | Distributed under the Boost Software License, Version 1.0. | |
9 | (See accompanying file LICENSE_1_0.txt or copy at | |
10 | http://www.boost.org/LICENSE_1_0.txt) | |
11 | ||
12 | ] | |
13 | ||
14 | ||
15 | The header file `<boost/algorithm/cxx11/is_sorted.hpp>` contains functions for determining if a sequence is ordered. | |
16 | ||
17 | [heading is_sorted] | |
18 | The function `is_sorted(sequence)` determines whether or not a sequence is completely sorted according so some criteria. If no comparison predicate is specified, then std::less_equal is used (i.e, the test is to see if the sequence is non-decreasing) | |
19 | ||
20 | `` | |
21 | namespace boost { namespace algorithm { | |
22 | template <typename ForwardIterator, typename Pred> | |
23 | bool is_sorted ( ForwardIterator first, ForwardIterator last, Pred p ); | |
24 | ||
25 | template <typename ForwardIterator> | |
26 | bool is_sorted ( ForwardIterator first, ForwardIterator last ); | |
27 | ||
28 | ||
29 | template <typename Range, typename Pred> | |
30 | bool is_sorted ( const Range &r, Pred p ); | |
31 | ||
32 | template <typename Range> | |
33 | bool is_sorted ( const Range &r ); | |
34 | }} | |
35 | `` | |
36 | ||
37 | Iterator requirements: The `is_sorted` functions will work forward iterators or better. | |
38 | ||
39 | [heading is_sorted_until] | |
40 | ||
41 | If `distance(first, last) < 2`, then `is_sorted ( first, last )` returns `last`. Otherwise, it returns the last iterator i in [first,last] for which the range [first,i) is sorted. | |
42 | ||
43 | In short, it returns the element in the sequence that is "out of order". If the entire sequence is sorted (according to the predicate), then it will return `last`. | |
44 | ||
45 | `` | |
46 | namespace boost { namespace algorithm { | |
47 | template <typename ForwardIterator, typename Pred> | |
48 | FI is_sorted_until ( ForwardIterator first, ForwardIterator last, Pred p ); | |
49 | ||
50 | template <typename ForwardIterator> | |
51 | ForwardIterator is_sorted_until ( ForwardIterator first, ForwardIterator last ); | |
52 | ||
53 | ||
54 | template <typename Range, typename Pred> | |
55 | typename boost::range_iterator<const R>::type is_sorted_until ( const Range &r, Pred p ); | |
56 | ||
57 | template <typename Range> | |
58 | typename boost::range_iterator<const R>::type is_sorted_until ( const Range &r ); | |
59 | }} | |
60 | `` | |
61 | ||
62 | Iterator requirements: The `is_sorted_until` functions will work on forward iterators or better. Since they have to return a place in the input sequence, input iterators will not suffice. | |
63 | ||
64 | Complexity: | |
65 | `is_sorted_until` will make at most ['N-1] calls to the predicate (given a sequence of length ['N]). | |
66 | ||
67 | Examples: | |
68 | ||
69 | Given the sequence `{ 1, 2, 3, 4, 5, 3 }`, `is_sorted_until ( beg, end, std::less<int>())` would return an iterator pointing at the second `3`. | |
70 | ||
71 | Given the sequence `{ 1, 2, 3, 4, 5, 9 }`, `is_sorted_until ( beg, end, std::less<int>())` would return `end`. | |
72 | ||
73 | ||
74 | There are also a set of "wrapper functions" for is_ordered which make it easy to see if an entire sequence is ordered. These functions return a boolean indicating success or failure rather than an iterator to where the out of order items were found. | |
75 | ||
76 | To test if a sequence is increasing (each element at least as large as the preceding one): | |
77 | `` | |
78 | namespace boost { namespace algorithm { | |
79 | template <typename Iterator> | |
80 | bool is_increasing ( Iterator first, Iterator last ); | |
81 | ||
82 | template <typename R> | |
83 | bool is_increasing ( const R &range ); | |
84 | }} | |
85 | `` | |
86 | ||
87 | To test if a sequence is decreasing (each element no larger than the preceding one): | |
88 | ||
89 | `` | |
90 | namespace boost { namespace algorithm { | |
91 | template <typename ForwardIterator> | |
92 | bool is_decreasing ( ForwardIterator first, ForwardIterator last ); | |
93 | ||
94 | template <typename R> | |
95 | bool is_decreasing ( const R &range ); | |
96 | }} | |
97 | `` | |
98 | ||
99 | To test if a sequence is strictly increasing (each element larger than the preceding one): | |
100 | `` | |
101 | namespace boost { namespace algorithm { | |
102 | template <typename ForwardIterator> | |
103 | bool is_strictly_increasing ( ForwardIterator first, ForwardIterator last ); | |
104 | ||
105 | template <typename R> | |
106 | bool is_strictly_increasing ( const R &range ); | |
107 | }} | |
108 | `` | |
109 | ||
110 | To test if a sequence is strictly decreasing (each element smaller than the preceding one): | |
111 | `` | |
112 | namespace boost { namespace algorithm { | |
113 | template <typename ForwardIterator> | |
114 | bool is_strictly_decreasing ( ForwardIterator first, ForwardIterator last ); | |
115 | ||
116 | template <typename R> | |
117 | bool is_strictly_decreasing ( const R &range ); | |
118 | }} | |
119 | `` | |
120 | ||
121 | Complexity: | |
122 | Each of these calls is just a thin wrapper over `is_sorted`, so they have the same complexity as `is_sorted`. | |
123 | ||
124 | [heading Notes] | |
125 | ||
126 | * The routines `is_sorted` and `is_sorted_until` are part of the C++11 standard. When compiled using a C++11 implementation, the implementation from the standard library will be used. | |
127 | ||
128 | * `is_sorted` and `is_sorted_until` both return true for empty ranges and ranges of length one. | |
129 | ||
130 | [endsect] |