Standard C++ Library Copyright 1998, Rogue Wave Software, Inc.

Algorithms- 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 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:oGeneric algorithms access the collection through itera- torsoAlgorithms are templatized on iterator typesoEach 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.

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

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

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.