Generic Algorithms
Generic algorthims are template functions that use iterators to do their thing on almost
any (qualifying) container. For example:
template < class InputIterator, class T >
InputIterator find(InputIterator first, InputIterator last,
const T& value) {
while (first != last && *first != value) ++first;
return first;
}
There is also often a predicate version which takes a function object argument as
well as an iterator type:
template < class InputIterator, class Predicate >
InputIterator find_if(InputIterator first, InputIterator last,
Predicate pred) {
while (first != last && !pred(*first)) ++first;
return first;
}
In addition, mutating operators often have a copy version that does not change
the original range but does its job on a new range built from copying the range (using an
output iterator). For example:
template < class InputIterator, class OutputIterator, class T >
OutputIterator replace_copy(InputIterator first,
InputIterator last,
OutputIterator result,
const T& old_value,
const T& new_value) {
while (first != last) {
*result++ = *first == old_value ?
new_value :
*first; ++first; }
return result;
}
Non-mutating sequence operations
for_each()
- Apply a function to each element in a sequence.
find()
- Find the first matching element in a sequence.
- Also
find_if()
.
find_end()
- Return the last iterator in a matching sequence.
find_first_of()
- Return the first iterator in a matching sequence.
adjacent_find()
- Find two adjacent matching elements.
count()
- Count the number of matching elements.
mismatch()
- Find the first two mismatched elements.
equal()
- Test two sequences for equality.
search()
- Search for a sequence
- Search for equal values.
Mutating sequence operations
copy()
- Copies a range of elments to a second range.
- Also
copy_backward()
.
swap()
- Swaps two elements.
- Also
iter_swap
(swaps two elements pointed by iterators).
- Also
swap_ranges
(swaps two ranges).
transform()
- Performs an operation on one or two sequences storing the new result.
replace()
- Replace selected elements in a range.
- Also
replace_copy(), replace_if(), replace_copy_if()
.
fill()
- Fills a range with a specific value.
- Also
fill_n
.
generate()
- Fills a range with a generated value.
- Also
generate_n
.
remove()
- Removes specific values from a range.
- Also
remove_if(), remove_copy(), remove_copy_if
.
unique()
- Eliminates runs of equal values from a range (container must have been sorted).
- Also
unique_if(), unique_copy(), unique_copy_if()
.
reverse()
- Reverses a sequence.
- Also
reverse_copy()
.
rotate()
- Rotates the elements of a sequence.
- Also
rotate_copy()
.
random_shuffle()
partition()
- Divides a range into two partitions (for quicksort).
- Also
stable_partition()
.
Sorting and Searching
sort()
- Sorts range using NlogN comparisons.
stable_sort()
- Sorts while preserving relative order of elements.
partial_sort()
- Puts the first N elements in their proper places.
- Also
partial_sort_copy()
.
nth_element()
- Puts elements N in its proper place in the range.
lower_bound()
- Finds the first position where an element can be inserted.
upper_bound()
- Finds the last position where an element can be inserted.
equal_range()
- Returns
lower_bound()
and upper_bound()
.
binary_search()
- Finds an element in the range.
merge()
- Merges two sorted ranges.
- Also
inplace_merge()
(merges two consecutive ranges).
Sets
includes()
set_union()
set_intersection()
set_difference()
set_symmetric_difference()
Heaps
- Heaps are binary trees implemented over other sequence containers.
- heap.right(m) = heap[2m+1]
- heap.left(m) = heap[2m+2]
- heap.parent(k) = heap[k/2]
push_heap()
pop_heap()
make_heap()
sort_heap()
Numeric algorithms
accumulate()
inner_product()
partial_sum()
adjacent_differences()
Miscellaneous
min()
max()
min_element()
max_element()
lexicographical_compare()
next_permutation()
prev_permutation()