C++. Для начинающих несколько примеров использования обобщённых алгоритмов

Кто-то из вас уже встречался с упоминанием алгоритмов STL, кто-то ещё встретится. А что это такое? Когда кто-то говорит об алгоритмах, первое что обычно приходит на ум новичку — это те блоксхемы, которые он рисовал на уроках информатики.
  • Алгоритмы STL — это встроенные в C++ функции, помогающие работать с STL-объектами (векторами, списками, очередями, деревьями...)
Алгоритмы STL — это шаблонные функции, которые, как правило, принимают на вход начало и конец последовательности и часто может принимать фрагмент исполняемого кода (фрагментом может быть функция, лямбда-функция, функтор: всё, что работает как функция), иногда вместо фрагмента кода обычное значение. Шаблонные функции — это такие функции, которые отвязаны от конкретного типа.
Всем, кто решал задачи с массивами, известны часто встречающиеся: найти в массиве максимальный и минимальный элемент, отсортировать массив, посчитать число четных или нечетных элементов, определить, содержится ли в массиве какое-то значение и многие другие. Так вот набор функций для решения этих задач разделили на группы и назвали этот набор групп функций, встроенных в язык, алгоритмами.
  • Для подключения возможности использовать алгоритмы STL нужно задействовать директиву алгоритмов: #include <algorithm>
Преимущество использования алгоритмов в том, что они в большинстве своём настраиваемые, благодаря возможности подавать им фрагменты кода. Если вы понимаете, что такое возвращаемое значение из функции — вы легко поймёте, как оно влияет на работу алгоритмов. Но о настраиваемости чуть позже: не все алгоритмы умеют принимать фрагменты кода. Для начала выполним поиск в массиве заданного значения:

АЛГОРИТМЫ ПОИСКА

