Algorithms

Library:  Algorithms

• Local Index
• Summary
• Synopsis
• Description
• Algorithms by Mutating/Non-mutating Function
• Algorithms by Operation
• Algorithms by Category
• Complexity
• See Also
• Standards Conformance

Generic algorithms for performing various operations on containers and sequences

#include <algorithm>

namespace std {
  // synopsis of the entry
}

The synopsis of each algorithm appears in its entry in this Reference Guide.

The C++ Standard Library allows you to apply generic algorithms to containers, and it supplies a set of these algorithms for searching, sorting, merging, transforming, scanning, and 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 mutate (alter) the contents of a container fall into the mutating group. All others are considered nonmutating. For example, both fill() and sort() are mutating algorithms, while find() and for_each() are nonmutating.

Nonmutating operations

accumulate()       find_end()                 max_element()
adjacent_find()    find_first_of()            min()
binary_search()    find_if()                  min_element()
count()            for_each()                 mismatch() 
count_if()         includes()                 search()
equal()            lexicographical_compare()  search_n()
equal_range()      lower_bound()              upper_bound()
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 cases where overloading proved impractical or impossible, the names differ. For example, replace() uses equality to determine replacement, and replace_if()accesses a user-provided compare function.

We can further distinguish algorithms by the kind of operations they perform. The following lists categorize algorithms by their operations.

Assigning operations

fill()                          generate()
fill_n()                        generate_n()

Search operations

adjacent_find()                 find_end()
count()                         find_if()
count_if()                      find_first_of()
find()                          search()
                                search_n()

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 lists organize 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()
count()                find_if()
count_if()             includes()
equal()                lexicographical_compare()
for_each()             mismatch()

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()           set_union()
copy()                replace_copy_if()        transform()
merge()               set_difference()         unique_copy()
remove_copy()         set_intersection()
remove_copy_if()      set_symmetric_difference()

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()

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.

ISO/IEC 14882:1998 -- International Standard for Information Systems -- Programming Language C++, Section 25