Общие сведения
Стандартная библиотека C++
имеет набор полезных функций (например, сортировки, поиска, подсчета), которые выполняют различные операции с элементами контейнеров и реализованы максимально эффективно. Эти функции определены в пространстве имен std
и, таким образом, их можно применять не только к определенным контейнерам, но и к обычным массивам (если алгоритм подразумевает последовательный контейнер). Для того, чтобы появилась возможность использовать эти функции, необходимо подключить заголовочный файл:
#include <algorithm>
Поскольку алгоритмы являются шаблонными функциями, их принято называть “обобщенные алгоритмы” или просто “алгоритмы”. В качестве аргументов функции принимают итераторы начала (здесь именуются – first
) и конца (last
) диапазона с которым будут производиться операции.
Тип итераторов очень важен, поскольку от этого, в конечном итоге, зависит к каким контейнерам могут применяться данные функции. В таблице ниже перечислены контейнеры и соответствующие им типы итераторов.
Контейнер | Тип итератора |
---|---|
array |
RandomAccessIt |
vector |
RandomAccessIt |
deque |
RandomAccessIt |
forward_list |
ForwardIt |
list |
BidirectionalIt |
set |
BidirectionalIt |
map |
BidirectionalIt |
multiset |
BidirectionalIt |
multimap |
BidirectionalIt |
unordered_set |
ForwardIt |
unordered_map |
ForwardIt |
unordered_multiset |
ForwardIt |
unordered_multimap |
ForwardIt |
Следует учитывать, что сами итераторы находятся в иерархической подчиненности друг к другу: итераторы с более широкими возможностями поддерживают все операции итераторов с менее широкими возможностями.
Помимо итераторов, функции принимают в качестве аргумента функциональные объекты:
- функторы (
fnc
); - предикаты (
prd
); - компараторы (
cmp
).
std
(заголовок numeric
).Алгоритмы стандартной библиотеки STL разделяются на следующие категории:
- Не изменяющие последовательные операции
- Изменяющие последовательные операции
- Операции с разделами
- Операции сортировки
- Бинарные операции поиска (на упорядоченных последовательностях)
- Операции над множествами (на упорядоченных массивах)
- Операции над кучами
- Операции min/max
- Операции сравнения
и другие. В этом уроке мы рассмотрим некоторые из них. Подробные сведения об алгоритмах можно получить, например, здесь. Обратите внимание, что в классах контейнеров реализованы свои методы, аналогичные функциям представленным ниже. В этом случае применять нужно именно встроенные методы, а не обобщенные алгоритмы.
Немодифицирующие алгоритмы
В немодифицирующих алгоритмах размер массива не изменяется (или элементы не перемещаются на новые позиции).
for_each()
for_each(first, last, fnc) for_each_n(first, last, fnc)
Наиболее часто используемый алгоритм. По порядку применяет заданный функтор fnc
к результату разыменования каждого итератора в диапазоне [first, last)
. Если func
возвращает результат, то он игнорируется. Версия for_each_n
в диапазоне [first, first + n)
. В программе ниже массив заполняется рядом четных натуральных чисел и одновременно выводится.
#include <iostream> #include <algorithm> #include <array> using namespace std; int main() { array<int, 20> mas {}; auto first = mas.begin(); auto last = mas.end(); int i = 0; auto fnc = [&i](int &r) {r = ++i * 2; cout << r << " ";}; for_each(first, last, fnc); cout << endl; return 0; }
Вывод
2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40
Проверка логического значения предиката
all_of(first, last, prd) any_of(first, last, prd) none_of(first, last, prd)
Итераторы: InputIt
. Возвращают булевский тип.
1. Проверяет, возвращает ли унарный предикат значение true
для всех элементов в диапазоне [first, last)
.
2. Проверяет, возвращает ли унарный предикат значение true
хотя бы для одного элемента в диапазоне [first, last)
.
3. Проверяет, возвращает ли унарный предикат значение true
для элементов в диапазоне [first, last)
.
if (all_of(first, last, [](int i){return !(i % 2);})) { cout << "Все числа четные\n"; }
find()
find(first, last, value) find_if(first, last, prd) find_if_not(first, last, prd) find_end(first, last, s_first, s_last, [prd]) find_first_of(first, last, s_first, s_last, [prd])
Функция находит в диапазоне [first, last)
первый элемент, удовлетворяющий определённым условиям:
1. find
ищет элемент, равный value
. Итераторы: InputIt
2. find_if
ищет элемент, для которого предикат prd
возвращает значение true
. Итераторы: InputIt
3. find_if_not
ищет элемент, для которого предикат prd
возвращает значение false
. Итераторы: InputIt
4. find_end
ищет последнее вхождение последовательности [s_first, s_last)
в диапазоне [first, last)
. Элементы сравниваются с использованием операции ==
или с использованием заданного двоичного предиката prd
(необязателен). Итераторы: ForwardIt
5. find_first_of
ищет в диапазоне [first, last)
любой из элементов в диапазоне [s_first, s_last)
. Элементы сравниваются с использованием операции ==
или с использованием заданного двоичного предиката prd
(необязателен). Итераторы: ForwardIt
1, 2, 3. Возвращает итератор первого элемента, удовлетворяющего условию, или last
, если такой элемент не найден.
4. Итератор предшествующий последнему появлению последовательности [s_first, s_last)
в диапазоне [first, last)
.
5. Итератор первого элемента в диапазоне [first, last)
, который равен элементу из диапазона [s_first; s_last)
. Если такой элемент не найден, возвращается last
.
#include <iostream> #include <algorithm> #include <array> #include <random> #include <chrono> using namespace std; using namespace chrono; int main() { array<int, 20> mas {}; auto first = mas.begin(); auto last = mas.end(); int seed = system_clock::now().time_since_epoch().count(); for_each(first, last, [seed](int &r) { static default_random_engine rnd(seed); static uniform_int_distribution<int> d(10, 99); r = d(rnd); cout << r << " "; }); auto it = find_if(first, last, [](int r) { return r > 70; }); cout << "\nПервый элемент, который > 70 " "это - " << it - mas.begin() + 1 << "-й" << endl; return 0; }
search()
search(first, last, s_first, s_last [, prd]) search_n(first, last, count, value)
Итераторы: ForwardIt
1. Поиск первого вхождения последовательности [s_first, s_last)
в последовательности [first, last - [s_last-s_first])
. Элементы сравниваются с использованием операции ==
или с использованием заданного двоичного предиката prd
(необязателен).
2. search_n()
первое вхождение одинаковых элементов длиною size_t count
, имеющих значение value
.
count()
count(first, last, value) count_if(first, last, prd)
Итераторы: InputIt
Возвращает, сколько раз элемент со значением value
входит в последовательность, заданную итераторами first
и last
.
count_if(first, last, prd)
– возвращает, сколько раз предикат prd
возвращает значение true
.
Например,
count_if(first, last, [](int &r){return !(r % 2);})
вернет, количество четных элементов в массиве.
equal()
equal(first1, last1, first2 [, prd])
Итераторы: InputIt
Возвращает true
, если в двух диапазонах элементы одинаковы. Первый диапазон [first1, last1)
, второй начинается с first2
. Используется операция ==
, чтобы определить, равны ли два элемента, или двоичный предикат prd
(необязателен).
Модифицирующие алгоритмы
Данный тип алгоритмов будет изменять массив: либо его размер, либо позицию элементов в массиве.
copy()
copy(first, last, d_first) copy_if(first, last, d_first, prd) copy_n(first, count, d_first) copy_backward(first, count, d_first)
Итераторы: OutputIt (d_first)
, InputIt (first, last)
и BidirectionalIt
для copy_backward
.
1. Копирует элементы из диапазона [first, last)
в диапазон, начинающийся с d_first
.
2. Второй вариант копирует только те элементы, для которых предикат pred
возвращает true
3. Копирует size_t count
элементов из диапазона с началом first
в диапазон, начинающийся с d_first
4. Копирует элементы из диапазона [first, last)
, в другой диапазон, заканчивающийся с d_last
. Элементы копируются в обратном порядке (последний элемент копируется первым), но их относительный порядок сохраняется.
vector<int> ar(10); auto d_first = ar.begin(); copy(first, first + (last - first) / 2, d_first); for (auto &r : ar) cout << r << " ";
fill()
fill(first, last, value) fill_n(first, count, value)
Итераторы: ForwardIt
для fill_n
и OutputIt
для fill
Присваивает заданное значение value
всем элементам диапазона [first, last)
. fill_n
присваивает size_t count
значений value
начиная с позиции first
.
reverse()
reverse(first, last) reverse_copy(first, last, d_first)
Итераторы: BidirIt
, OutputIt
(d_first
)
Меняет порядок следования элементов в диапазоне [first, last)
на противоположный. reverse_copy
копирует элементы из диапазона [first, last)
в другой диапазон, начинающийся с d_first
, таким образом, что элементы в новом диапазоне располагаются в обратном порядке.
replace()
replace(first, last, old, new) replace_if(first, last, prd, new) replace_copy(first, last, d_first, old_value, new_value) replace_copy_if(first, last, d_first, prd, new_value)
Итераторы: ForwardIt
для replace
и replace_if
; InputIt
и OutputIt
для replace_copy
и replace_copy_if
Заменяет все элементы в диапазоне [first, last)
, удовлетворяющие определенному условию, на new
.
1. Заменяет элементы, на равные old
2. Заменяет элементы, для которых предикат prd
возвращает true
.
Копирует элементы из диапазона [first, last)
в другой диапазон, начинающийся с d_first
, заменяя все элементы, удовлетворяющие определенным критериям, на значение new
.
3. Заменяет элементы, на равные old
4. Заменяет элементы, для которых предикат prd
возвращает true
.
remove()
remove(first, last, value) remove_if(first, last, prd) remove_copy(first, last, d_first, value) remove_copy_if(first, last, d_first, prd)
Итераторы: ForwardIt
для remove
и remove_if
; InputIt
и OutputIt
для remove_copy
и remove_copy_if
Удаляет из диапазона [first, last)
все элементы, удовлетворяющие определенному условию.
1. Удаляет все элементы, равные value
,
2. Уаляет все элементы, для которых предикат prd
возвращает true
.
Удаление осуществляется путём сдвига элементов внутри диапазона таким образом, что удаляемые элементы перезаписываются. Элементы между старым и новым концами диапазона имеют неопределённое значение. Возвращается итератор на новый конец диапазона. Относительный порядок оставшихся элементов сохраняется.
remove_copy
копирует элементы из диапазона [first, last)
в другой диапазон, начинающийся с d_first
, пропуская элементы, которые удовлетворяют определенным критериям. Исходный и целевой диапазоны не могут перекрываться.
3. Игнорирует все элементы, которые равны value
.
4. Игнорирует все элементы, для которых предикат prd
возвращает true
.
transform()
transform(first1, last1, d_first, unary_op); transform(first1, last1, first2, d_first, binary_op);
Итераторы: InputIt
, OutputIt
Применяет заданную функцию к одному диапазону и сохраняет результат в другой диапазон, начинающийся с d_first
.
1. Унарная операция unary_op
применяется к диапазону [first1, last1)
.
2. Бинарная операция binary_op
применяется к элементам из двух диапазонов: [first1, last1)
и начинающемуся с first2
.
iter_swap()
iter_swap(it1, it2)
Итераторы: ForwardIt
Обменивает объекты, на которые указывают два итератора it1
и it2
.
unique()
unique(first, last [, prd])
Итераторы: ForwardIt
Удаляет все последовательно повторяющиеся элементы из диапазона [first, last)
и возвращает итератор на элемент, следующий за последним элементом нового диапазона. Удаление производится путем сдвига диапазона таким образом, что элементы которые должны быть удалены будут перезаписаны. Относительный порядок элементов сохранится, а размер контейнера не изменяется. Итераторы, указывающие на элементы после нового диапазона становятся недействительными.
unique_copy()
unique_copy(first, last, d_first [, prd])
Итераторы: InputIt
, OutputIt
Копирует элементы из диапазона [first, last)
, в диапазон, начинающийся с d_first
, так, чтобы в нём не было последовательных одинаковых элементов.
vector<int> ar2(20); auto d_first2 = ar2.begin(); cout << endl; unique_copy(first, last, d_first2); for (auto &r : ar2) cout << r << " ";
Возможный вывод:
10 10 12 18 17 17 17 17 14 13 18 18 17 17 11 12 16 17 15 12 10 12 18 17 14 13 18 17 11 12 16 17 15 12 0 0 0 0 0 0
Операции сортировки
sort()
sort(first, last [, cmp])
Итераторы:
RandomIt
Первый вариант осуществляет сортировку по возрастанию. Элементы сравниваются с использованием оператора <
или с использованием заданного компаратора cmp
.
Например, для осуществления сортировки по убыванию необходимо использовать предопределенный предикат - greater<int>()
:
sort(first, last, greater<int>());
Пример использования функций sort
и replace_copy_if
.
sort(first, last); for(auto &i : mas) cout << i << " "; cout << endl; vector<int> ar(20); auto d_first = ar.begin(); auto prd = [](int el){return el < 50;}; replace_copy_if(first, last, d_first, prd, 10); for(auto &i : ar) cout << i << " ";
Рассмотрим пример с сортировкой посложнее. Допустим, нам нужно выполнить сортировку массива пар по возрастанию значений первых элементов пар. Ниже приводим пример такой программы полностью.
#include <iostream> #include <algorithm> #include <random> #include <vector> #include <chrono> using namespace std; using namespace chrono; int main() { vector<pair<int, double>> mas(20); auto first = mas.begin(); auto last = mas.end(); cout << "Исходный массив:\n"; int seed = system_clock::now().time_since_epoch().count(); for_each(first, last, [seed](pair<int, double> &r) { static default_random_engine rnd(seed); static uniform_int_distribution<int> d1(10, 99); static uniform_real_distribution<double> d2(1., 10.); r = {d1(rnd), d2(rnd)}; cout << r.first << "\t" << r.second << endl; }); cout << "Производим сортировку по первому\n" << "элементу пары, по возрастанию" << endl; sort(first, last, [](pair<int, double> a, pair<int, double> b) { return a.first < b.first; // поменять операцию, если нужно }); // изменить направление for (auto &r : mas) { cout << r.first << "\t" << r.second << endl; } return 0; }
is_sorted
is_sorted(first, last [, cmp])
Итераторы: ForwardIt
Проверяет, отсортированы ли элементы в диапазоне [first, last)
по убыванию. Элементы сравниваются с использованием оператора <
или с использованием заданной двоичной функции сравнения cmp
.
partial_sort
partial_sort(first, middle, last [, prd]) partial_sort_copy(first, last, d_first, d_last [, cmp])
Итераторы: RandomIt
; InputIt first
и InputIt last
для partial_sort_copy
Сортирует элементы так, чтобы в диапазоне [first, middle)
содержались упорядоченные элементы из диапазона [first, last)
. Порядок равных элементов не гарантирован. Порядок оставшихся элементов в диапазоне [middle, last)
не указан.
Элементы сравниваются с использованием оператора <
или с использованием заданного компаратора cmp
. partial_sort_copy
переносит отсортированный диапазон в [d_first, d_last)
.
stable_sort
stable_sort(first, last [, cmp])
Итераторы: RandomIt
Сортирует элементы в диапазоне [first, last)
в порядке убывания. Порядок эквивалентных элементов гарантированно сохраняется. Элементы сравниваются с использованием оператора <
или с использованием заданного компаратора cmp
.
Операции двоичного поиска (на упорядоченных диапазонах)
binary_search
binary_search(first, last, value [, cmp])
Итераторы: ForwardIt
Проверяет, содержится ли в отсортированном диапазоне [first, last)
элемент, равный value
. Элементы сравниваются с использованием оператора <
или с использованием заданного компаратора cmp
. Возвращает булевское значение: true
, если найден элемент, равный value
, в противном случае - значение false
.
lower_bound
lower_bound(first, last, value [, cmp])
Итераторы: ForwardIt
Возвращает итератор, указывающий на первый элемент в диапазоне [first, last)
, который не меньше по значению значению value
или last
, если такой элемент не найден. Элементы сравниваются с использованием оператора <
или с использованием заданного компаратора cmp
.
upper_bound
upper_bound(first, last, value [, cmp])
Итераторы: ForwardIt
Возвращает итератор, указывающий на первый элемент в диапазоне [first, last)
, который больше значения value
или last
, если такой элемент не найден. Элементы сравниваются с использованием оператора <
или с использованием заданного компаратора cmp
.
equal_range
equal_range(first, last, value [, cmp])
Итераторы: ForwardIt
Возвращает диапазон (в виде пары), содержащий все элементы, эквивалентные значению в диапазоне [first, last)
. Возвращаемый диапазон определяется двумя итераторами: один указывает на первый элемент, значение которого не меньше value
, а другой указывает на первый элемент, значение которого больше value
. Элементы сравниваются с использованием оператора <
или с использованием заданного компаратора cmp
.
Операции над множествами
merge()
merge(first1, last1, first2, last2, d_first [, cmp])
Итераторы: InputIt
, OutputIt
Объединяет два отсортированных диапазона [first1, last1)
и [first2, last2)
в один упорядоченный диапазон с началом в d_first
. Возвращает OutputIt
итератор для элемента после последнего скопированного элемента.
includes
includes(first1, last1, first2, last2 [, cmp])
Итераторы: InputIt
Возвращает true
, если каждый элемент из упорядоченного диапазона [first2, last2)
находится в упорядоченном диапазоне [first, last)
. Также возвращает true
, если [first2, last2)
пуст.
Первая версия ожидает, что оба диапазона упорядочены по возрастанию, вторая версия ожидает, что они должны быть упорядочены с заданной функцией сравнения cmp
.
set_difference
set_difference(first1, last1, first2, last2, d_first [, cmp])
Итераторы: InputIt
, OutputIt
Копирует элементы из отсортированного диапазона [first1, last1)
, которые не найдены в отсортированном диапазоне [first2, last2)
, в диапазон, начинающийся с d_first
. Возвращает d_last
построенного диапазона.
set_intersection
set_intersection(first1, last1, first2, last2, d_first [, cmp])
Итераторы: InputIt
, OutputIt
Создает отсортированный диапазон, начинающийся с d_first
, состоящий из элементов, которые находятся в обоих отсортированных диапазонах [first1, last1)
и [first2, last2)
. Если какой-либо элемент найден m
раз в [first1, last1)
и n
раз в [first2, last2)
, первые элементы std::min(m, n)
будут скопированы из первого диапазона в диапазон назначения. Порядок эквивалентных элементов сохраняется. Возвращает d_last
построенного диапазона.
set_symmetric_difference
set_symmetric_difference(first1, last1, first2, last2, d_first [, cmp])
Итераторы: InputIt
, OutputIt
Вычисляет симметричную разность двух отсортированных диапазонов: элементы, найденные в любом из диапазонов, но не в обоих, копируются в диапазон, начинающийся с d_first
. Полученный диапазон также будет отсортирован. Возвращает d_last
построенного диапазона.
set_union
set_union(first1, last1, first2, last2, d_first [, cmp])
Итераторы: InputIt
, OutputIt
Создает отсортированное объединение, начинающееся с d_first
, состоящее из набора элементов, присутствующих в одном или обоих отсортированных диапазонах [first1, last1)
и [first2, last2)
. Возвращает d_last
построенного диапазона.
Операции на куче
is_heap
is_heap(first, last [, cmp])
Итераторы: RandomIt
Проверяет, являются ли элементы в диапазоне [first, last)
максимальной кучей. Элементы сравниваются с использованием оператора <
или с использованием заданного компаратора cmp
.
make_heap
make_heap(first, last [, cmp])
Итераторы: RandomIt
Создает максимальную кучу в диапазоне [first, last)
. Элементы сравниваются с использованием оператора <
или с использованием заданного компаратора cmp
. (void
)
push_heap
push_heap(first, last [, cmp])
Итераторы: RandomIt
Вставляет элемент в позиции last-1
максимальной кучи, определенную диапазоном [first, last-1)
. Элементы сравниваются с использованием оператора <
или с использованием заданного компаратора cmp
.
pop_heap
pop_heap(first, last [, cmp])
Итераторы: RandomIt
Меняет значение в позиции first
и значение в позиции last-1
и превращает поддиапазон [first, last-1)
в кучу. Это приводит к удалению первого элемента из кучи, определенной диапазоном [first, last)
. Элементы сравниваются с использованием оператора <
или с использованием заданного компаратора cmp
.
sort_heap
sort_heap(first, last [, cmp])
Итераторы: RandomIt
Преобразует максимальную кучу [first, last-1)
в отсортированный диапазон в порядке возрастания. Результирующий диапазон больше не имеет свойства кучи. Элементы сравниваются с использованием оператора <
или с использованием заданного компаратора cmp
.
Операции отношений
max_element()
max_element(first, last)
Итераторы: ForwardIt
Возвращает итератор, указывающий на наибольший объект в диапазоне [first, last)
.
min_element()
min_element(first, last)
Итераторы: ForwardIt
Возвращает итератор, указывающий на наименьший объект в диапазоне [first, last)
.
minmax_element()
minmax_element(first, last);
Итераторы: ForwardIt
Находит наибольший и наименьший элемент в диапазоне [first, last)
. Возвращается тип pair
- пара, состоящая из итератора минимального элемента в качестве первого элемента пары и итератора максимального элемента в качестве второго элемента пары. Если имеется несколько элементов равных min, то возвращается итератор на первый такой элемент. Если имеется несколько элементов равных max, то возвращается итератор на последний такой элемент.
auto p = minmax_element(first, last); cout << "min = " << *p.first << " Он находится на " << p.first - first << " позиции\n" << "max = " << *p.second << " Он находится на " << p.second - first << " позиции" << endl;
Числовые операции
partial_sum
partial_sum(first, last, d_first [, prd])
Итераторы: InputIt
, OutputIt
Вычисляет частичные суммы элементов в поддиапазонах диапазона [first, last)
и записывает их в диапазон, начинающийся с d_first
. Применяет std::move
к своим операндам с левой стороны.