[БЕЗ_ЗВУКА] Здравствуйте! На прошлом занятии мы узнали, как устроен контейнер map внутри. Сейчас мы рассмотрим, как работают итераторы в нём. Для начала установим итератор на begin. Мы знаем, что когда мы итерируемся по целому контейнеру map, мы получаем отсортированные по возрастанию элементы. Поэтому логично предположить, что begin указывает на минимальный элемент, то есть на самый левый узел. При инкременте итератора, то есть при вызове оператора (++), происходит понятная вещь: мы переходим на следующий по возрастанию элемент, производя обход дерева, и так далее. Каждый вызов оператора (++) будет нас продвигать все к большим и большим значениям. И мы будем постепенно обходить дерево дальше и дальше. Иногда при очередном инкременте итератору предстоит проделать более длинный путь и перескочить сразу через несколько уровней, как на указанном примере. Аналогично происходит и декремент итератора, то есть вызов оператора (−−), только в обратном порядке, то есть мы будем двигаться в сторону уменьшения элементов. Вы можете задаться вопросом: а не являются ли тогда вызовы операторов (++) и (−−) тяжелыми? Ведь некоторые очередные сдвиги итераторов выглядят очень сложными, потому что требуется перескочить очень много уровней. Давайте рассмотрим этот момент подробнее. Представим, что нам надо обойти все дерево, то есть проитерироваться от begin до end. Всего в дереве у нас N элементов, поэтому будет N-1 ребро, так как каждый элемент (кроме корня) имеет ровно входящее в него ребро, и каждое ребро мы проходим дважды - по направлению туда и обратно. То есть всего для обхода всех N элементов мы сделаем порядка N проходов рёбер. Получается, что в среднем на переход от элемента к элементу мы совершаем какую-то константную работу. Поэтому в среднем вызовы операторов (++) и (−−) стоят недорого, несмотря на то, что лишь некоторые из них тяжёлые. Вы можете спросить, а зачем же мы все это разбирали? Неужели только за тем, чтобы сказать, что инкремент работает за константное время в среднем? Но не только. Оказывается, что это знание может пригодиться в весьма неожиданном месте, а именно, при выборе одного из двух похожих вызовов поиска: через глобальный алгоритм либо через встроенный метод. Давайте сейчас мы с вами напишем код и посмотрим, к какой разнице это приводит. У нас есть код, вы его можете помнить по задаче о Шерлоке Холмсе. У нас есть какое-то произведение о нём, оно лежит в файле, мы считываем из него все строки и складываем в set. Такой код у нас уже был написан, давайте запустим его ещё раз и вспомним, что он работает. Да, действительно он работает, как ожидается. Вот у нас первые пять слов из этого текста, они отсортированы в лексикографическом порядке. Всё честно. Что мы хотим сделать? Мы хотим вызвать методы поиска в lower_bound двумя способами. Сначала вызвать метод lower_bound у set, а затем глобальный алгоритм lower_bound. Вызываем их с одними и теми же входными данными, то есть пробегаемся по всем буквам от A до Z и ищем слова на эти буквы. Тесты одинаковые, но посмотрим, с какой скоростью они работают. Что мы видим? Что хоть они и работают одинаково, но время требуют очень разное. Метод lower_bound выполняется почти мгновенно, а глобальный алгоритм lower_bound работает сильно дольше, вполне ощутимое время. Мы можем сделать вывод: а может, это у нас глобальный lower_bound такой плохой, может быть, он всегда так работал? Но нет, вы же помните из предыдущих курсов, что на отсортированном векторе он работает очень даже хорошо. И давайте это проверим сейчас. Возьмем вектор строк, скопируем в него строки из нашего set, он у нас уже сразу будет отсортированный, потому что в set слова отсортированы. Вызовем на этом векторе точно такой же тест и посмотрим, за какое время выполнится он. Запускаем. Что мы видим? Слова вектора лежат те же самые, и работает он очень быстро. Он работает так же быстро, как вызов метода set. То есть намного быстрее, чем этот же алгоритм на контейнере set. И нам сейчас нужно разобраться, почему у нас такая большая разница во времени. Вернемся к нашим слайдам. lower_bound в отсортированном векторе использует двоичный поиск, производя арифметические операции над итераторами. Это возможно, потому что итераторы в векторах являются итераторами произвольного доступа. Если вы не знаете или не помните что это такое - посмотрите наши лекции. Двоичный поиск и итераторы рассматривались в «Жёлтом поясе». Заметим, что глобальный алгоритм lower_bound принимает на вход только пару итераторов и ничего не знает об устройстве контейнера. Поэтому становится важно, насколько мощны эти итераторы, могут ли они позволить, например, обращаться к произвольному элементу между ними. В случае map вряд ли, это видно из структуры дерева. Представьте, что у нас есть два итератора — на begin и на end, и мы хотим найти элемент ровно между ними посередине. Это довольно трудно сделать, потому что непонятно, где он находится. Посередине как бы находится корень, но это совсем не та середина, это не значит, что элемент строго между begin и end. И давайте сейчас ещё раз посмотрим на наш код, посмотрим, что у нас итераторы в set действительно не такие крутые. Заведём итератор в нашем контейнере, возьмём, скажем, begin, пока у нас всё хорошо. Но если мы прибавим к нему любое произвольное число, мы просто увидим, что этот код не компилируется. Нам компилятор подсказывает, что оператор + не может быть применен к такому итератору. Мы поняли, что итераторы в map не позволяют производить над собой арифметические операции. Они умеют делать только инкремент и декремент. Такие итераторы называются двунаправленными. Поэтому для map глобальный алгоритм lower_bound применяет линейный поиск по порядку. В подтверждение наших слов мы можем открыть документацию для глобального алгоритма lower_bound и убедиться, что он гарантирует логарифмическую сложность только для итераторов произвольного доступа. В противном случае сложность будет линейной. Заметим, что встроенный метод lower_bound, в отличие от глобального, алгоритма знает о внутреннем устройстве контейнера map, и это позволяет ему работать за логарифмическое время. И если вы внимательно посмотрите на рисунок, вы можете провести аналогию между таким поиском и двоичным поиском отсортированного вектора. Итак, на этом занятии мы рассмотрели, как работают итераторы в контейнерах map, как происходит их инкремент и декремент. Каждая такая операция стоит константу в среднем. Мы разобрали, что итераторы в map двунаправленные, разобрали что это значит, и также можем сделать вывод, что нам нужно пользоваться встроенными методами для поиска, такими как find, lower_bound и upper_bound.
