1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>The Boost Algorithm Library</title> 5<link rel="stylesheet" href="../../../../doc/src/boostbook.css" type="text/css"> 6<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 7<link rel="home" href="index.html" title="The Boost Algorithm Library"> 8<link rel="next" href="algorithm/Searching.html" title="Searching Algorithms"> 9</head> 10<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 11<table cellpadding="2" width="100%"><tr> 12<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../boost.png"></td> 13<td align="center"><a href="../../../../index.html">Home</a></td> 14<td align="center"><a href="../../../../libs/libraries.htm">Libraries</a></td> 15<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 16<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 17<td align="center"><a href="../../../../more/index.htm">More</a></td> 18</tr></table> 19<hr> 20<div class="spirit-nav"><a accesskey="n" href="algorithm/Searching.html"><img src="../../../../doc/src/images/next.png" alt="Next"></a></div> 21<div class="chapter"> 22<div class="titlepage"><div> 23<div><h2 class="title"> 24<a name="algorithm"></a>The Boost Algorithm Library</h2></div> 25<div><div class="author"><h3 class="author"> 26<span class="firstname">Marshall</span> <span class="surname">Clow</span> 27</h3></div></div> 28<div><p class="copyright">Copyright © 2010-2012 Marshall Clow</p></div> 29<div><div class="legalnotice"> 30<a name="algorithm.legal"></a><p> 31 Distributed under the Boost Software License, Version 1.0. (See accompanying 32 file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) 33 </p> 34</div></div> 35</div></div> 36<div class="toc"> 37<p><b>Table of Contents</b></p> 38<dl class="toc"> 39<dt><span class="section"><a href="index.html#algorithm.description_and_rationale">Description and Rationale</a></span></dt> 40<dt><span class="section"><a href="algorithm/Searching.html">Searching Algorithms</a></span></dt> 41<dd><dl> 42<dt><span class="section"><a href="algorithm/Searching.html#the_boost_algorithm_library.Searching.BoyerMoore">Boyer-Moore 43 Search</a></span></dt> 44<dt><span class="section"><a href="the_boost_algorithm_library/Searching/BoyerMooreHorspool.html">Boyer-Moore-Horspool 45 Search</a></span></dt> 46<dt><span class="section"><a href="the_boost_algorithm_library/Searching/KnuthMorrisPratt.html">Knuth-Morris-Pratt 47 Search</a></span></dt> 48</dl></dd> 49<dt><span class="section"><a href="algorithm/CXX11.html">C++11 Algorithms</a></span></dt> 50<dd><dl> 51<dt><span class="section"><a href="algorithm/CXX11.html#algorithm.CXX11.CXX11_inner_algorithms"></a></span></dt> 52<dd><dl> 53<dt><span class="section"><a href="algorithm/CXX11.html#the_boost_algorithm_library.CXX11.CXX11_inner_algorithms.all_of">all_of</a></span></dt> 54<dt><span class="section"><a href="algorithm/CXX11.html#the_boost_algorithm_library.CXX11.CXX11_inner_algorithms.any_of">any_of</a></span></dt> 55<dt><span class="section"><a href="algorithm/CXX11.html#the_boost_algorithm_library.CXX11.CXX11_inner_algorithms.none_of">none_of</a></span></dt> 56<dt><span class="section"><a href="algorithm/CXX11.html#the_boost_algorithm_library.CXX11.CXX11_inner_algorithms.one_of">one_of</a></span></dt> 57<dt><span class="section"><a href="algorithm/CXX11.html#the_boost_algorithm_library.CXX11.CXX11_inner_algorithms.is_sorted">is_sorted 58 </a></span></dt> 59<dt><span class="section"><a href="algorithm/CXX11.html#the_boost_algorithm_library.CXX11.CXX11_inner_algorithms.is_partitioned">is_partitioned 60 </a></span></dt> 61<dt><span class="section"><a href="algorithm/CXX11.html#the_boost_algorithm_library.CXX11.CXX11_inner_algorithms.is_permutation">is_permutation 62 </a></span></dt> 63<dt><span class="section"><a href="algorithm/CXX11.html#the_boost_algorithm_library.CXX11.CXX11_inner_algorithms.partition_point">partition_point 64 </a></span></dt> 65<dt><span class="section"><a href="algorithm/CXX11.html#algorithm.CXX11.CXX11_inner_algorithms.partition_copy">partition_copy 66 </a></span></dt> 67<dt><span class="section"><a href="algorithm/CXX11.html#algorithm.CXX11.CXX11_inner_algorithms.copy_if">copy_if 68 </a></span></dt> 69<dt><span class="section"><a href="algorithm/CXX11.html#algorithm.CXX11.CXX11_inner_algorithms.copy_n">copy_n 70 </a></span></dt> 71<dt><span class="section"><a href="algorithm/CXX11.html#algorithm.CXX11.CXX11_inner_algorithms.iota">iota 72 </a></span></dt> 73</dl></dd> 74</dl></dd> 75<dt><span class="section"><a href="algorithm/CXX14.html">C++14 Algorithms</a></span></dt> 76<dd><dl> 77<dt><span class="section"><a href="algorithm/CXX14.html#algorithm.CXX14.CXX14_inner_algorithms"></a></span></dt> 78<dd><dl> 79<dt><span class="section"><a href="algorithm/CXX14.html#the_boost_algorithm_library.CXX14.CXX14_inner_algorithms.equal">equal 80 </a></span></dt> 81<dt><span class="section"><a href="algorithm/CXX14.html#the_boost_algorithm_library.CXX14.CXX14_inner_algorithms.mismatch">mismatch 82 </a></span></dt> 83</dl></dd> 84</dl></dd> 85<dt><span class="section"><a href="algorithm/CXX17.html">C++17 Algorithms</a></span></dt> 86<dd><dl> 87<dt><span class="section"><a href="algorithm/CXX17.html#algorithm.CXX17.CXX17_inner_algorithms"></a></span></dt> 88<dd><dl><dt><span class="section"><a href="algorithm/CXX17.html#algorithm.CXX17.CXX17_inner_algorithms.for_each_n">for_each_n</a></span></dt></dl></dd> 89</dl></dd> 90<dt><span class="section"><a href="algorithm/Misc.html">Other Algorithms</a></span></dt> 91<dd><dl> 92<dt><span class="section"><a href="algorithm/Misc.html#algorithm.Misc.misc_inner_algorithms"></a></span></dt> 93<dd><dl> 94<dt><span class="section"><a href="algorithm/Misc.html#algorithm.Misc.misc_inner_algorithms.none_of_equal">none_of_equal 95 </a></span></dt> 96<dt><span class="section"><a href="algorithm/Misc.html#algorithm.Misc.misc_inner_algorithms.one_of_equal">one_of_equal 97 </a></span></dt> 98<dt><span class="section"><a href="algorithm/Misc.html#algorithm.Misc.misc_inner_algorithms.is_decreasing">is_decreasing 99 </a></span></dt> 100<dt><span class="section"><a href="algorithm/Misc.html#algorithm.Misc.misc_inner_algorithms.is_increasing">is_increasing 101 </a></span></dt> 102<dt><span class="section"><a href="algorithm/Misc.html#algorithm.Misc.misc_inner_algorithms.is_strictly_decreasing">is_strictly_decreasing 103 </a></span></dt> 104<dt><span class="section"><a href="algorithm/Misc.html#algorithm.Misc.misc_inner_algorithms.is_strictly_increasing">is_strictly_increasing 105 </a></span></dt> 106<dt><span class="section"><a href="algorithm/Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.clamp">clamp</a></span></dt> 107<dt><span class="section"><a href="algorithm/Misc.html#algorithm.Misc.misc_inner_algorithms.clamp_range">clamp_range 108 </a></span></dt> 109<dt><span class="section"><a href="algorithm/Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not">find_not 110 </a></span></dt> 111<dt><span class="section"><a href="algorithm/Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward">find_backward 112 </a></span></dt> 113<dt><span class="section"><a href="algorithm/Misc.html#algorithm.Misc.misc_inner_algorithms.find_not_backward">find_not_backward 114 </a></span></dt> 115<dt><span class="section"><a href="algorithm/Misc.html#algorithm.Misc.misc_inner_algorithms.find_if_backward">find_if_backward 116 </a></span></dt> 117<dt><span class="section"><a href="algorithm/Misc.html#algorithm.Misc.misc_inner_algorithms.find_if_not">find_if_not 118 </a></span></dt> 119<dt><span class="section"><a href="algorithm/Misc.html#algorithm.Misc.misc_inner_algorithms.find_if_not_backward">find_if_not_backward 120 </a></span></dt> 121<dt><span class="section"><a href="algorithm/Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.gather">gather</a></span></dt> 122<dt><span class="section"><a href="algorithm/Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.hex">hex</a></span></dt> 123<dt><span class="section"><a href="algorithm/Misc.html#algorithm.Misc.misc_inner_algorithms.unhex">unhex 124 </a></span></dt> 125<dt><span class="section"><a href="algorithm/Misc.html#algorithm.Misc.misc_inner_algorithms.hex_lower">hex_lower 126 </a></span></dt> 127<dt><span class="section"><a href="algorithm/Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.is_palindrome">is_palindrome</a></span></dt> 128<dt><span class="section"><a href="algorithm/Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.is_partitioned_until">is_partitioned_until 129 </a></span></dt> 130<dt><span class="section"><a href="algorithm/Misc.html#algorithm.Misc.misc_inner_algorithms.apply_reverse_permutation">apply_reverse_permutation 131 </a></span></dt> 132<dt><span class="section"><a href="algorithm/Misc.html#the_boost_algorithm_library.Misc.misc_inner_algorithms.apply_permutation">apply_permutation</a></span></dt> 133<dt><span class="section"><a href="algorithm/Misc.html#algorithm.Misc.misc_inner_algorithms.copy_until">copy_until 134 </a></span></dt> 135<dt><span class="section"><a href="algorithm/Misc.html#algorithm.Misc.misc_inner_algorithms.copy_while">copy_while 136 </a></span></dt> 137<dt><span class="section"><a href="algorithm/Misc.html#algorithm.Misc.misc_inner_algorithms.iota_n">iota_n 138 </a></span></dt> 139<dt><span class="section"><a href="algorithm/Misc.html#algorithm.Misc.misc_inner_algorithms.power">power 140 </a></span></dt> 141</dl></dd> 142</dl></dd> 143<dt><span class="section"><a href="algorithm/not_yet_documented_cxx17_algos.html">Not-yet-documented 144 C++17 Algorithms</a></span></dt> 145<dt><span class="section"><a href="algorithm/not_yet_documented_other_algos.html">Not-yet-documented 146 Other Algorithms</a></span></dt> 147<dt><span class="section"><a href="algorithm/reference.html">Reference</a></span></dt> 148<dd><dl> 149<dt><span class="section"><a href="algorithm/reference.html#header.boost.algorithm.algorithm_hpp">Header <boost/algorithm/algorithm.hpp></a></span></dt> 150<dd><dl></dl></dd> 151<dt><span class="section"><a href="header/boost/algorithm/apply_permutation_hpp.html">Header <boost/algorithm/apply_permutation.hpp></a></span></dt> 152<dt><span class="section"><a href="header/boost/algorithm/clamp_hpp.html">Header <boost/algorithm/clamp.hpp></a></span></dt> 153<dd><dl></dl></dd> 154<dt><span class="section"><a href="header/boost/algorithm/cxx11/all_of_hpp.html">Header <boost/algorithm/cxx11/all_of.hpp></a></span></dt> 155<dd><dl></dl></dd> 156<dt><span class="section"><a href="header/boost/algorithm/cxx11/any_of_hpp.html">Header <boost/algorithm/cxx11/any_of.hpp></a></span></dt> 157<dd><dl></dl></dd> 158<dt><span class="section"><a href="header/boost/algorithm/cxx11/copy_if_hpp.html">Header <boost/algorithm/cxx11/copy_if.hpp></a></span></dt> 159<dd><dl></dl></dd> 160<dt><span class="section"><a href="header/boost/algorithm/cxx11/copy_n_hpp.html">Header <boost/algorithm/cxx11/copy_n.hpp></a></span></dt> 161<dd><dl></dl></dd> 162<dt><span class="section"><a href="header/boost/algorithm/cxx11/find_if_not_hpp.html">Header <boost/algorithm/cxx11/find_if_not.hpp></a></span></dt> 163<dd><dl></dl></dd> 164<dt><span class="section"><a href="header/boost/algorithm/cxx11/iota_hpp.html">Header <boost/algorithm/cxx11/iota.hpp></a></span></dt> 165<dd><dl></dl></dd> 166<dt><span class="section"><a href="header/boost/algorithm/cxx11/is_partitioned_hpp.html">Header <boost/algorithm/cxx11/is_partitioned.hpp></a></span></dt> 167<dd><dl></dl></dd> 168<dt><span class="section"><a href="header/boost/algorithm/cxx11/is_permutation_hpp.html">Header <boost/algorithm/cxx11/is_permutation.hpp></a></span></dt> 169<dd><dl></dl></dd> 170<dt><span class="section"><a href="header/boost/algorithm/cxx14/is_permutation_hpp.html">Header <boost/algorithm/cxx14/is_permutation.hpp></a></span></dt> 171<dd><dl></dl></dd> 172<dt><span class="section"><a href="header/boost/algorithm/cxx11/is_sorted_hpp.html">Header <boost/algorithm/cxx11/is_sorted.hpp></a></span></dt> 173<dd><dl></dl></dd> 174<dt><span class="section"><a href="header/boost/algorithm/cxx11/none_of_hpp.html">Header <boost/algorithm/cxx11/none_of.hpp></a></span></dt> 175<dd><dl></dl></dd> 176<dt><span class="section"><a href="header/boost/algorithm/cxx11/one_of_hpp.html">Header <boost/algorithm/cxx11/one_of.hpp></a></span></dt> 177<dd><dl></dl></dd> 178<dt><span class="section"><a href="header/boost/algorithm/cxx11/partition_copy_hpp.html">Header <boost/algorithm/cxx11/partition_copy.hpp></a></span></dt> 179<dd><dl></dl></dd> 180<dt><span class="section"><a href="header/boost/algorithm/cxx11/partition_point_hpp.html">Header <boost/algorithm/cxx11/partition_point.hpp></a></span></dt> 181<dd><dl></dl></dd> 182<dt><span class="section"><a href="header/boost/algorithm/cxx14/equal_hpp.html">Header <boost/algorithm/cxx14/equal.hpp></a></span></dt> 183<dd><dl></dl></dd> 184<dt><span class="section"><a href="header/boost/algorithm/cxx14/mismatch_hpp.html">Header <boost/algorithm/cxx14/mismatch.hpp></a></span></dt> 185<dd><dl></dl></dd> 186<dt><span class="section"><a href="header/boost/algorithm/cxx17/exclusive_scan_hpp.html">Header <boost/algorithm/cxx17/exclusive_scan.hpp></a></span></dt> 187<dt><span class="section"><a href="header/boost/algorithm/cxx17/for_each_n_hpp.html">Header <boost/algorithm/cxx17/for_each_n.hpp></a></span></dt> 188<dd><dl></dl></dd> 189<dt><span class="section"><a href="header/boost/algorithm/cxx17/inclusive_scan_hpp.html">Header <boost/algorithm/cxx17/inclusive_scan.hpp></a></span></dt> 190<dt><span class="section"><a href="header/boost/algorithm/cxx17/reduce_hpp.html">Header <boost/algorithm/cxx17/reduce.hpp></a></span></dt> 191<dt><span class="section"><a href="header/boost/algorithm/cxx17/transform_exclusive_scan_hpp.html">Header <boost/algorithm/cxx17/transform_exclusive_scan.hpp></a></span></dt> 192<dt><span class="section"><a href="header/boost/algorithm/cxx17/transform_inclusive_scan_hpp.html">Header <boost/algorithm/cxx17/transform_inclusive_scan.hpp></a></span></dt> 193<dt><span class="section"><a href="header/boost/algorithm/cxx17/transform_reduce_hpp.html">Header <boost/algorithm/cxx17/transform_reduce.hpp></a></span></dt> 194<dt><span class="section"><a href="header/boost/algorithm/find_backward_hpp.html">Header <boost/algorithm/find_backward.hpp></a></span></dt> 195<dt><span class="section"><a href="header/boost/algorithm/find_not_hpp.html">Header <boost/algorithm/find_not.hpp></a></span></dt> 196<dt><span class="section"><a href="header/boost/algorithm/gather_hpp.html">Header <boost/algorithm/gather.hpp></a></span></dt> 197<dt><span class="section"><a href="header/boost/algorithm/hex_hpp.html">Header <boost/algorithm/hex.hpp></a></span></dt> 198<dd><dl></dl></dd> 199<dt><span class="section"><a href="header/boost/algorithm/is_palindrome_hpp.html">Header <boost/algorithm/is_palindrome.hpp></a></span></dt> 200<dd><dl></dl></dd> 201<dt><span class="section"><a href="header/boost/algorithm/is_partitioned_until_hpp.html">Header <boost/algorithm/is_partitioned_until.hpp></a></span></dt> 202<dd><dl></dl></dd> 203<dt><span class="section"><a href="header/boost/algorithm/minmax_hpp.html">Header <boost/algorithm/minmax.hpp></a></span></dt> 204<dt><span class="section"><a href="header/boost/algorithm/minmax_element_hpp.html">Header <boost/algorithm/minmax_element.hpp></a></span></dt> 205<dt><span class="section"><a href="header/boost/algorithm/searching/boyer_moore_hpp.html">Header <boost/algorithm/searching/boyer_moore.hpp></a></span></dt> 206<dd><dl></dl></dd> 207<dt><span class="section"><a href="header/boost/algorithm/searching/boyer_moore_horspool_hpp.html">Header <boost/algorithm/searching/boyer_moore_horspool.hpp></a></span></dt> 208<dd><dl></dl></dd> 209<dt><span class="section"><a href="header/boost/algorithm/searching/knuth_morris_pratt_hpp.html">Header <boost/algorithm/searching/knuth_morris_pratt.hpp></a></span></dt> 210<dd><dl></dl></dd> 211<dt><span class="section"><a href="header/boost/algorithm/sort_subrange_hpp.html">Header <boost/algorithm/sort_subrange.hpp></a></span></dt> 212<dt><span class="section"><a href="header/boost/algorithm/string_hpp.html">Header <boost/algorithm/string.hpp></a></span></dt> 213<dt><span class="section"><a href="header/boost/algorithm/string_regex_hpp.html">Header <boost/algorithm/string_regex.hpp></a></span></dt> 214</dl></dd> 215</dl> 216</div> 217<div class="section"> 218<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 219<a name="algorithm.description_and_rationale"></a><a class="link" href="index.html#algorithm.description_and_rationale" title="Description and Rationale">Description and Rationale</a> 220</h2></div></div></div> 221<p> 222 Boost.Algorithm is a collection of general purpose algorithms. While Boost 223 contains many libraries of data structures, there is no single library for 224 general purpose algorithms. Even though the algorithms are generally useful, 225 many tend to be thought of as "too small" for Boost. 226 </p> 227<p> 228 An implementation of Boyer-Moore searching, for example, might take a developer 229 a week or so to implement, including test cases and documentation. However, 230 scheduling a review to include that code into Boost might take several months, 231 and run into resistance because "it is too small". Nevertheless, 232 a library of tested, reviewed, documented algorithms can make the developer's 233 life much easier, and that is the purpose of this library. 234 </p> 235<h4> 236<a name="algorithm.description_and_rationale.h0"></a> 237 <span class="phrase"><a name="algorithm.description_and_rationale.future_plans"></a></span><a class="link" href="index.html#algorithm.description_and_rationale.future_plans">Future 238 plans</a> 239 </h4> 240<p> 241 I will be soliciting submissions from other developers, as well as looking 242 through the literature for existing algorithms to include. The Adobe Source 243 Library, for example, contains many useful algorithms that already have documentation 244 and test cases. Knuth's <span class="underline">The Art of Computer Programming</span> 245 is chock-full of algorithm descriptions, too. 246 </p> 247<p> 248 My goal is to run regular algorithm reviews, similar to the Boost library review 249 process, but with smaller chunks of code. 250 </p> 251<h4> 252<a name="algorithm.description_and_rationale.h1"></a> 253 <span class="phrase"><a name="algorithm.description_and_rationale.dependencies"></a></span><a class="link" href="index.html#algorithm.description_and_rationale.dependencies">Dependencies</a> 254 </h4> 255<p> 256 Boost.Algorithm uses Boost.Range, Boost.Assert, Boost.Array, Boost.TypeTraits, 257 and Boost.StaticAssert. 258 </p> 259<h4> 260<a name="algorithm.description_and_rationale.h2"></a> 261 <span class="phrase"><a name="algorithm.description_and_rationale.acknowledgements"></a></span><a class="link" href="index.html#algorithm.description_and_rationale.acknowledgements">Acknowledgements</a> 262 </h4> 263<p> 264 Thanks to all the people who have reviewed this library and made suggestions 265 for improvements. Steven Watanabe and Sean Parent, in particular, have provided 266 a great deal of help. 267 </p> 268</div> 269</div> 270<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 271<td align="left"><p><small>Last revised: August 11, 2020 at 15:02:02 GMT</small></p></td> 272<td align="right"><div class="copyright-footer"></div></td> 273</tr></table> 274<hr> 275<div class="spirit-nav"><a accesskey="n" href="algorithm/Searching.html"><img src="../../../../doc/src/images/next.png" alt="Next"></a></div> 276</body> 277</html> 278
