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 19Boost.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 21An 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 25I 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 27My 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 31Boost.Algorithm uses Boost.Range, Boost.Assert, Boost.Array, Boost.TypeTraits, and Boost.StaticAssert. 32 33 34[heading Acknowledgements] 35 36Thanks 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] ] ] 65Copy 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] ] ] 70Copy 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] ] ] 75Copy 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] ] ] 80Generate 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] ] ] 106Apply 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] ] ] 120Whether 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] ] ] 125Whether 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] ] ] 130Whether 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] ] ] 135Whether 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] ] ] 140Whether 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] ] ] 145Whether 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] ] ] 152Perform [^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] ] ] 161Find the last element in a sequence that does not equal a value. 162See [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] ] ] 167Find the last element in a sequence that satisfies a predicate. 168See [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] ] ] 173Find the first element in a sequence that does not satisfy a predicate. 174See [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] ] ] 179Find the last element in a sequence that does not satisfy a predicate. 180See [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] ] ] 189Convert 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] ] ] 194Convert 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 ] 202See 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] ] ] 209Copy 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] ] ] 214Copy 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] ] ] 219Write 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] ] ] 224Raise 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 265