[library The Boost Algorithm Library
    [quickbook 1.5]
    [id algorithm]
    [dirname algorithm]
    [purpose Library of useful algorithms]
    [category algorithms]
    [authors [Clow, Marshall]]
    [copyright 2010-2012 Marshall Clow]
    [source-mode c++]
    [license
		Distributed under the Boost Software License, Version 1.0.
		(See accompanying file LICENSE_1_0.txt or copy at
		[@http://www.boost.org/LICENSE_1_0.txt])
    ]
]

[section Description and Rationale]

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.

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.

[heading Future plans]

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. 

My goal is to run regular algorithm reviews, similar to the Boost library review process, but with smaller chunks of code. 

[heading Dependencies]

Boost.Algorithm uses Boost.Range, Boost.Assert, Boost.Array, Boost.TypeTraits, and Boost.StaticAssert.


[heading Acknowledgements]

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.

[endsect]

[/ include toc.qbk]


[section:Searching Searching Algorithms]
[include boyer_moore.qbk]
[include boyer_moore_horspool.qbk]
[include knuth_morris_pratt.qbk]
[endsect]


[section:CXX11 C++11 Algorithms]

[section:CXX11_inner_algorithms]

[include all_of.qbk]
[include any_of.qbk]
[include none_of.qbk]
[include one_of.qbk]
[include ordered-hpp.qbk]
[include is_partitioned.qbk]
[include is_permutation.qbk]
[include partition_point.qbk]

[section:partition_copy partition_copy ]
[*[^[link header.boost.algorithm.cxx11.partition_copy_hpp            partition_copy]              ] ]
Copy a subset of a sequence to a new sequence
[endsect:partition_copy]

[section:copy_if        copy_if        ]
[*[^[link header.boost.algorithm.cxx11.copy_if_hpp                   copy_if]                     ] ]
Copy a subset of a sequence to a new sequence
[endsect:copy_if]

[section:copy_n         copy_n         ]
[*[^[link header.boost.algorithm.cxx11.copy_n_hpp                    copy_n]                      ] ]
Copy n items from one sequence to another
[endsect:copy_n]

[section:iota           iota           ]
[*[^[link header.boost.algorithm.cxx11.iota_hpp                      iota]                        ] ]
Generate an increasing series
[endsect:iota]

[endsect:CXX11_inner_algorithms]

[endsect:CXX11]


[section:CXX14 C++14 Algorithms]

[section:CXX14_inner_algorithms]

[include equal.qbk]
[include mismatch.qbk]

[endsect:CXX14_inner_algorithms]

[endsect:CXX14]


[section:CXX17 C++17 Algorithms]

[section:CXX17_inner_algorithms]

[section:for_each_n for_each_n]
[*[^[link boost.algorithm.for_each_n                                 for_each_n]                  ] ]
Apply a functor to the elements of a sequence
[endsect:for_each_n]

[section:transform_inclusive_scan transform_inclusive_scan]
[*[^[link boost.algorithm.transform_inclusive_scan                   transform_inclusive_scan]    ] ]
Transform each element in a range then combine adjacent elements to create an output range. Inclusive scaning means that the nth input is present in the nth output.
[endsect:transform_inclusive_scan]

[section:transform_exclusive_scan transform_exclusive_scan]
[*[^[link boost.algorithm.transform_exclusive_scan                   transform_exclusive_scan]    ] ]
Transform each element in a range then combine adjacent elements to create an output range. Exclusive scanning means that the nth input is not present in the nth output.
[endsect:transform_exclusive_scan]

[endsect:CXX17_inner_algorithms]

[endsect:CXX17]


[section:Copy Variations on Copy]
[section:variations_on_copy]

[section:copy_until                copy_until                ]
[*[^[link header.boost.algorithm.cxx11.copy_if_hpp                   copy_until]                  ] ]
Copy all the elements from the start of the input range to the output range until the predicate is satisfied
[endsect:copy_until]

[section:copy_while                copy_while                ]
[*[^[link header.boost.algorithm.cxx11.copy_if_hpp                   copy_while]                  ] ]
Copy all the elements from the start of the input range to the output range while the predicate is satisfied
[endsect:copy_while]

[section:copy_if_until             copy_if_until             ]
[*[^[link header.boost.algorithm.cxx11.copy_if_hpp                   copy_if_until                ] ]
Copy all elements that satisfy the element predicate from the start of the input range to the output range until the termination predicate is satisfied

[endsect:copy_if_until]

[section:copy_if_while             copy_if_while             ]
[*[^[link header.boost.algorithm.cxx11.copy_if_hpp                   copy_if_while                ] ]
Copy all elements that satisfy the element predicate from the start of the input range to the output range while the termination predicate is satisfied

[endsect:copy_if_while]

[endsect:variations_on_copy]
[endsect:Copy]


[section:Misc Other Algorithms]

[section:misc_inner_algorithms]

[section:none_of_equal             none_of_equal             ]
[*[^[link header.boost.algorithm.cxx11.none_of_hpp                   none_of_equal]               ] ]
Whether none of a range's elements matches a value
[endsect:none_of_equal]

[section:one_of_equal              one_of_equal              ]
[*[^[link header.boost.algorithm.cxx11.one_of_hpp                    one_of_equal]                ] ]
Whether only one of a range's elements matches a value
[endsect:one_of_equal]

[section:is_decreasing             is_decreasing             ]
[*[^[link header.boost.algorithm.cxx11.is_sorted_hpp                 is_decreasing]               ] ]
Whether an entire sequence is decreasing; i.e, each item is less than or equal to the previous one
[endsect:is_decreasing]

[section:is_increasing             is_increasing             ]
[*[^[link header.boost.algorithm.cxx11.is_sorted_hpp                 is_increasing]               ] ]
Whether an entire sequence is increasing; i.e, each item is greater than or equal to the previous one
[endsect:is_increasing]

[section:is_strictly_decreasing    is_strictly_decreasing    ]
[*[^[link header.boost.algorithm.cxx11.is_sorted_hpp                 is_strictly_decreasing]      ] ]
Whether an entire sequence is strictly decreasing; i.e, each item is less than the previous one
[endsect:is_strictly_decreasing]

[section:is_strictly_increasing    is_strictly_increasing    ]
[*[^[link header.boost.algorithm.cxx11.is_sorted_hpp                 is_strictly_increasing]      ] ]
Whether an entire sequence is strictly increasing; i.e, each item is greater than the previous one
[endsect:is_strictly_increasing]

[include clamp-hpp.qbk]

[section:clamp_range               clamp_range               ]
[*[^[link header.boost.algorithm.clamp_hpp                           clamp_range]                 ] ]
Perform [^clamp] on the elements of a range and write the results into an output iterator
[endsect:clamp_range]

[include find_not.qbk]

[include find_backward.qbk]

[section:find_not_backward         find_not_backward         ]
[*[^[link header.boost.algorithm.find_backward_hpp                   find_not_backward]           ] ]
Find the last element in a sequence that does not equal a value.
See [link the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward find_backward].
[endsect:find_not_backward]

[section:find_if_backward          find_if_backward          ]
[*[^[link header.boost.algorithm.find_backward_hpp                   find_if_backward]            ] ]
Find the last element in a sequence that satisfies a predicate.
See [link the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward find_backward].
[endsect:find_if_backward]

[section:find_if_not               find_if_not               ]
[*[^[link header.boost.algorithm.cxx11.find_if_not_hpp               find_if_not]                 ] ]
Find the first element in a sequence that does not satisfy a predicate.
See [link the_boost_algorithm_library.Misc.misc_inner_algorithms.find_not find_not].
[endsect:find_if_not]

[section:find_if_not_backward      find_if_not_backward      ]
[*[^[link header.boost.algorithm.find_backward_hpp                   find_if_not_backward]        ] ]
Find the last element in a sequence that does not satisfy a predicate.
See [link the_boost_algorithm_library.Misc.misc_inner_algorithms.find_backward find_backward].
[endsect:find_if_not_backward]

[include gather.qbk]

[include hex.qbk]

[section:unhex                     unhex                     ]
[*[^[link header.boost.algorithm.hex_hpp                             unhex]                       ] ]
Convert a sequence of hexadecimal characters into a sequence of integers or characters
[endsect:unhex]

[section:hex_lower                 hex_lower                 ]
[*[^[link header.boost.algorithm.hex_hpp                             hex_lower]                   ] ]
Convert a sequence of integral types into a lower case hexadecimal sequence of characters
[endsect:hex_lower]

[include is_palindrome.qbk]

[include is_partitioned_until.qbk]

[section:apply_reverse_permutation apply_reverse_permutation ]
See below
[endsect:apply_reverse_permutation]

[include apply_permutation.qbk]

[section:iota_n                    iota_n                    ]
[*[^[link boost.algorithm.iota_n                                     iota_n]                      ] ]
Write a sequence of n increasing values to an output iterator
[endsect:iota_n]

[section:power                     power                     ]
[*[^[link header.boost.algorithm.algorithm_hpp                       power]                       ] ]
Raise a value to an integral power ([^constexpr] since C++14)
[endsect:power]

[endsect:misc_inner_algorithms]

[endsect:Misc]


[section:not_yet_documented_cxx17_algos Not-yet-documented C++17 Algorithms]

* [*[^[link header.boost.algorithm.cxx17.exclusive_scan_hpp            exclusive_scan]              ] ]
* [*[^[link header.boost.algorithm.cxx17.inclusive_scan_hpp            inclusive_scan]              ] ]
* [*[^[link header.boost.algorithm.cxx17.reduce_hpp                    reduce]                      ] ]
* [*[^[link header.boost.algorithm.cxx17.transform_reduce_hpp          transform_reduce]            ] ]

[endsect:not_yet_documented_cxx17_algos]


[section:not_yet_documented_other_algos Not-yet-documented Other Algorithms]

* [*[^[link header.boost.algorithm.minmax_hpp                          minmax]                      ] ]
* [*[^[link header.boost.algorithm.minmax_element_hpp                  first_max_element]           ] ]
* [*[^[link header.boost.algorithm.minmax_element_hpp                  first_min_element]           ] ]
* [*[^[link header.boost.algorithm.minmax_element_hpp                  first_min_first_max_element] ] ]
* [*[^[link header.boost.algorithm.minmax_element_hpp                  first_min_last_max_element]  ] ]
* [*[^[link header.boost.algorithm.minmax_element_hpp                  last_max_element]            ] ]
* [*[^[link header.boost.algorithm.minmax_element_hpp                  last_min_element]            ] ]
* [*[^[link header.boost.algorithm.minmax_element_hpp                  last_min_first_max_element]  ] ]
* [*[^[link header.boost.algorithm.minmax_element_hpp                  last_min_last_max_element]   ] ]
* [*[^[link header.boost.algorithm.minmax_element_hpp                  minmax_element]              ] ]
* [*[^[link header.boost.algorithm.sort_subrange_hpp                   partition_subrange]          ] ]
* [*[^[link header.boost.algorithm.sort_subrange_hpp                   sort_subrange]               ] ]

[endsect:not_yet_documented_other_algos]


[xinclude autodoc.xml]


