Algorithms(3C++)

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

Museum