Заголовочный файл algorithm содержит много полезных алгоритмов.
Большинство из этих алгоритмов принимают в качестве параметра два итератора, будем обозначать их first и last. В этом случае алгоритм работает с элементами контейнера от first включительно до last невключительно. Чаще всего в качестве first используется метод begin(), а в качестве last - метод end(), в этом случае алгоритм применяется ко всему контейнеру. Например,
sort(a.begin(), a.end());
Используя операции "+" и "-" для итераторов можно применять алгоритмы не для всего контейнера, а для части.
Можно передавать также reverse_iteraror, наиболее употребительный способ использования - это сортировка в обратном порядке при помощи:
sort(a.rbegin(), e.rend());
Алгоритм find(first, last, val) осуществляет линейный поиск значения val от итератора first до итератора last. Элементы просматриваются последовательность, возвращается итератор на первый найденный элемент. Если элемент val не будет найден, то возвращается значение итератора last.
Алгоритм binary_search(first, last, val) осуществляет двоичный поиск значения val. Контейнер должен быть упорядочен. Возвращается значение типа bool, то есть true или false в зависимости от того, есть ли такой элемент в контейнере.
Алгоритм lower_bound(first, last, val) осуществляет двоичный поиск значения val и возвращает итератор res на первый элемент, который не меньше, чем val, то есть *res>=val, a *(res-1)<val. Если все элементы контейнера (начиная с first) будут не меньше, чем val, то будет возвращено значение first. Если в контейнере все элементы меньше val, то возвращается значение last.
Алгоритм upper_bound(first, last, val) осуществляет двоичный поиск значения val и возвращает итератор res на первый элемент, который строго больше, чем val, то есть *res>val, a *(res-1)<=val. Если же все элементы контейнера (начиная с first) будут больше, чем val, то будет возвращено значение first. Если в контейнере все элементы меньше или равны val, то возвращается значение last.
sort(first, last) - упорядочивает элементы контейнера по неубыванию.
sort(first, last) - упорядочивает элементы контейнера по неубыванию, при этом равные элементы не переставляются (так называемая "устойчивая сортировка").
reverse(first, last) - разворачивает фрагмент контейнера в обратном порядке, переставляя элементы, равноудаленные от концов.
reverse(first, n_first, last) - осуществляет циклический сдвиг фрагмента контейнера. Элемент, на который указывает итератор n_first становится первым элементом (то есть переходит на место элемента first), элемент n_first+1 - вторым и т.д.
next_permutation(first, last) - переставляет элементы так, чтобы получилась следующая в лексикографическом порядке перестановка. Можно применять не только к векторам, но и к строкам (как и многие другие алгоритмы). Метод возвращает true, если удалось построить следующую в лексикографическом порядке перестановку. Если же первоначальная перестановка уже была максимальной в лексикографическом порядке, то метод генерирует минимальную в лексикографическом порядке перестановку и возвращает false.
Например, вывести все перестановки в лексикографическом порядке можно так:
do
{
for (auto x: a)
cout << x;
cout << endl;
}
while(next_permutation(a.begin(), a.end());
prev_permutation(first, last) - переставляет элементы так, чтобы получилась предыдущая в лексикографическом порядке перестановка. Можно применять не только к векторам, но и к строкам (как и многие другие алгоритмы). Метод возвращает true, если удалось построить предыдущую в лексикографическом порядке перестановку. Если же первоначальная перестановка уже была минимальной в лексикографическом порядке, то метод генерирует максимальную в лексикографическом порядке перестановку и возвращает false.
random_shuffle(first, last) - делает случайную перестановку элементов контейнера.
Алгоритм min_element(first, last) находит минимальный элемент в контейнере и возвращает итератор на этот элемент. Если есть несколько элементов, равных минимальному, возвращается значение первого из них.
max_element(first, last) возвращает итератор на наибольший элемент. Если есть несколько элементов, равных наибольшему - то на первый из них.
count(first, last, val) -- подсчитывает сколько элементов контейнера равны значению val.