ceph/src/boost/libs/algorithm/doc/ordered-hpp.qbk

   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]