ceph/src/boost/libs/range/doc/reference/algorithms.qbk

   1 [/
   2     Copyright 2010 Neil Groves
   3     Distributed under the Boost Software License, Version 1.0.
   4     (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   5 /]
   6 [section:algorithms Range Algorithms]
   7 [section:introduction Introduction and motivation]
   8 In its most simple form a [*Range Algorithm] (or range-based algorithm) is simply an iterator-based algorithm where the /two/ iterator arguments have been replaced by /one/ range argument. For example, we may write
   9
  10 ``
  11 #include <boost/range/algorithm.hpp>
  12 #include <vector>
  13
  14 std::vector<int> vec = ...;
  15 boost::sort(vec);
  16 ``
  17
  18 instead of
  19
  20 ``
  21 std::sort(vec.begin(), vec.end());
  22 ``
  23
  24 However, the return type of range algorithms is almost always different from that of existing iterator-based algorithms.
  25
  26 One group of algorithms, like `boost::sort()`, will simply return the same range so that we can continue to pass the range around and/or further modify it. Because of this we may write
  27 ``
  28 boost:unique(boost::sort(vec));
  29 ``
  30 to first sort the range and then run `unique()` on the sorted range.
  31
  32 Algorithms like `boost::unique()` fall into another group of algorithms that return (potentially) narrowed views of the original range. By default `boost::unique(rng)` returns the range `[boost::begin(rng), found)` where `found` denotes the iterator returned by `std::unique(boost::begin(rng), boost::end(rng))`
  33
  34 Therefore exactly the unique values can be copied by writing
  35 ``
  36 boost::copy(boost::unique(boost::sort(vec)),
  37             std::ostream_iterator<int>(std::cout));
  38 ``
  39
  40 Algorithms like `boost::unique` usually return the range: `[boost::begin(rng), found)`.
  41 However, this behaviour may be changed by supplying a `range_return_value`
  42 as a template parameter to the algorithm:
  43
  44 [table
  45     [[Expression] [Return]]
  46     [[`boost::unique<boost::return_found>(rng)`] [returns a single iterator like `std::unique`]]
  47     [[`boost::unique<boost::return_begin_found>(rng)`] [returns the range `[boost::begin(rng), found)` (this is the default)]]
  48     [[`boost::unique<boost::return_begin_next>(rng)`] [returns the range `[boost::begin(rng), boost::next(found))`]]
  49     [[`boost::unique<boost::return_found_end>(rng)`] [returns the range `[found, boost::end(rng))`]]
  50     [[`boost::unique<boost::return_next_end>(rng)`] [returns the range `[boost::next(found),boost::end(rng))`]]
  51     [[`boost::unique<boost::return_begin_end>(rng)`] [returns the entire original range.]]
  52 ]
  53
  54 This functionality has the following advantages:
  55
  56 # it allows for ['*seamless functional-style programming*] where you do not need to use named local variables to store intermediate results
  57 # it is very ['*safe*] because the algorithm can verify out-of-bounds conditions and handle tricky conditions that lead to empty ranges
  58
  59 For example, consider how easy we may erase the duplicates in a sorted container:
  60
  61 ``
  62 std::vector<int> vec = ...;
  63 boost::erase(vec, boost::unique<boost::return_found_end>(boost::sort(vec)));
  64 ``
  65
  66 Notice the use of `boost::return_found_end`. What if we wanted to erase all the duplicates except one of them? In old-fashioned STL-programming we might write
  67
  68 ``
  69 // assume 'vec' is already sorted
  70 std::vector<int>::iterator i = std::unique(vec.begin(), vec.end());
  71
  72 // remember this check or you get into problems
  73 if (i != vec.end())
  74     ++i;
  75
  76 vec.erase(i, vec.end());
  77 ``
  78
  79 The same task may be accomplished simply with
  80 ``
  81 boost::erase(vec, boost::unique<boost::return_next_end>(vec));
  82 ``
  83 and there is no need to worry about generating an invalid range. Furthermore, if the container is complex, calling `vec.end()` several times will be more expensive than using a range algorithm.
  84
  85 [endsect]
  86
  87 [section:mutating Mutating algorithms]
  88 [include algorithm/copy.qbk]
  89 [include algorithm/copy_backward.qbk]
  90 [include algorithm/fill.qbk]
  91 [include algorithm/fill_n.qbk]
  92 [include algorithm/generate.qbk]
  93 [include algorithm/inplace_merge.qbk]
  94 [include algorithm/merge.qbk]
  95 [include algorithm/nth_element.qbk]
  96 [include algorithm/partial_sort.qbk]
  97 [include algorithm/partition.qbk]
  98 [include algorithm/random_shuffle.qbk]
  99 [include algorithm/remove.qbk]
 100 [include algorithm/remove_copy.qbk]
 101 [include algorithm/remove_copy_if.qbk]
 102 [include algorithm/remove_if.qbk]
 103 [include algorithm/replace.qbk]
 104 [include algorithm/replace_copy.qbk]
 105 [include algorithm/replace_copy_if.qbk]
 106 [include algorithm/replace_if.qbk]
 107 [include algorithm/reverse.qbk]
 108 [include algorithm/reverse_copy.qbk]
 109 [include algorithm/rotate.qbk]
 110 [include algorithm/rotate_copy.qbk]
 111 [include algorithm/sort.qbk]
 112 [include algorithm/stable_partition.qbk]
 113 [include algorithm/stable_sort.qbk]
 114 [include algorithm/swap_ranges.qbk]
 115 [include algorithm/transform.qbk]
 116 [include algorithm/unique.qbk]
 117 [include algorithm/unique_copy.qbk]
 118 [endsect]
 119
 120 [section:non_mutating Non-mutating algorithms]
 121 [include algorithm/adjacent_find.qbk]
 122 [include algorithm/binary_search.qbk]
 123 [include algorithm/count.qbk]
 124 [include algorithm/count_if.qbk]
 125 [include algorithm/equal.qbk]
 126 [include algorithm/equal_range.qbk]
 127 [include algorithm/for_each.qbk]
 128 [include algorithm/find.qbk]
 129 [include algorithm/find_end.qbk]
 130 [include algorithm/find_first_of.qbk]
 131 [include algorithm/find_if.qbk]
 132 [include algorithm/lexicographical_compare.qbk]
 133 [include algorithm/lower_bound.qbk]
 134 [include algorithm/max_element.qbk]
 135 [include algorithm/min_element.qbk]
 136 [include algorithm/mismatch.qbk]
 137 [include algorithm/search.qbk]
 138 [include algorithm/search_n.qbk]
 139 [include algorithm/upper_bound.qbk]
 140 [endsect]
 141
 142 [section:set Set algorithms]
 143 [include algorithm/includes.qbk]
 144 [include algorithm/set_union.qbk]
 145 [include algorithm/set_intersection.qbk]
 146 [include algorithm/set_difference.qbk]
 147 [include algorithm/set_symmetric_difference.qbk]
 148 [endsect]
 149
 150 [section:heap Heap algorithms]
 151 [include algorithm/push_heap.qbk]
 152 [include algorithm/pop_heap.qbk]
 153 [include algorithm/make_heap.qbk]
 154 [include algorithm/sort_heap.qbk]
 155 [endsect]
 156
 157 [section:permutation Permutation algorithms]
 158 [include algorithm/next_permutation.qbk]
 159 [include algorithm/prev_permutation.qbk]
 160 [endsect]
 161
 162 [section:new New algorithms]
 163 [include algorithm_ext/copy_n.qbk]
 164 [include algorithm_ext/erase.qbk]
 165 [include algorithm_ext/for_each.qbk]
 166 [include algorithm_ext/insert.qbk]
 167 [include algorithm_ext/iota.qbk]
 168 [include algorithm_ext/is_sorted.qbk]
 169 [include algorithm_ext/overwrite.qbk]
 170 [include algorithm_ext/push_back.qbk]
 171 [include algorithm_ext/push_front.qbk]
 172 [include algorithm_ext/remove_erase.qbk]
 173 [include algorithm_ext/remove_erase_if.qbk]
 174 [endsect]
 175
 176 [section:numeric Numeric algorithms]
 177 [include numeric/accumulate.qbk]
 178 [include numeric/adjacent_difference.qbk]
 179 [include numeric/inner_product.qbk]
 180 [include numeric/partial_sum.qbk]
 181 [endsect]
 182 [endsect]