libs/algorithm/doc/algorithm.qbk

   1 [library The Boost Algorithm Library
   2     [quickbook 1.5]
   3     [id algorithm]
   4     [dirname algorithm]
   5     [purpose Library of useful algorithms]
   6     [category algorithms]
   7     [authors [Clow, Marshall]]
   8     [copyright 2010-2012 Marshall Clow]
   9     [source-mode c++]
  10     [license
  11                 Distributed under the Boost Software License, Version 1.0.
  12                 (See accompanying file LICENSE_1_0.txt or copy at
  13                 [@http://www.boost.org/LICENSE_1_0.txt])
  14     ]
  15 ]
  16
  17 [section Description and Rationale]
  18
  19 Boost.Algorithm is a collection of general purpose algorithms. While Boost contains many libraries of data structures, there is no single library for general purpose algorithms. Even though the algorithms are generally useful, many tend to be thought of as "too small" for Boost.
  20
  21 An implementation of Boyer-Moore searching, for example, might take a developer a week or so to implement, including test cases and documentation. However, scheduling a review to include that code into Boost might take several months, and run into resistance because "it is too small". Nevertheless, a library of tested, reviewed, documented algorithms can make the developer's life much easier, and that is the purpose of this library.
  22
  23 [heading Future plans]
  24
  25 I will be soliciting submissions from other developers, as well as looking through the literature for existing algorithms to include. The Adobe Source Library, for example, contains many useful algorithms that already have documentation and test cases. Knuth's _The Art of Computer Programming_ is chock-full of algorithm descriptions, too.
  26
  27 My goal is to run regular algorithm reviews, similar to the Boost library review process, but with smaller chunks of code.
  28
  29 [heading Dependencies]
  30
  31 Boost.Algorithm uses Boost.Range, Boost.Assert, Boost.Array, Boost.TypeTraits, and Boost.StaticAssert.
  32
  33
  34 [heading Acknowledgements]
  35
  36 Thanks to all the people who have reviewed this library and made suggestions for improvements. Steven Watanabe and Sean Parent, in particular, have provided a great deal of help.
  37
  38 [endsect]
  39
  40 [/ include toc.qbk]
  41
  42
  43 [section:Searching Searching Algorithms]
  44 [include boyer_moore.qbk]
  45 [include boyer_moore_horspool.qbk]
  46 [include knuth_morris_pratt.qbk]
  47 [endsect]
  48
  49
  50 [section:CXX11 C++11 Algorithms]
  51
  52 [section:CXX11_inner_algorithms]
  53
  54 [include all_of.qbk]
  55 [include any_of.qbk]
  56 [include none_of.qbk]
  57 [include one_of.qbk]
  58 [include ordered-hpp.qbk]
  59 [include is_partitioned.qbk]
  60 [include is_permutation.qbk]
  61 [include partition_point.qbk]
  62
  63 [section:partition_copy partition_copy ]
  64 [*[^[link header.boost.algorithm.cxx11.partition_copy_hpp            partition_copy]              ] ]
  65 Copy a subset of a sequence to a new sequence
  66 [endsect:partition_copy]
  67
  68 [section:copy_if        copy_if        ]
  69 [*[^[link header.boost.algorithm.cxx11.copy_if_hpp                   copy_if]                     ] ]
  70 Copy a subset of a sequence to a new sequence
  71 [endsect:copy_if]
  72
  73 [section:copy_n         copy_n         ]
  74 [*[^[link header.boost.algorithm.cxx11.copy_n_hpp                    copy_n]                      ] ]
  75 Copy n items from one sequence to another
  76 [endsect:copy_n]
  77
  78 [section:iota           iota           ]
  79 [*[^[link header.boost.algorithm.cxx11.iota_hpp                      iota]                        ] ]
  80 Generate an increasing series
  81 [endsect:iota]
  82
  83 [endsect:CXX11_inner_algorithms]
  84
  85 [endsect:CXX11]
  86
  87
  88 [section:CXX14 C++14 Algorithms]
  89
  90 [section:CXX14_inner_algorithms]
  91
  92 [include equal.qbk]
  93 [include mismatch.qbk]
  94
  95 [endsect:CXX14_inner_algorithms]
  96
  97 [endsect:CXX14]
  98
  99
 100 [section:CXX17 C++17 Algorithms]
 101
 102 [section:CXX17_inner_algorithms]
 103
 104 [section:for_each_n for_each_n]
 105 [*[^[link boost.algorithm.for_each_n                                 for_each_n]                  ] ]
 106 Apply a functor to the elements of a sequence
 107 [endsect:for_each_n]
 108
 109 [endsect:CXX17_inner_algorithms]
 110
 111 [endsect:CXX17]
 112
 113
 114 [section:Misc Other Algorithms]
 115
 116 [section:misc_inner_algorithms]
 117
 118 [section:none_of_equal             none_of_equal             ]
 119 [*[^[link header.boost.algorithm.cxx11.none_of_hpp                   none_of_equal]               ] ]
 120 Whether none of a range's elements matches a value
 121 [endsect:none_of_equal]
 122
 123 [section:one_of_equal              one_of_equal              ]
 124 [*[^[link header.boost.algorithm.cxx11.one_of_hpp                    one_of_equal]                ] ]
 125 Whether only one of a range's elements matches a value
 126 [endsect:one_of_equal]
 127
 128 [section:is_decreasing             is_decreasing             ]
 129 [*[^[link header.boost.algorithm.cxx11.is_sorted_hpp                 is_decreasing]               ] ]
 130 Whether an entire sequence is decreasing; i.e, each item is less than or equal to the previous one
 131 [endsect:is_decreasing]
 132
 133 [section:is_increasing             is_increasing             ]
 134 [*[^[link header.boost.algorithm.cxx11.is_sorted_hpp                 is_increasing]               ] ]
 135 Whether an entire sequence is increasing; i.e, each item is greater than or equal to the previous one
 136 [endsect:is_increasing]
 137
 138 [section:is_strictly_decreasing    is_strictly_decreasing    ]
 139 [*[^[link header.boost.algorithm.cxx11.is_sorted_hpp                 is_strictly_decreasing]      ] ]
 140 Whether an entire sequence is strictly decreasing; i.e, each item is less than the previous one
 141 [endsect:is_strictly_decreasing]
 142
 143 [section:is_strictly_increasing    is_strictly_increasing    ]
 144 [*[^[link header.boost.algorithm.cxx11.is_sorted_hpp                 is_strictly_increasing]      ] ]
 145 Whether an entire sequence is strictly increasing; i.e, each item is greater than the previous one
 146 [endsect:is_strictly_increasing]
 147
 148 [include clamp-hpp.qbk]
 149
 150 [section:clamp_range               clamp_range               ]
 151 [*[^[link header.boost.algorithm.clamp_hpp                           clamp_range]                 ] ]
 152 Perform [^clamp] on the elements of a range and write the results into an output iterator
 153 [endsect:clamp_range]
 154
 155 [include find_not.qbk]
 156
 157 [include find_backward.qbk]
 158
 159 [section:find_not_backward         find_not_backward         ]
 160 [*[^[link header.boost.algorithm.find_backward_hpp                   find_not_backward]           ] ]
 161 Find the last element in a sequence that does not equal a value.
 162 See [link the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward find_backward].
 163 [endsect:find_not_backward]
 164
 165 [section:find_if_backward          find_if_backward          ]
 166 [*[^[link header.boost.algorithm.find_backward_hpp                   find_if_backward]            ] ]
 167 Find the last element in a sequence that satisfies a predicate.
 168 See [link the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward find_backward].
 169 [endsect:find_if_backward]
 170
 171 [section:find_if_not               find_if_not               ]
 172 [*[^[link header.boost.algorithm.cxx11.find_if_not_hpp               find_if_not]                 ] ]
 173 Find the first element in a sequence that does not satisfy a predicate.
 174 See [link the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not find_not].
 175 [endsect:find_if_not]
 176
 177 [section:find_if_not_backward      find_if_not_backward      ]
 178 [*[^[link header.boost.algorithm.find_backward_hpp                   find_if_not_backward]        ] ]
 179 Find the last element in a sequence that does not satisfy a predicate.
 180 See [link the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward find_backward].
 181 [endsect:find_if_not_backward]
 182
 183 [include gather.qbk]
 184
 185 [include hex.qbk]
 186
 187 [section:unhex                     unhex                     ]
 188 [*[^[link header.boost.algorithm.hex_hpp                             unhex]                       ] ]
 189 Convert a sequence of hexadecimal characters into a sequence of integers or characters
 190 [endsect:unhex]
 191
 192 [section:hex_lower                 hex_lower                 ]
 193 [*[^[link header.boost.algorithm.hex_hpp                             hex_lower]                   ] ]
 194 Convert a sequence of integral types into a lower case hexadecimal sequence of characters
 195 [endsect:hex_lower]
 196
 197 [include is_palindrome.qbk]
 198
 199 [include is_partitioned_until.qbk]
 200
 201 [section:apply_reverse_permutation apply_reverse_permutation ]
 202 See below
 203 [endsect:apply_reverse_permutation]
 204
 205 [include apply_permutation.qbk]
 206
 207 [section:copy_until                copy_until                ]
 208 [*[^[link header.boost.algorithm.cxx11.copy_if_hpp                   copy_until]                  ] ]
 209 Copy all the elements at the start of the input range that do not satisfy the predicate to the output range
 210 [endsect:copy_until]
 211
 212 [section:copy_while                copy_while                ]
 213 [*[^[link header.boost.algorithm.cxx11.copy_if_hpp                   copy_while]                  ] ]
 214 Copy all the elements at the start of the input range that satisfy the predicate to the output range
 215 [endsect:copy_while]
 216
 217 [section:iota_n                    iota_n                    ]
 218 [*[^[link boost.algorithm.iota_n                                     iota_n]                      ] ]
 219 Write a sequence of n increasing values to an output iterator
 220 [endsect:iota_n]
 221
 222 [section:power                     power                     ]
 223 [*[^[link header.boost.algorithm.algorithm_hpp                       power]                       ] ]
 224 Raise a value to an integral power ([^constexpr] since C++14)
 225 [endsect:power]
 226
 227 [endsect:misc_inner_algorithms]
 228
 229 [endsect:Misc]
 230
 231
 232 [section:not_yet_documented_cxx17_algos Not-yet-documented C++17 Algorithms]
 233
 234 * [*[^[link header.boost.algorithm.cxx17.exclusive_scan_hpp            exclusive_scan]              ] ]
 235 * [*[^[link header.boost.algorithm.cxx17.inclusive_scan_hpp            inclusive_scan]              ] ]
 236 * [*[^[link header.boost.algorithm.cxx17.reduce_hpp                    reduce]                      ] ]
 237 * [*[^[link header.boost.algorithm.cxx17.transform_exclusive_scan_hpp  transform_exclusive_scan]    ] ]
 238 * [*[^[link header.boost.algorithm.cxx17.transform_inclusive_scan_hpp  transform_inclusive_scan]    ] ]
 239 * [*[^[link header.boost.algorithm.cxx17.transform_reduce_hpp          transform_reduce]            ] ]
 240
 241 [endsect:not_yet_documented_cxx17_algos]
 242
 243
 244 [section:not_yet_documented_other_algos Not-yet-documented Other Algorithms]
 245
 246 * [*[^[link header.boost.algorithm.minmax_hpp                          minmax]                      ] ]
 247 * [*[^[link header.boost.algorithm.minmax_element_hpp                  first_max_element]           ] ]
 248 * [*[^[link header.boost.algorithm.minmax_element_hpp                  first_min_element]           ] ]
 249 * [*[^[link header.boost.algorithm.minmax_element_hpp                  first_min_first_max_element] ] ]
 250 * [*[^[link header.boost.algorithm.minmax_element_hpp                  first_min_last_max_element]  ] ]
 251 * [*[^[link header.boost.algorithm.minmax_element_hpp                  last_max_element]            ] ]
 252 * [*[^[link header.boost.algorithm.minmax_element_hpp                  last_min_element]            ] ]
 253 * [*[^[link header.boost.algorithm.minmax_element_hpp                  last_min_first_max_element]  ] ]
 254 * [*[^[link header.boost.algorithm.minmax_element_hpp                  last_min_last_max_element]   ] ]
 255 * [*[^[link header.boost.algorithm.minmax_element_hpp                  minmax_element]              ] ]
 256 * [*[^[link header.boost.algorithm.sort_subrange_hpp                   partition_subrange]          ] ]
 257 * [*[^[link header.boost.algorithm.sort_subrange_hpp                   sort_subrange]               ] ]
 258
 259 [endsect:not_yet_documented_other_algos]
 260
 261
 262 [xinclude autodoc.xml]
 263
 264