Personal tools
Document Actions
Algorithms
Click on the banner to return to the class reference home page.
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 provides a very flexible framework for applying generic algorithms to containers. The library also provides a rich set of these algorithms for searching, sorting, merging, transforming, scanning, and much 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 provides both in place and copy versions of many algorithms, such as replace and replace_copy. The library also provides 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 (e.g., replace, which will use 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 Iterators 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_intersedtion 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
inplace_merge prev_permutation
next_permutation reverse
stable_permutation
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 1996, Rogue Wave Software, Inc.
