Алгоритмы стандартной библиотеки C++

Общие подходы

Заголовочный файл algorithm содержит много полезных алгоритмов.

Большинство из этих алгоритмов принимают в качестве параметра два итератора, будем обозначать их first и last. В этом случае алгоритм работает с элементами контейнера от first включительно до last невключительно. Чаще всего в качестве first используется метод begin(), а в качестве last - метод end(), в этом случае алгоритм применяется ко всему контейнеру. Например,

sort(a.begin(), a.end());

Используя операции "+" и "-" для итераторов можно применять алгоритмы не для всего контейнера, а для части.

Можно передавать также reverse_iteraror, наиболее употребительный способ использования - это сортировка в обратном порядке при помощи:

sort(a.rbegin(), e.rend());

Алгоритмы поиска

find

Алгоритм find(first, last, val) осуществляет линейный поиск значения val от итератора first до итератора last. Элементы просматриваются последовательность, возвращается итератор на первый найденный элемент. Если элемент val не будет найден, то возвращается значение итератора last.

binary_search

Алгоритм binary_search(first, last, val) осуществляет двоичный поиск значения val. Контейнер должен быть упорядочен. Возвращается значение типа bool, то есть true или false в зависимости от того, есть ли такой элемент в контейнере.

lower_bound

Алгоритм lower_bound(first, last, val) осуществляет двоичный поиск значения val и возвращает итератор res на первый элемент, который не меньше, чем val, то есть *res>=val, a *(res-1)<val. Если все элементы контейнера (начиная с first) будут не меньше, чем val, то будет возвращено значение first. Если в контейнере все элементы меньше val, то возвращается значение last.

upper_bound

Алгоритм upper_bound(first, last, val) осуществляет двоичный поиск значения val и возвращает итератор res на первый элемент, который строго больше, чем val, то есть *res>val, a *(res-1)<=val. Если же все элементы контейнера (начиная с first) будут больше, чем val, то будет возвращено значение first. Если в контейнере все элементы меньше или равны  val, то возвращается значение last.

Алгоритмы сортировки, разворота, сдвига

sort

sort(first, last) - упорядочивает элементы контейнера по неубыванию.

stable_sort

sort(first, last) - упорядочивает элементы контейнера по неубыванию, при этом равные элементы не переставляются (так называемая "устойчивая сортировка").

reverse

reverse(first, last) - разворачивает фрагмент контейнера в обратном порядке, переставляя элементы, равноудаленные от концов.

rotate

reverse(first, n_first, last) - осуществляет циклический сдвиг фрагмента контейнера. Элемент, на который указывает итератор n_first становится первым элементом (то есть переходит на место элемента first), элемент n_first+1 - вторым и т.д.

Перестановки

next_permutation

next_permutation(first, last) - переставляет элементы так, чтобы получилась следующая в лексикографическом порядке перестановка. Можно применять не только к векторам, но и к строкам (как и многие другие алгоритмы). Метод возвращает true, если удалось построить следующую в лексикографическом порядке перестановку. Если же первоначальная перестановка уже была максимальной в лексикографическом порядке, то метод генерирует минимальную в лексикографическом порядке перестановку и возвращает false.

Например, вывести все перестановки в лексикографическом порядке можно так:

do

{

    for (auto x: a)

        cout << x;

    cout << endl;

}

while(next_permutation(a.begin(), a.end());

prev_permutation

prev_permutation(first, last) - переставляет элементы так, чтобы получилась предыдущая в лексикографическом порядке перестановка. Можно применять не только к векторам, но и к строкам (как и многие другие алгоритмы). Метод возвращает true, если удалось построить предыдущую в лексикографическом порядке перестановку. Если же первоначальная перестановка уже была минимальной в лексикографическом порядке, то метод генерирует максимальную в лексикографическом порядке перестановку и возвращает false.

random_shuffle

random_shuffle(first, last) - делает случайную перестановку элементов контейнера.

Минимальные и максимальные элементы, подсчет

min_element

Алгоритм min_element(first, last) находит минимальный элемент в контейнере и возвращает итератор на этот элемент. Если есть несколько элементов, равных минимальному, возвращается значение первого из них.

max_element

max_element(first, last) возвращает итератор на наибольший элемент. Если есть несколько элементов, равных наибольшему - то на первый из них.

count

count(first, last, val)  -- подсчитывает сколько элементов контейнера равны значению val.