Общие сведения
Стандартная библиотека C++ имеет набор полезных функций (например, сортировки, поиска, подсчета), которые выполняют различные операции с элементами контейнеров и реализованы максимально эффективно. Эти функции независимы и определены в пространстве имен std. Таким образом, их можно применять не только к определенным последовательным контейнерам, но и к обычным массивам! Для того, чтобы появилась возможность использования этих функций необходимо подключить заголовочный файл <algorithm>. От названия библиотеки их принято называть “обобщенные алгоритмы” или просто “алгоритмы”. В качестве аргументов функции принимают итераторы начала (first) и конца (last) диапазона с которым будут производиться операции. Помимо итераторов, функции принимают в качестве аргумента функциональные объекты (или функторы). Некоторые функции имеют логический суффикс _if (например, find_if, count_if и т. д.). Такие функции требуют дополнительный аргумент – предикат (функтор возвращающий булевский тип). В примерах ниже, в качестве функтора, применяется лямбда-выражение. О функторах (и лямбда-выражениях) мы будем подробно говорить на следующем уроке.
Алгоритмы стандартной библиотеки STL разделяются на следующие категории:
- Не изменяющие последовательные операции
- Изменяющие последовательные операции
- Операции сортировки
- Бинарные операции поиска
- Операции слияния
- Кучи
- Операции отношений
В этом уроке мы рассмотрим лишь некоторые из них. Подробные сведения об алгоритмах можно получить, например, здесь.
Немодифицирующие алгоритмы
В немодифицирующих алгоритмах размер массива не изменяется (или элементы не перемещаются на новые позиции).
for_each()
for_each(first, last, func)
Наиболее часто используемый алгоритм. По порядку применяет заданный функтор func к результату разыменования каждого итератора в диапазоне [first, last). Если func возвращает результат, то он игнорируется.
Программа 17.1 (фрагмент)
array<int, 20> mas {};
auto first = mas.begin();
auto last = mas.end();
int i = 0;
for_each(first, last, [&i](int &r) {
r = ++i;
cout << r << " ";
});
Для читабельности программы блок лямбды лучше оформлять так же, как и для обычной функции (как в примере выше), особенно, если в теле лямбды несколько инструкций.
find()
find(first, last, value) find_if(first, last, pred) find_if_not(first, last, pred)
Итераторы: InputIt
Функция находит в диапазоне [first, last) первый элемент, удовлетворяющий определённым условиям:
1. find ищет элемент, равный value
2. find_if ищет элемент, для которого предикат pred возвращает значение true
3. find_if_not ищет элемент, для которого предикат pred возвращает значение false
Программа 17.2 (фрагмент)
array<int, 20> mas {};
auto first = mas.begin();
auto last = mas.end();
default_random_engine rnd(time(0));
uniform_int_distribution<unsigned> d(10, 99);
for_each(first, last, [](int &r) {
r = d(rnd);
cout << r << " ";
});
auto it = find_if(first, last, [](int &r) {
return r > 70;
});
cout << "\nПервый элемент, который > 70 "
"это - "
<< it - mas.begin() + 1
<< "-й"
<< endl;
count()
count(first, last, value) count_if(first, last, pred)
Итераторы: InputIt
Возвращает, сколько раз элемент со значением value входит в последовательность, заданную итераторами first и last.
count_if(first, last, pred) – возвращает, сколько раз предикат pred возвращает значение true.
Например,
count_if(first, last, [](int &r){return !(r % 2);})
вернет, количество четных элементов в массиве.
search()
search(first, last, s_first, s_last); search(first, last, s_first, s_last, pred); search_n(first, last, count, value);
Итераторы: ForwardIt
1. Поиск первого вхождения последовательности [s_first, s_last) в последовательности [first, last - [s_last-s_first]).
2. search_n() первое вхождение одинаковых элементов длиною count, имеющих значение value.
equal()
equal(first1, last1, first2) equal(first1, last1, first2, pred)
Итераторы: InputIt
Возвращает true, если в двух диапазонах элементы одинаковы. Первый диапазон [first1, last1), второй начинается с first2.
Модифицирующие алгоритмы
copy()
copy(first, last, d_first); copy_if(first, last, d_first, pred);
Итераторы: OutputIt (d_first), InputIt (first, last)
1. Копирует элементы из диапазона [first, last) в диапазон, начинающийся с d_first.
2. Второй вариант копирует только те элементы, для которых предикат pred возвращает true
Программа 17.3 (фрагмент)
array<int, 20> mas {};
auto first = mas.begin();
auto last = mas.end();
default_random_engine rnd(time(0));
uniform_int_distribution<unsigned> d(10, 99);
for_each(first, last, [](int &r) {
r = d(rnd);
cout << r << " ";
});
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)
Итераторы: ForwardIt
Присваивает заданное значение value всем элементам диапазона [first, last).
reverse()
reverse(first, last)
Итераторы: BidirIt
Меняет порядок следования элементов в диапазоне [first, last) на противоположный.
replace()
replace(first, last, old, new) replace_if(first, last, pred, new)
Итераторы: ForwardIt
Заменяет все элементы в диапазоне [first, last), удовлетворяющие определенному условию, на new. Первый вариант заменяет элементы, равные old, второй вариант заменяет элементы, для которых предикат pred возвращает true.
remove()
remove(first, last, value) remove_if(first, last, pred)
Итераторы: ForwardIt
Удаляет из диапазона [first, last) все элементы, удовлетворяющие определенному условию. Первый вариант удаляет все элементы, равные value, второй вариант удаляет все элементы, для которых предикат pred возвращает 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); unique(first, last, pred)
Итераторы: ForwardIt
Удаляет все последовательно повторяющиеся элементы из диапазона [first, last) и возвращает итератор на элемент, следующий за последним элементом нового диапазона. Удаление производится путем сдвига диапазона таким образом, что элементы которые должны быть удалены будут перезаписаны. Относительный порядок элементов сохранится, а размер контейнера не изменяется. Итераторы, указывающие на элементы после нового диапазона становятся недействительными.
unique_copy()
unique_copy(first, last, d_first); unique_copy(first, last, d_first, pred);
Итераторы: InputIt, OutputIt
Копирует элементы из диапазона [first, last), в диапазон, начинающийся с d_first, так, чтобы в нём не было последовательных одинаковых элементов.
Программа 17.4 (фрагмент)
array<int, 20> mas {};
auto first = mas.begin();
auto last = mas.end();
default_random_engine rnd(time(0));
uniform_int_distribution<unsigned> d(10, 99);
for_each(first, last, [](int &r) {
r = d(rnd);
cout << r << " ";
});
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) sort(first, last, pred)
Итераторы: RandomIt
Сортировка элементов в диапазоне [first, last) в порядке возрастания.
Для изменения порядка сортировки необходимо использовать предикат, например, greater обеспечит сортировку по убыванию:
sort(first, last, greater<int>())
Операции двоичного поиска (на упорядоченных диапазонах)
binary_search()
binary_search(first, last, value)
Итераторы: ForwardIt
Проверяет, содержится ли в отсортированном диапазоне [first, last) элемент, равный value.
Операции над множествами (на упорядоченных диапазонах)
merge()
merge(first1, last1, first2, last2, d_first); merge(first1, last1, first2, last2, d_first, pred);
Итераторы: InputIt, OutputIt
Объединяет два отсортированных диапазона [first1, last1) и [first2, last2) в один упорядоченный диапазон с началом в d_first.
includes()
includes(first1, last1, first2, last2); includes(first1, last1, first2, last2, pred);
Итераторы: InputIt
Возвращает true, если каждый элемент из упорядоченного диапазона [first2, last2) находится в упорядоченном диапазоне [first, last). Также возвращает true, если [first2, last2) пуст.
Первая версия ожидает, что оба диапазона упорядочены по возрастанию, вторая версия ожидает, что они должны быть упорядочены с заданной функцией сравнения pred.
Операции отношений
max_element()
max_element(first, last)
Возвращает итератор, указывающий на наибольший объект в диапазоне [first, last).
min_element()
min_element(first, last)
Возвращает итератор, указывающий на наименьший объект в диапазоне [first, last).
minmax_element()
minmax_element(first, last);
Итераторы: ForwardIt
Находит наибольший и наименьший элемент в диапазоне [first, last). Возвращается тип pair – пара, состоящая из итератора минимального элемента в качестве первого элемента пары и итератора максимального элемента в качестве второго элемента пары. Если имеется несколько элементов равных min, то возвращается итератор на первый такой элемент. Если имеется несколько элементов равных max, то возвращается итератор на последний такой элемент.
Примечание. Класс pair предназначен для работы с парами значений, как с единым целым. С этим классом мы встретимся позже, при изучении ассоциативных массивов.
Получить значения пары можно следующими способами:
Первый элемент: p.first или get<0>(p) Второй элемент: p.second или get<1>(p)
Программа 17.5 (фрагмент)
array<int, 20> mas {};
auto first = mas.begin();
auto last = mas.end();
default_random_engine rnd(time(0));
uniform_int_distribution<unsigned> d(10, 99);
for_each(first, last, [](int &r) {
r = d(rnd);
cout << r << " ";
});
auto p = minmax_element(first, last);
cout << "min = " << *p.first
<< " Он находится на "
<< p.first - first
<< " позиции\n"
<< "max = " << *p.second
<< " Он находится на "
<< p.second - first
<< " позиции"
<< endl;
Литература
- Прата, Стивен. Язык программирования C++. Лекции и упражнения, 6-е изд.: Пер. с англ. — М.: ООО «И.Д. Вильяме», 2012
- Липпман Б. Стенли, Жози Лажойе, Барбара Э. Му. Язык программирования С++. Базовый курс. Изд. 5-е. М: ООО “И. Д. Вильямс”, 2014
- Эллайн А. C++. От ламера до программера. СПб.: Питер, 2015
- Джосаттис Н. М. Стандартная библиотека C++: справочное руководство, 2-е изд.-М.: Вильямс, 2014
