Standard C++ Library
Copyright 1998, Rogue Wave Software, Inc.
NAME
Algorithms
- Generic algorithms for performing various operations on
containers and sequences.
SYNOPSIS
#include <algorithm>
The synopsis of each algorithm appears in its entry in the
reference guide.
DESCRIPTION
The Standard C++ Library allows you to apply generic algo-
rithms to containers, and it supplies a set of these algo-
rithms for searching, sorting, merging, transforming, scan-
ning, and more.
Each algorithm can be applied to a variety of containers,
including those defined by a user of the library. The fol-
lowing design features make algorithms generic:
o Generic algorithms access the collection through itera-
tors
o Algorithms are templatized on iterator types
o 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 previ-
ously 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 sec-
tion below. They can also be grouped according to the type
of operation they perform.
ALGORITHMS BY MUTATING/NON-MUTATING FUNCTION
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
equal_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 has place and copy versions of many
algorithms, such as replace and replace_copy. The library
also has 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 (for example, replace, which uses equality to
determine replacement, and replace_if, which accesses a
user-provided compare function).
ALGORITHMS BY OPERATION
We can further distinguish algorithms by the kind of opera-
tions 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
ALGORITHMS BY CATEGORY
Each algorithm requires certain kinds of iterators (for a
description of the iterators and their capabilities see the
Iterator_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 out-
put iterators:
adjacent_difference replace_copy transform
copy replace_copy_if unique_copy
merge set_difference
partial_sum set_intersection
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 stable_permutation
inplace_merge prev_permutation
next_permutation reverse
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 ran-
dom access iterators:
partial_sort_copy
COMPLEXITY
The complexity for each of these algorithms is given in the
manual page for that algorithm.
SEE ALSO
Manual pages for each of the algorithms named in the lists
above.