Generic algorithms for performing various operations on containers and sequences.
#include <algorithm>
The synopsis of each algorithm appears in its entry in the reference guide.
The Standard C++ Library provides a very flexible framework for applying generic algorithms to containers. The library also provides a rich set of these algorithms for searching, sorting, merging, transforming, scanning, and much more.
Each algorithm can be applied to a variety of containers, including those defined by a user of the library. The following design features make algorithms generic:
Generic algorithms access the collection through iterators
Algorithms are templatized on iterator types
Each algorithm is designed to require the least number of services from the iterators it uses
In addition to requiring certain iterator capabilities, algorithms may require a container to be in a specific state. For example, some algorithms can only work on previously sorted containers.
Because most algorithms rely on iterators to gain access to data, they can be grouped according to the type of iterator they require, as is done in the Algorithms by Iterator section below. They can also be grouped according to the type of operation they perform.
The broadest categorization groups algorithms into two main types: mutating and non-mutating. Algorithms that alter (or mutate) the contents of a container fall into the mutating group. All others are considered non-mutating. For example, both fill and sort are mutating algorithms, while find and for_each are non-mutating.
Non-mutating operations
| accumulate | find_end | max_element |
| adjacent_find | find_first_of | min |
| binary_search | find_if | min_element |
| count_min | for_each | mismatch |
| count_if | includes | nth_element |
| equal | lexicographical_compare | search |
| eqaul_range | lower_bound | search_n |
| find | max |
Mutating operations
| copy | remove_if |
| copy_backward | replace |
| fill | replace_copy |
| fill_n | replace_copy_if |
| generate | replace_if |
| generate_n | reverse |
| inplace_merge | reverse_copy |
| iter_swap | rotate |
| make_heap | rotate_copy |
| merge | set_difference |
| nth_element | set_symmetric_difference |
| next_permutation | set_intersection |
| partial_sort | set_union |
| partial_sort_copy | sort |
| partition | sort_heap |
| prev_permutation | stable_partition |
| push_heap | stable_sort |
| pop_heap | swap |
| random_shuffle | swap_ranges |
| remove | transform |
| remove_copy | unique |
| remove_copy_if | unique_copy |
Note that the library provides both in place and copy versions of many algorithms, such as replace and replace_copy. The library also provides versions of algorithms that allow the use of default comparators and comparators supplied by the user. Often these functions are overloaded, but in some cases (where overloading proved impractical or impossible) the names differ (e.g., replace, which will use equality to determine replacement, and replace_if, which accesses a user provided compare function).
We can further distinguish algorithms by the kind of operations they perform. The following lists all algorithms by loosely grouping them into similar operations.
Initializing operations
fill generate fill_n generate_n
Search operations
adjacent_find find_end search_n count find_if count_if find_first_of find search
Binary search operations (Elements must be sorted)
binary_search lower_bound equal_range upper_bound
Compare operations
equal mismatch lexicographical_compare
Copy operations
copy copy_backward
Transforming operations
partition reverse random_shuffle reverse_copy replace rotate replace_copy rotate_copy replace_copy_if stable_partition replace_if transform
Swap operations
swap swap_ranges
Scanning operations
accumulate for_each
Remove operations
remove remove_if remove_copy unique remove_copy_if unique_copy
Sorting operations
nth_element sort partial_sort stable_sort partial_sort_copy
Merge operations (Elements must be sorted)
inplace_merge merge
Set operations (Elements must be sorted)
includes set_symmetric_difference set_difference set_union set_intersection
Heap operations
make_heap push_heap pop_heap sort_heap
Minimum and maximum
max min max_element min_element
Permutation generators
next_permutation prev_permutation
Each algorithm requires certain kinds of iterators (for a description of the iterators and their capabilities see the Iterators entry in this manual). The following set of lists groups the algorithms according to the types of iterators they require.
Algorithms that use no iterators:
max min swap
Algorithms that require only input iterators:
accumulate find mismatch count find_if count_if includes equal inner_product for_each lexicographical_compare
Algorithms that require only output iterators:
fill_n generate_n
Algorithms that read from input iterators and write to output iterators:
adjacent_difference replace_copy transform copy replace_copy_if unique_copy merge set_difference partial_sum set_intersedtion remove_copy set_symmetric_difference remove_copy_if set_union
Algorithms that require forward iterators:
| adjacent_find | iter_swap | replace_if |
| binary_search | lower_bound | rotate |
| equal_range | max_element | search |
| fill | min_element | search_n |
| find_end | remove | swap_ranges |
| find_first_of | remove_if | unique |
| generate | replace | upper_bound |
Algorithms that read from forward iterators and write to output iterators:
rotate_copy
Algorithms that require bidirectional iterators
copy_backward partition
inplace_merge prev_permutation
next_permutation reverse
stable_permutation
Algorithms that read from bidirectional iterators and write to output iterators:
reverse_copy
Algorithms that require random access iterators:
make_heap pop_heap sort nth_element push_heap sort_heap partial_sort random_shuffle stable_sort
Algorithms that read from input iterators and write to random access iterators:
partial_sort_copy
The complexity for each of these algorithms is given in the manual page for that algorithm.
Manual pages for each of the algorithms named in the lists above.