## Algorithms

- Summary
- Data Type and Member Function Indexes
- Synopsis
- Description
- Algorithms by Mutating/Non-mutating Function
- Algorithms by Operation
- Algorithms by Category
- Complexity
- See Also

### Summary

Generic algorithms for performing various operations on containers and sequences.

### Data Type and Member Function Indexes
(exclusive of constructors and destructors)

None

### 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 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.

### 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 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

### 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 output 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 random 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.

Copyright (c) 1998, Rogue Wave Software, Inc.
Send mail to report errors or comment on the documentation.
OEM Release, June 1998