§19 Библиотека обобщенных алгоритмов

Общие сведения

Стандартная библиотека C++ имеет набор полезных функций (например, сортировки, поиска, подсчета), которые выполняют различные операции с элементами контейнеров и реализованы максимально эффективно. Эти функции определены в пространстве имен std и, таким образом, их можно применять не только к определенным контейнерам, но и к обычным массивам (если алгоритм подразумевает последовательный контейнер). Для того, чтобы появилась возможность использовать эти функции, необходимо подключить заголовочный файл:

#include <algorithm>

Поскольку алгоритмы являются шаблонными функциями, их принято называть “обобщенные алгоритмы” или просто “алгоритмы”. В качестве аргументов функции принимают итераторы начала (здесь именуются – first) и конца (last) диапазона с которым будут производиться операции.
Тип итераторов очень важен, поскольку от этого, в конечном итоге, зависит к каким контейнерам могут применяться данные функции. В таблице ниже перечислены контейнеры и соответствующие им типы итераторов.

Следует учитывать, что сами итераторы находятся в иерархической подчиненности друг к другу: итераторы с более широкими возможностями поддерживают все операции итераторов с менее широкими возможностями.

Помимо итераторов, функции принимают в качестве аргумента функциональные объекты:

1. Не изменяющие последовательные операции
2. Изменяющие последовательные операции
3. Операции с разделами
4. Операции сортировки
5. Бинарные операции поиска (на упорядоченных последовательностях)
6. Операции над множествами (на упорядоченных массивах)
7. Операции над кучами
8. Операции min/max
9. Операции сравнения

и другие. В этом уроке мы рассмотрим некоторые из них. Подробные сведения об алгоритмах можно получить, например, здесь. Обратите внимание, что в классах контейнеров реализованы свои методы, аналогичные функциям представленным ниже. В этом случае применять нужно именно встроенные методы, а не обобщенные алгоритмы.

Немодифицирующие алгоритмы

В немодифицирующих алгоритмах размер массива не изменяется (или элементы не перемещаются на новые позиции).

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;
}

13      7.26493
45      9.01965
32      3.65027
31      1.76216
35      6.83121
51      1.50976
94      7.113
72      6.50572
65      5.80195
43      2.84763
42      7.77742
50      2.29542
22      8.998
84      3.40551
24      6.00061
42      6.10226
26      3.8038
94      5.6271
86      8.86742
97      9.99399
Производим сортировку по первому
элементу пары, по возрастанию
13      7.26493
22      8.998
24      6.00061
26      3.8038
31      1.76216
32      3.65027
35      6.83121
42      6.10226
42      7.77742
43      2.84763
45      9.01965
50      2.29542
51      1.50976
65      5.80195
72      6.50572
84      3.40551
86      8.86742
94      7.113
94      5.6271
97      9.99399

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 к своим операндам с левой стороны.

(2 оценок, среднее: 4,50 из 5)

Загрузка...