[БЕЗ_ЗВУКА] Рассмотрим
специальный класс методов контейнеров и алгоритмов.
Алгоритмы поиска.
Мы уже на самом деле сталкивались с алгоритмами поиска, а именно,
мы знали что у множества есть методы count и find,
которые подсчитывают количество элементов и находят конкретный элемент.
Также есть алгоритмы count и find, которые позволяют, опять же,
посчитать количество элементов или найти конкретный элемент.
Мы могли на самом деле даже вызвать алгоритмы count и find для множества,
но у них есть одноименные методы, и это знак, что для множеств нужно использовать
соответствующие методы, они работают гораздо эффективнее,
потому что во множестве можно быстро искать, не то, что векторы.
Давайте глобально рассмотрим такую задачу, как поиск элементов в разных контейнерах.
Начнем с того, что определимся, где мы будем искать.
Мы научимся искать в не отсортированном векторе,
точнее вспомним, как мы в нем можем искать; в отсортированном векторе; а также
во множествах и словарях, для которых все аналогично.
Итак, что мы хотим научиться делать?
Мы, во-первых, хотим научиться
проверять существование конкретного элемента в нашем контейнере.
Во-вторых, хотим научиться находить конкретный элемент и понимать,
есть он или нет.
В-третьих, такой интересный момент — хотим научиться находить
первый элемент в контейнере, который больше либо равен данному,
а также находить первый элемент в контейнере, который больше данного.
Кроме того,
мы хотим научиться подсчитывать количество элементов и перебирать все элементы,
которые удовлетворяют данному условию или равны данному элементу.
Наверное, больше всего вас смущают пункты в середине про нахождение первого
элемента, который больше либо равен данному.
Звучит довольно искусственно,
однако можно вспомнить первый курс и задачу про имена и фамилии.
Мы там должны были хранить некоторую историю изменения фамилий.
Мы хранили записи в словаре год и фамилия, которая
изменилась в этот год, и нам нужно было по запросу про конкретный год отвечать,
находить последнюю запись в истории к этому моменту.
И мы должны были найти, получается, максимальный ключ в словаре,
который меньше данного, меньше либо равен.
Эта задача очень похожа на ту, которую мы научимся сейчас решать.
Эффективнее, чем мы решали ее в первом курсе.
Итак, начнем с не отсортированного вектора, для которого всё понятно.
Чтобы найти конкретный элемент в векторе, используйте алгоритм find.
Если вы хотите найти элемент по какому-то условию в векторе, например,
по условию первый элемент, который меньше либо равен данному, или больше либо равен,
используйте find_if.
Если вы хотите подсчитать количество элементов в векторе,
используйте алгоритм count, а если вы хотите перебрать все элементы,
равные данному или удовлетворяющие данному условию,
просто используется цикл, а в нем find или find_if.
Давайте рассмотрим пример такого цикла.
Например, выведем позиции всех пробелов строки s.
У нас есть такая строка s, хотим вывести позиции всех пробелов.
Как мы это сделаем?
Мы проитерируемся, начиная с чего?
Начиная с первого пробела, который мы сразу найдем алгоритмом find.
find(begin) до end пробел.
Нашли этот пробел, закончим, когда итератор станет указывать на конец,
а переход в цикле for будет к следующему пробелу,
find(next) до конца вектора, найти пробел.
Вот такой цикл for отлично решает нашу задачу.
Заметьте, что мы вместо x + 1 использовали next, просто потому,
что это чуть более универсальный способ записать x + 1.
Продолжим, рассмотрим отсортированный вектор.
Оказывается, в нем можно искать быстрее с помощью, так называемого, двоичного,
или бинарного, как его еще называют, поиска.
Почему в отсортированном векторе можно искать быстрее?
Давайте рассмотрим пример.
Рассмотрим набор чисел, какие-то целые числа от 0 до 9, некоторые повторяются,
некоторые нет.
И хотим найти в этом векторе число 4.
Как это можно делать?
Представьте, что вы пишете код уже.
Давайте возьмем средний элемент в векторе, например, шестерку и посмотрим на нее.
Шестерка явно больше четверки, а вектор отсортирован, поэтому четверка не
может быть справа от шестерки, она может быть только слева от нее, поэтому мы сразу
можем ограничить нашу область рассмотрения только левой половиной вектора.
Область рассмотрения уменьшилась сразу в два раза.
Еще раз, берем середину, в середине тройка.
Тройка меньше четверки, поэтому четверку надо искать справа.
Опять в два раза уменьшился наш диапазон.
Опять же, берем середину, опять в два раза уменьшаем,
и еще через один шаг мы находим нашу четверку.
Мы увидели, что наш диапазон текущий, который мы рассматриваем,
каждый раз уменьшался в два раза.
И, получается, на массиве 16 элементов мы потратили всего, по сути,
четыре шага, чтобы найти наш элемент.
И в целом, раз мы каждый раз уменьшаем размер вдвое,
то мы проделываем ровно столько операций, какова степень двойки нашего массива, то
есть в какую степень надо возвести двойку, чтобы получить размер нашего диапазона.
Это называется двоичным логарифмом в математике.
То есть поиск в отсортированном векторе работает за логарифмом от
размера диапазона.
Кстати говоря, столько же работает и поиск во множестве из словаря.
Из этого, кстати, следует, что,
если вы просто хотите быстро искать по набору элементов, но не хотите добавлять
новые или удалять какие-то, вам достаточно отсортированного вектора.
Это будет оптимальнее, чем, если вы используете множество.
Хотя, если хотите, можете использовать множество.
Хорошо.
Мы увидели, что можно искать быстро по отсортированному вектору.
Какие же есть алгоритмы для этого?
Во-первых, есть алгоритм binary_search, который принимает диапазон,
в котором надо искать, и сам элемент, который надо найти.
Он возвращает bool true, если элемент есть, или false, если элемента нет.
Кроме того, есть алгоритмы lower_bound и upper_bound,
которые находят первый элемент, который больше либо равен данному, lower_bound,
или первый элемент, который больше данного, это upper_bound.
А еще есть алгоритм equal_range, который по аналогии с
minmax_element возвращает пару из lower_bound и upper_bound.
Просто, если вы хотите сразу найти и lower_bound, и upper_bound,
есть для этого готовый алгоритм equal_range.
Хорошо, казалось бы, мы определили явно,
что lower_bound — это то-то, то-то и то-то.
upper_bound тоже определили, но это тяжело запомнить на практике.
Как же запомнить, что такое lower_bound и upper_bound?
Посмотрим на примерах, на разных примерах.
В первом примере у меня есть отсортированный вектор,
в котором есть три четверки.
lower_bound указывает на первый элемент, который больше либо равен данному,
то есть на первую четверку, upper_bound указывает на шестерку, как первый элемент,
который больше четверки.
Получается, что диапазон от lower_bound и upper_bound — это как раз все четверки.
То же самое мы видим на втором примере, когда у нас четверки в начале вектора.
То же самое видим на третьем примере, когда четверки в конце вектора,
в этом случае upper_bound указывает на end.
А если у меня четверок в векторе нет, то lower_bound и upper_bound
будут указывать на один и тот же элемент, первый элемент, который больше данного.
Они будут равны, чтобы сигнализировать о том, что четверок в этом векторе нет.
Итак, если элемент в векторе есть,
то equal_range — это как раз диапазон с элементами, равными данному,
от lower_bound включительно до upper_bound не включительно.
А если элемента в векторе нет,
то lower_bound и upper_bound не всегда будут равны end.
Они будут равны друг другу и указывать на ту позицию,
в которую надо вставить этот элемент, чтобы не нарушить порядок сортировки.
Вот так достаточно запомнить, что такое lower_bound и upper_bound.
Они образуют диапазон элементов, которые равны данному,
или указывают на позицию для вставки этого элемента.
Как с помощью equal_range найти количество вхождений?
Поскольку он задает диапазон, достаточно из second вычесть first,
то есть из upper_bound вычесть lower_bound.
А как перебрать все элементы, равные данному?
Достаточно проитерироваться от lower_bound до upper_bound.
От equal_range.first до equal_range.second,
как обычно мы итерируемся по диапазону.
Хорошо, если мы вспомним про множества,
то в них тоже мы на самом деле практически умеем всё искать.
Мы знаем метод count, который можно использовать как для проверки того,
есть ли элемент в контейнере, потому что вернется 0 или 1,
так и для подсчета количества элементов,
потому что во множестве каждый элемент встречается не более одного раза.
Кроме того, мы знаем метод find, который находит конкретный элемент,
а также во множестве есть методы lower_bound, upper_bound и equal_range,
о значении которых мы вполне себе уже догадываемся.
equal_range для множества на самом деле не бесполезен,
потому что он позволяет не только найти lower_bound или upper_bound,
а они, конечно, различаются не сильно во множестве, но и заодно,
сравнив их, сравнив их equal_range first и second, можно легко понять,
есть ли элемент во множестве, иначе вам пришлось бы разминовывать lower_bound,
обрабатывать случай, когда он end или не end, equal_range все равно помогает,
даже во множестве, несмотря на то, что там элемент встречается не более одного раза.
Итак, в этом видео мы узнали, что можно быстро искать по отсортированному вектору.
Так же быстро, как и по множеству.
Узнали, как именно искать, установили алгоритм binary_search и алгоритмы
lower_bound и upper_bound и equal_range, которые есть в виде алгоритмов для
отсортированного вектора, так и они есть для множества в виде методов.
Заодно мы вспоминали тот принцип, который был в начале этого видео, что если у
контейнера есть какой-то метод, у которого такое же название, как у какого-то
алгоритма, нужно использовать именно метод, потому что он будет эффективнее.
Так и для множества использовать именно методы lower_bound и
upper_bound и equal_range.
