1[/ QuickBook Document version 1.5 ] 2[section:is_sorted is_sorted ] 3 4[/license 5 6Copyright (c) 2010-2012 Marshall Clow 7 8Distributed under the Boost Software License, Version 1.0. 9(See accompanying file LICENSE_1_0.txt or copy at 10http://www.boost.org/LICENSE_1_0.txt) 11 12] 13 14 15The header file `<boost/algorithm/cxx11/is_sorted.hpp>` contains functions for determining if a sequence is ordered. 16 17[heading is_sorted] 18The 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` is used (i.e, the test is to see if the sequence is non-decreasing) 19 20`` 21namespace 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 37Iterator requirements: The `is_sorted` functions will work forward iterators or better. 38 39[heading is_sorted_until] 40 41If `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 43In 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`` 46namespace 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 62Iterator 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 64Complexity: 65 `is_sorted_until` will make at most ['N-1] calls to the predicate (given a sequence of length ['N]). 66 67Examples: 68 69Given 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 71Given the sequence `{ 1, 2, 3, 4, 5, 9 }`, `is_sorted_until ( beg, end, std::less<int>())` would return `end`. 72 73 74There 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 76To test if a sequence is increasing (each element at least as large as the preceding one): 77`` 78namespace 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 87To test if a sequence is decreasing (each element no larger than the preceding one): 88 89`` 90namespace 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 99To test if a sequence is strictly increasing (each element larger than the preceding one): 100`` 101namespace 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 110To test if a sequence is strictly decreasing (each element smaller than the preceding one): 111`` 112namespace 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 121Complexity: 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] 131