В #1.1 алгоритму задаются начало и конец последовательности (вектора v) и искомое значение (99). Алгоритм отрабатывает и возвращает результат, только он возвращает не булево значение (что может кто-то ожидать), а итератор на найденный элемент или на конец последовательности. Если не знаете, что такое итераторы, то можете их воспринимать как указатели. Это своеобразные указатели, направляемые на кконкретные элементы контейнеров. Так вот, если итератор достиг конца вектора, то, значит, искомого элемента в векторе нет, но если не достиг, то можно выявить позицию или просто сориентироваться, что коли элемент есть, то надо что-то сделать:
Чтобы определить позицию найденного элемента, нужно от полученного результата вычесть v.begin(). Можно искать с помощью функции distance, но я по инерции продолжу как сделал. Сейчас будет правильно считающий позицию существующего элемента, но немного неправильный код:
Неправильно здесь то, что этот код не учитывает, что у искомого значения может не быть позиции в векторе (что значения в векторе нет). Это можно исправить, если дважды написать алгоритм, но зачем два раза выполнять один алгоритм, если можно запомнить итератор на найденный элемент, а потом использовать этот итератор как результат алгоритма?
Вообще к итераторам придётся привыкать. Многие алгоритмы возвращают именно их. В целом, итераторы похожи на указатели, для них работает практически всё, что работает для указателей, поэтому часто итераторы и указатели приравнивают.
Алгоритм find работает не с фрагментом кода, а непосредственно со значением в третьем параметре, поэтому его нельзя использовать для поиска по условию. Для поиска по условию используют алгоритм find_if. Понятие настраиваемости алгоритмов как раз и означает, что алгоритму можно задавать условия с помощью функций, функторов и лямбда-выражений (всего, что можно использовать как функции).
Функции, возвращающие булевы значения и служащие для обозначения критериев, называют предикатными или предикатами. В #2.1 предикатную функцию можно сократить, оставив возвращаемым значением только само условие. Это удобно, поэтому так делают все:
Обходимый алгоритмом элемент последовательности, можно сказать, вшит в работу алгоритма, поэтому его не нужно указывать предикатоной функции. Если алгоритм предполагает работу с одним элементом обходимого контейнера, то предикатная функция должна принимать один элемент. Алгоритм подставит в параметр функции обходимый элемент. Проблема в #2.1 в том, что значение для сравнения жёстко вшито в предикатную функцию. Из-за этого нет возможности выбирать любое значение в любой момент времени. Ведь может быть необходимость вместо 10 подставлять другие значения. Это обходится либо с помощью функциональных адаптеров (так делали раньше), либо с помощью функторов или лямбда-функций.
Поскольку итераторы практически указатели, то разыменованием итератора часто можно получить значение, на которое итератор направлен. Иногда может быть нужно найти все элементы последовательности, удовлетворяющие условию, тогда поскольку find_if ищет только первое вхождение, нужно зацикливать поиск:
При создании циклов, подобных в #2.3 у начинающих возможны ошибки, когда последовательность обходится каждый раз с самого начала (т. е. обход уже обойдённого) и когда забывают переместиться на один элемент вперёд (из-за чего итератор зацикливается на найденной позиции). В общем, нужно отслеживать позиции, на которые нацелены итераторы и не забывать смещать точку старта для циклов. Вообще #2.3 можно оформить более красиво, если ещё и вывести на экран позиции найденных элементов:
Я для примеров использую лямбда-выражения. Это просто короче, чем если бы я приводил примеры на функторах, да и использование лямбда-выражений в таких ситуациях после принятия С++11 довольно популярное занятие. Вот, например, так может выглядеть поиск по диапазону:
Без лямбда-выражения #2.5 мог бы выглядеть так:
У алгоритмов, который не предполагают в своём третьем параметре прямых значений всё вертится вокруг исполняемого кода (функций, функторов, лямбда-выражений). Если человек умеет использовать функции, но не знает ничего про функторы или лямбда-выражения, то он немного ограничен в использовании алгоритмов, в том плане, что, если фрагменту кода надо докинуть кроме элемента обходимой последовательности что-то ещё (как в случае с поиском по диапазону), то нужно использовать такие объекты языка, которые умеют сохранять состояние (функции как раз не умеют, а функторы умеют, а лямбда-выражения умеют подхватывать данные). Иногда может быть нужно ещё использовать и функциональные адаптеры: это когда алгоритм предполагает одно число параметров, а используемый для него фрагмент кода предполагает другое число. Если будет желание проникнуться базовыми знаниями в этой области, то можете почитать:
В семейство алгоритмов поиска входит алгоритм search. В отличие от файндеров (тех, что начинаются с find), ищет он не значение, а последовательность. Им можно искать, например, подстроку в строке, либо подмассив в массиве. Чтобы его использовать, нужно прежде всего понимать, что нужно будет использовать в параметрах: начало и конец последовательности, в которой ищут, начало и конец последовательности, которую ищут, ну и условие поиска, если оно будет нужно.
Вообще у типа string есть свой собственный способ искать подстроки, а #2.3 был приведён только для общего понимания. Предпочитать следует встроенный в string поиск. Обычно search используют для обнаружения подмассивов:
Итераторы для неклассовых типов — это обычные указатели на типы хранимых в обходимых последовательностях данных. Поскольку в #3.2 массив хранит int'ы (массив [] — это неклассовый тип), то итератор должен быть указателем на int. Тут нужно только ещё уметь понимать, как определять границы последовательностей. Для массивов, что с квадратными скобками, можно либо выводить количество элементов и отталкиваться от результата, либо определять итератор с помощью функций begin или end. Поскольку у match (в #3.2) размер явно не задан, я использовал функцию для определения итератора на последний элемент. Этот трюк может не сработать, если где-то от массива останется только указатель на первый элемент. Но это не меняет сути. В любом случае следует понимать, как определять границы искомого объекта. Для векторов всё намного проще, чем для массивов, потому что у них всегда можно сориентироваться на начало и конец:
В #3.3 в качестве последовательности используется вектор (классовый тип), поэтому итератор уже не обычный указатель.
Иногда может случиться так, что для искомой последовательности и объекта, в котором она ищется, может быть не определена операция сравнения. Тогда алгоритму search будет нужно подсказывать, как производить сравнение. Такую подсказку можно сделать с помощью предикатной функции.
В #3.4 сравнивается int-значение вектора v и A-значение вектора match. Так мало того, что типы не совпадают, тут ещё и не к значению x обращение идёт. Чтобы исправить это, нужно научить алгоритм сравнивать внешние для структуры элементы с x-значениями структуры. Сделать это можно с помощью вспомогательной функции, которую задействовать как предикат:
Благодаря возможности использовать предикаты, мы смогли подсказать нуждающемуся в подсказке алгоритму, как нужно делать сравнение, после чего алгоритм с лёгкостью исполнил свою задачу.
Есть еще бинарный поиск: binary_search: он ищет значение, не последовательность. Бинарный поиск в разы быстрее find, но выполняется он, только если диапазон значений, в котором ищется элемент, отсортирован по возрастанию. Этот поиск не возвращает итератор на найденный элемент, а возвращает булево значение, нашёлся элемент или нет. Из-за этого нельзя понять позицию найденного. Чтобы использовать бинарный поиск с возможностью определения позиций, следует использовать одну из разновидностей бинарного поиска вхождения последовательности: lower_bound, upper_bound, equal_range.
Особое внимание, что перед поиском вектор сортируется по возрастанию, а результат поиска — это обычное булево значение.
Бинарный поиск в отличие от find умеет работать с предикатом. Поэтому, как и в случае с search, если будет нужно докинуть способ сравнения, организовать это можно с помощью вспомогательной функции. Только нужно иметь в виду, что если тогда использовалась операция на равенство (искались одинаковые элементы), то здесь уже используется операция сравнения, ну и что требуется подать четыре параметра: начало и конец последовательности, в которой ищем, искомое значение и только потом предикат.
lower_bound — это разновидность бинарного поиска. Помогает найти первое вхождение, не меньшее, чем заданный элемент. А upper_bound помогает найти первое вхождение, большее, чем заданный элемент:
[0, 5, 10]
lower_bound(3)
первый элемент, не меньший 3?
5
[0, 5, 10]
upper_bound(3)
первый элемент, больший 3?
5
[0, 3, 3, 3, 10]
lower_bound(3)
первый элемент, не меньший 3?
3
[0, 3, 3, 3, 10]
upper_bound(3)
первый элемент, больший 3?
10
В коде это выглядит так:
Если нужно вытащить итератор на позицию найденного элемента, то можно сделать так:
equal_range — это алгоритм поиска, который объединяет в себе работу lower_bound и upper_bound и отдаёт как результат пару итератора: один итератор — это итератор lower_bound, другой — это итератор от upper_bound. Если вы поняли пятые листинги, то и этот алгоритм поймёте.
#5.3 опирается на #5.2 b #5.1. В #5.3 получаем левую границу и правую границу. Левая граница — это первый элемент последовательности, не меньший, чем зававаемое значение в алгоритм, а правая — это первый элемент, что больше, чем задаваемый. То, что обяснялось в таблице выше. Опираясь на границы, можно получить диапазон значений, такой диапазон значений и выводится в результате работы на экран. Т. е. мы делаем обход от левого итератора к правому, а попутно вытаскиваем все значения из обходимой области данных.
Теперь отвлечёмся от алгоритмов поиска и посмотрим на популярные и не такие сложные. На алгоритм сортировки sort и алгоритмы счёта: count и count_if.
Алгоритм sort не возвращает ничего, поэтому его результаты никуда не запомнить. Он просто модифицирует последовательность так, чтоб элементы были упорядочены. Когда нет цели использовать конкретный вид сортировки, обычно выбирают из семейства алгоритмов сортировок именно этот.

