24.4 Lista algorytmów

Biblioteka standardowa dostarcza oczywiście dużo więcej narzędzi niż te, o których tu wspomnieliśmy. Pełny ich opis można znaleźć w książkach cytowanych w spisie literatury .

Poniżej podamy tylko nazwy i skrócony opis algorytmów z biblioteki standardowej, bez szczegółów; powinno to ułatwić poszukiwanie właściwego dla problemu nad którym pracujemy (na przykład ze strony en.cppreference.com):

*** Non-modifying sequence operations — header algorithm

all_of, any_of, none_of (C++11) checks if a predicate is true for all, any or none of the elements in a range

for_each applies a function to a range of elements

for_each_n (C++17) applies a function object to the first n elements of a sequence

countcount_if returns the number of elements satisfying specific criteria

mismatch finds the first position where two ranges differ

find, find_if, find_if_not (C++11) finds the first element satisfying specific criteria

find_end finds the last sequence of elements in a certain range

find_first_of searches for any one of a set of elements

adjacent_find finds the first two adjacent items that are equal (or satisfy a given predicate)

search searches for a range of elements

search_n searches a range for a number of consecutive copies of an element

*** Modifying sequence operations — header algorithm

copy, copy_if (C++11) copies a range of elements to a new location

copy_n (C++11) copies a number of elements to a new location

copy_backward copies a range of elements in backwards order

move (C++11) moves a range of elements to a new location

move_backward (C++11) moves a range of elements to a new location in backwards order

fill copy-assigns the given value to every element in a range

fill_n copy-assigns the given value to N elements in a range

transform applies a function to a range of elements

generate assigns the results of successive function calls to every element in a range

generate_n assigns the results of successive function calls to N elements in a range

remove, remove_if removes elements satisfying specific criteria

remove_copy, remove_copy_if copies a range of elements omitting those that satisfy specific criteria

replace, replace_if replaces all values satisfying specific criteria with another value

replace_copy, replace_copy_if copies a range, replacing elements satisfying specific criteria with another value

swap swaps the values of two objects

swap_ranges swaps two ranges of elements

iter_swap swaps the elements pointed to by two iterators

reverse reverses the order of elements in a range

reverse_copy creates a copy of a range that is reversed

rotate rotates the order of elements in a range

rotate_copy copies and rotate a range of elements

shift_left, shift_right (C++20) shifts elements in a range

shuffle (C++11) randomly re-orders elements in a range

sample (C++17) selects n random elements from a sequence

unique removes consecutive duplicate elements in a range

unique_copy creates a copy of some range of elements that contains no consecutive duplicates

*** Partitioning operations — header algorithm

is_partitioned (C++11) determines if the range is partitioned by the given predicate

partition divides a range of elements into two groups

partition_copy (C++11) copies a range dividing the elements into two groups

stable_partition divides elements into two groups while preserving their relative order

partition_point (C++11) locates the partition point of a partitioned range

*** Sorting operations — header algorithm

is_sorted (C++11) checks whether a range is sorted into ascending order

is_sorted_until (C++11) finds the largest sorted subrange

sort sorts a range into ascending order

partial_sort sorts the first N elements of a range

partial_sort_copy copies and partially sorts a range of elements

stable_sort sorts a range of elements while preserving order between equal elements

nth_element partially sorts the given range making sure that it is partitioned by the given element

*** Binary search operations on sorted ranges — header algorithm

lower_bound returns an iterator to the first element not less than the given value

upper_bound returns an iterator to the first element greater than a certain value

binary_search determines if an element exists in a certain range

equal_range returns range of elements matching a specific key

*** Other operations on sorted ranges — header algorithm

merge merges two sorted ranges

inplace_merge merges two ordered ranges in-place

*** Set operations on sorted ranges — header algorithm

includes returns true if one set is a subset of another

set_difference computes the difference between two sets

set_intersection computes the intersection of two sets

set_symmetric_difference computes the symmetric difference between two sets

set_union computes the union of two sets

*** Heap operations — header algorithm

is_heap (C++11) checks if the given range is a max heap

is_heap_until (C++11) finds the largest subrange that is a max heap

make_heap creates a max heap out of a range of elements

push_heap adds an element to a max heap

pop_heap removes the largest element from a max heap

sort_heap turns a max heap into a range of elements sorted in ascending order

*** Minimum/maximum operations — header algorithm

max returns the greater of the given values

max_element returns the largest element in a range

min returns the smaller of the given values

min_element returns the smallest element in a range

minmax (C++11) returns the smaller and larger of two elements

minmax_element (C++11) returns the smallest and the largest elements in a range

clamp (C++17) clamps a value between a pair of boundary values

*** Comparison operations — header algorithm

equal determines if two sets of elements are the same

lexicographical_compare returns true if one range is lexicographically less than another

compare_3way (C++20) compares two values using three-way comparison

lexicographical_compare_3way (C++20) compares two ranges using three-way comparison

*** Permutation operations — header algorithm

is_permutation (C++11) determines if a sequence is a permutation of another sequence

next_permutation generates the next greater lexicographic permutation of a range of elements

prev_permutation generates the next smaller lexicographic permutation of a range of elements

*** Numeric operations — header numeric

iota (C++11) fills a range with successive increments of the starting value

accumulate sums up a range of elements

inner_product computes the inner product of two ranges of elements

adjacent_difference computes the differences between adjacent elements in a range

partial_sum computes the partial sum of a range of elements

reduce (C++17) similar to std::accumulate, except out of order

exclusive_scan (C++17) similar to std::partial_sum, excludes the ith input element from the ith sum

inclusive_scan (C++17) similar to std::partial_sum, includes the ith input element in the ith sum

transform_reduce (C++17) applies a functor, then reduces out of order

transform_exclusive_scan (C++17) applies a functor, then calculates exclusive scan

transform_inclusive_scan (C++17) applies a functor, then calculates inclusive scan

*** Operations on uninitialized memory — header memory

uninitialized_copy copies a range of objects to an uninitialized area of memory

uninitialized_copy_n (C++11) copies a number of objects to an uninitialized area of memory

uninitialized_fill copies an object to an uninitialized area of memory, defined by a range

uninitialized_fill_n copies an object to an uninitialized area of memory, defined by a start and a count

uninitialized_move (C++17) moves a range of objects to an uninitialized area of memory

uninitialized_move_n (C++17) moves a number of objects to an uninitialized area of memory

uninitialized_default_construct (C++17) constructs objects by default-initialization in an uninitialized area of memory, defined by a range

uninitialized_default_construct_n (C++17) constructs objects by default-initialization in an uninitialized area of memory, defined by a start and a count

uninitialized_value_construct (C++17) constructs objects by value-initialization in an uninitialized area of memory, defined by a range

uninitialized_value_construct_n (C++17) constructs objects by value-initialization in an uninitialized area of memory, defined by a start and a count

destroy_at (C++17) destroys an object at a given address

destroy (C++17) destroys a range of objects

destroy_n (C++17) destroys a number of objects in a range