Алгоритмы
Алгоритмы являются важнейшей частью стандартной библиотеки C++. Алгоритмы работают не с самими контейнерами, а с итераторами. Поэтому один и тот же алгоритм можно использовать с большинством, а то и со всеми контейнерами стандартной библиотеки C++. В этом разделе рассматриваются правила и терминология алгоритмов стандартной библиотеки C++.
Комментарии
Описания шаблонов функций алгоритма используют несколько сокращенных фраз:
- Фраза «в диапазоне [A, B)» означает последовательность нулевых или более дискретных значений, начиная с A до , но не включая B. Диапазон действителен, только если B доступен из A, можно сохранить A в объекте N (N = A), можно увеличить объект ноль или более раз (++N), а объект равен B после конечного числа приращений (N == B).
- Фраза «каждый N в диапазоне [A, B)» означает, что N начинается со значения A и увеличивается ноль или более раз, пока не будет равно значению B. Случай N == B не в диапазоне.
- Фраза «наименьшее значение N в диапазоне [A, B) таким образом, что X» означает, что условие X определяется для каждого N в диапазоне [AB) вплоть до выполнения условия X.
- Фраза «наибольшее значение N в диапазоне [A, B), так что X» означает, что X определяется для каждого N в диапазоне [A, B). Функция сохраняет в K копию N при каждом выполнении условия X . Если происходит такое хранение, функция заменяет конечное значение N, равное B, на значение K. Однако для итератора с двунаправленным или случайным доступом это также может означать, что N начинается с наибольшего значения в диапазоне и уменьшается по диапазону до тех пор, пока не будет выполнено условие X .
- Выражения, такие как X — Y, где X и Y могут быть итераторами, отличными от итераторов произвольного доступа, предназначены в математическом смысле. Функция не обязательно вычисляет оператор — , если она должна определить такое значение. То же самое справедливо и для таких выражений, как X + N и X — N, где N — целочисленный тип.
Несколько алгоритмов используют предикат, выполняющие попарное сравнение, например, operator== , для получения результата bool . Функция предиката operator== или любая ее замена не должны изменять ни один из операндов. Он должен давать один и тот же bool результат при каждой оценке, и должен давать тот же результат, если копия любого из операндов заменяется операндом.
Некоторые алгоритмы используют предикат, который налагает строгое слабое упорядочение к парам элементов из последовательности. Для предиката pred(X, Y):
- Строгий означает, что pred(X, X) имеет значение false.
- Слабый означает, что X и Y имеют эквивалентный порядок, если ! pred(X, Y) && !pred(Y, X) (X == Y не нужно определять).
- Упорядочение означает, что pred(X, Y) &&pred(Y, Z) подразумевает pred(X, Z).
Некоторые из этих алгоритмов неявно используют предикат XY. Другие предикаты, которые обычно удовлетворяют строгим требованиям к упорядочению, — это X>Y, less (X, Y) и greater (X, Y). Однако обратите внимание, что предикаты, такие как XY и X>= Y , не удовлетворяют этому требованию.
Последовательность элементов, обозначаемых итераторами в диапазоне [ First , Last ), представляет собой кучу, упорядоченную по operator< , если для каждого N в диапазоне [1, Last — First ) предикат !( *Первое < *(First + N)) имеет значение true. (Первый элемент является самым большим.) В противном случае его внутренняя структура известна только функциям make_heap шаблона , pop_heap и push_heap . Как и в случае с упорядоченной последовательностью, функция operator < предиката или любая замена для нее не должны изменять ни один из своих операндов, и она должна налагать строгий слабый порядок для сравниваемых операндов. Он должен давать один и тот же bool результат при каждой оценке, и должен давать тот же результат, если копия любого из операндов заменяется операндом.
Алгоритмы стандартной библиотеки C++ находятся в файлах заголовков и .
Algorithm h in cpp
The header defines a collection of functions especially designed to be used on ranges of elements.
A range is any sequence of objects that can be accessed through iterators or pointers, such as an array or an instance of some of the STL containers. Notice though, that algorithms operate through iterators directly on the values, not affecting in any way the structure of any possible container (it never affects the size or storage allocation of the container).
Functions in
Non-modifying sequence operations:
all_of Test condition on all elements in range (function template) any_of Test if any element in range fulfills condition (function template) none_of Test if no elements fulfill condition (function template) for_each Apply function to range (function template) find Find value in range (function template) find_if Find element in range (function template) find_if_not Find element in range (negative condition) (function template) find_end Find last subsequence in range (function template) find_first_of Find element from set in range (function template) adjacent_find Find equal adjacent elements in range (function template) count Count appearances of value in range (function template) count_if Return number of elements in range satisfying condition (function template) mismatch Return first position where two ranges differ (function template) equal Test whether the elements in two ranges are equal (function template) is_permutation Test whether range is permutation of another (function template) search Search range for subsequence (function template) search_n Search range for elements (function template)
Modifying sequence operations:
copy Copy range of elements (function template) copy_n Copy elements (function template) copy_if Copy certain elements of range (function template) copy_backward Copy range of elements backward (function template) move Move range of elements (function template) move_backward Move range of elements backward (function template) swap Exchange values of two objects (function template) swap_ranges Exchange values of two ranges (function template) iter_swap Exchange values of objects pointed to by two iterators (function template) transform Transform range (function template) replace Replace value in range (function template) replace_if Replace values in range (function template) replace_copy Copy range replacing value (function template) replace_copy_if Copy range replacing value (function template) fill Fill range with value (function template) fill_n Fill sequence with value (function template) generate Generate values for range with function (function template) generate_n Generate values for sequence with function (function template) remove Remove value from range (function template) remove_if Remove elements from range (function template) remove_copy Copy range removing value (function template) remove_copy_if Copy range removing values (function template) unique Remove consecutive duplicates in range (function template) unique_copy Copy range removing duplicates (function template) reverse Reverse range (function template) reverse_copy Copy range reversed (function template) rotate Rotate left the elements in range (function template) rotate_copy Copy range rotated left (function template) random_shuffle Randomly rearrange elements in range (function template) shuffle Randomly rearrange elements in range using generator (function template)
Partitions:
is_partitioned Test whether range is partitioned (function template) partition Partition range in two (function template) stable_partition Partition range in two — stable ordering (function template) partition_copy Partition range into two (function template) partition_point Get partition point (function template)
Sorting:
sort Sort elements in range (function template) stable_sort Sort elements preserving order of equivalents (function template) partial_sort Partially sort elements in range (function template) partial_sort_copy Copy and partially sort range (function template) is_sorted Check whether range is sorted (function template) is_sorted_until Find first unsorted element in range (function template) nth_element Sort element in range (function template)
Binary search (operating on partitioned/sorted ranges):
lower_bound Return iterator to lower bound (function template) upper_bound Return iterator to upper bound (function template) equal_range Get subrange of equal elements (function template) binary_search Test if value exists in sorted sequence (function template)
Merge (operating on sorted ranges):
merge Merge sorted ranges (function template) inplace_merge Merge consecutive sorted ranges (function template) includes Test whether sorted range includes another sorted range (function template) set_union Union of two sorted ranges (function template) set_intersection Intersection of two sorted ranges (function template) set_difference Difference of two sorted ranges (function template) set_symmetric_difference Symmetric difference of two sorted ranges (function template)
Heap:
push_heap Push element into heap range (function template) pop_heap Pop element from heap range (function template) make_heap Make heap from range (function template) sort_heap Sort elements of heap (function template) is_heap Test if range is heap (function template) is_heap_until Find first element not in heap order (function template)
Min/max:
min Return the smallest (function template) max Return the largest (function template) minmax Return smallest and largest elements (function template) min_element Return smallest element in range (function template) max_element Return largest element in range (function template) minmax_element Return smallest and largest elements in range (function template)
Other:
lexicographical_compare Lexicographical less-than comparison (function template) next_permutation Transform range to next permutation (function template) prev_permutation Transform range to previous permutation (function template)