АЛГОРИТМ СОРТИРОВКИ

greater<int>() и less<int>() — это функторы, встроенные в язык. На их места вы можете вставить свои предикаты. В предикатах определить условия, что должно быть больше чего
Сортировать можно массив, только для этого нужно знать, где его границы.
Из-за того, что иногда от массива остается только указатель на первый элемент, функции получения итераторов начала и конца не работают. Пример можно увидеть в #6.4.В таких ситуациях мы должны использовать арифметику указателей (что и сделано в коде).
Алгоритмы счёта могут помочь посчитать число каких-то значений в последовательности. Как и у алгоритма find, алгоритмы счёта разделяются на алгоритм простого счёта (count) и алгоритм счёта по условию (count_if. Алгоритм простого счёта не умеет работать с предикатами, а алгоритм счёта по условию умеет, поэтому, если нужно посчитать что-то, согласно какому-то условию, то нужно использовать count_if, а если просто посчитать число вхождений какого-то элемента в последовательность, то можно использовать count.

АЛГОРИТМЫ СЧЁТА

Для того, чтобы искать не одно значение, а группу значений, согласно какому-то условию, то используем count_if. Посчитаем число гласных в строке:
В #7.2 считаются русские буквы. Следует понимать, что русская 'а' и латинская 'а' — это разные коды в таблице символов. Функцию определения гласных символов можете переписать в свою, суть её должна быть сведена к тому, что возвращать она должна истинну, если ch гласная.
Есть ещё много алгоритмов, но все в этой публикации поместиться не могут. На этом я остановлюсь. Надеюсь, вы узнали много полезной информации, что-то нашли или чему-то научились.

НЕКОТОРЫЕ ОБОБЩЕННЫЕ АЛГОРИТМЫ

АЛГОРИТМЫ ПОИСКА
АЛГОРИТМЫ СОРТИРОВКИ И УПОРЯДОЧИВАНИЙ
АЛГОРИТМЫ УДАЛЕНИЯ
ЧИСЛЕННЫЕ АЛГОРИТМЫ
АЛГОРИТМЫ ГЕНЕРАЦИИ И ИЗМЕНЕНИЙ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
АЛГОРИТМЫ СРАВНЕНИЯ
find()
sort()
unique()
accumulate()
generate()
equal()
find_if()
partial_sort()
remove()
partial_sum()
fill()
min()
search()
merge()
inner_product()
transform()
max()
binary_search()
partition()
adjacent_difference()
copy()
count()
rotate()
count_if()
reverse()
random_shuffle()
Вот пример поиска максимально и минимального значений в последовательности:

АЛГОРИТМ ПОИСКА МАКСИМАЛЬНОГО И МИНИМАЛЬНОГО ЗНАЧЕНИЙ

В #8.1 в одном случае используется указатель, в другом указатель не используется. Код маленький и должен быстро уложиться в вашей голове. Предлагаю вам решить несложную задачу. Выведите на экран все индексы вектора, в которых лежит минимальный элемент. Т.е. например вектор содержит [0 1 0 0 1] —-> на экран [1 4] (отсчет индексов с нуля). Приблизительный код я приводил, нужно просто создать аналогию программы.
Статья обновлена 31.12.2021

Один комментарий на «“C++. Для начинающих несколько примеров использования обобщённых алгоритмов”»

  1. Аноним:

    В Код C++ Алгоритм max_element и Алгоритм min_element небольшая ошибка: перепутани коментарии. Правильно будет так:

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Поиск

 
     

Случайная книга в электронном формате

https://www.litres.ru/golden-krishna/horoshiy-interfeys-nevidimyy-interfeys-19057890/?lfrom=15589587
Яндекс.Метрика