Обратные итераторы

Loading...

From the course by Moscow Institute of Physics and Technology

Основы разработки на C++: жёлтый пояс

67 оценки

Moscow Institute of Physics and Technology

Основы разработки на C++: жёлтый пояс

67 оценки

Этот курс является продолжением курса "Основы разработки на C++: белый пояс". В нём преподаватели продолжают знакомить вас с возможностями языка C++. В курсе рассмотрены: - целочисленные типы языка C++ - пары и кортежи - шаблоны функций - наследование и полиморфизм - итераторы и стандартные алгоритмы - распределение кода по нескольким файлам Кроме того, в курсе рассмотрено использование юнит-тестов для отладки программ и обеспечения надёжности кода, а также продемонстрировано, как, пользуясь знаниями только "Белого" и "Жёлтого" поясов, разработать свой собственный unit test framework. Так же, как и в "Белом поясе", в конце курса вас ждёт финальный проект. В "Белом поясе" надо было самостоятельно реализовать простое хранилище данных с возможностью добавления, удаления и поиска. В "Жёлтом поясе" это хранилище надо будет усовершенствовать, добавив поддержку более сложных запросов. Курс разработан ведущими специалистами Яндекса и преподавателями Школы анализа данных. За их плечами – годы разработки сервисов поиска, рекламы и инфраструктуры. Кроме того в подготовке заданий участвовали сотрудники Яндекса и студенты Школы анализа данных: - Александр Гришин - Алексей Аверченко - Максим Филипов - Даниил Петров - Евгений Шавлюгин - Владислав Виноградов - Алексей Боголюбский - Дмитрий Кузьмичёв - Иван Качалкин - Андрей Полушин - Андрей Корнеев - Константин Меренков

From the lesson

Итераторы, алгоритмы и контейнеры

В курсе "Белый пояс по C++" мы познакомились с некоторыми стандартными алгоритмами: count, count_if и sort. Конечно же, библиотека C++ гораздо богаче и содержит значительно больше стандартных алгоритмов, которые позволяют сделать ваш код короче, понятнее и надёжнее. Чтобы их освоить, сначала нужно узнать, что такое итераторы. С этого мы и начнём четвёртую неделю. Затем рассмотрим стандартные алгоритмы, в которых используются итераторы. Наконец, мы познакомим вас с новыми стандартными контейнерами: деком и очередью.

Использование итераторов в методах контейнеров4:39

Использование итераторов в алгоритмах9:53

Обратные итераторы7:01

Алгоритмы, возвращающие набор элементов8:17

Итераторы inserter и back_inserter5:47

Отличия итераторов векторов и множеств5:26

Категории итераторов, документация4:22

Meet the Instructors

Лежанкин Иван Андреевич

Яндекс
Парамонов Евгений Анатольевич

Яндекс
Полднев Антон Вячеславович

Яндекс
Шишков Илья Иванович
кандидат технических наук
Яндекс

[БЕЗ_ЗВУКА] Мы увидели,

что итераторы универсальны в смысле контейнеров, для которых они используются.

Бывают итераторы для векторов, для ссылок, для множеств, для словарей,

и они все ведут себя одинаково.

Благодаря этому удобно писать, например, шаблонные функции, шаблонные алгоритмы.

Но оказывается, что у одного контейнера бывает несколько разных итераторов.

Бывают не только обычные итераторы begin и end, бывает еще специальные итераторы,

которые могут нам помочь легче решить задачу, которую мы решали во втором видео.

Там мы итерировались по контейнеру в обратную сторону и очень страдали,

на самом деле.

Там был странный цикл while, который было не очень легко понять.

Оказывается, можно легко и просто, например,

вывести вектор в обратном порядке.

Для этого раньше мы писали begin (langs) и end (langs), получали итераторы,

с помощью которых мы выводили этот вектор.

Давайте я еще раз продемонстрирую, что у меня всё выводится.

Чтобы проитерировать в обратном порядке, я передам немного другие итераторы.

Да, у меня всё вывелось, вот мой вектор.

А теперь я выведу в обратном порядке, вызвав не begin и end, а rbegin и rend.

r от слова reverse, обратный порядок, обратные итераторы.

Компилирую, запускаю.

Итак, у меня действительно строчки вывелись в обратном порядке.

Я использовал ту же самую функцию, тот же самый готовый написанный мной алгоритм,

чтобы вывести элемент в обратном порядке.

Интересно, что такое rbegin?

Получается, что rbegin — это начало диапазона в обратном порядке.

То есть это конец диапазона.

Давайте, я попробую вывести *rbegin (langs).

Наверное, логично увидеть там последний элемент,

то есть первый в обратном порядке.

Сейчас мы это увидим, запускаем код и видим C#.

А если я попробую вызвать звездочку от rend,

давайте я PrintRange пока уберу, то, наверное, это будет какой-то,

опять же, невалидный итератор, от которого звездочку делать нельзя.

Действительно, у меня код упал.

Давайте все-таки чуть подробнее разберемся.

Вот у меня rbegin указывает на конец, rend указывает за началом, получается.

А что делает ++ от такого итератора?

Логично предположить, что он позволяет пройтись в обратном порядке.

Соответственно, если я сохраню rbegin в какую-то переменную,

давайте я выведу сначала *it,

а теперь я сделаю ++, то это будет ++ для

обратного итератора, то есть итератор подвинется в обратную сторону.

Сейчас я это увижу, компилирую код.

Сначала я должен увидеть rbegin, то есть последний элемент,

а затем следующий за ним в обратном порядке, то есть Java.

Хорошо, давайте разбираться.

У меня итераторы были обычные, прямые итераторы begin и end.

Begin указывал на нулевые элементы, end указывал за последним.

А rbegin и rend — это то же самое, но для прохода в обратном порядке.

Соответственно, rbegin указывает на последний элемент,

а rend как бы перед первым.

Если я возьму обратный итератор на нулевой элемент и сделаю от него минус-минус,

то я попаду в rend.

Точнее, ++.

При этом мы мельком видели, какой тип у меня имели обычные итераторы.

Это контейнер : : итератор.

Например, vector<string> : : iterator.

Для обратных итераторов тип называется по-другому,

вместо iterator reverse_iterator.

Хорошо.

Давайте увидим еще какую-нибудь пользу от обратных итераторов.

Может, не только с помощью них вывести диапазон в обратном порядке,

можно еще их в алгоритмы попередавать, алгоритмы же универсальные, правда?

Вот мы в наш алгоритм попробовали передать,

а теперь попробуем в другой алгоритм передать.

Например, я снова напишу find_if.

Снова найду первый язык в диапазоне от rbegin до rend,

который начинается на букву C.

То есть лямбда-функция должна вернуть lang [0] = = 'C'.

И давайте я сразу этот итератор

посмотрю, что в нем лежит.

Итак, вызвал find_if, но нет begin и end от rbegin и rend, точно так же,

когда у него лямбда-функция.

Убираю лишнюю скобку, компилирую.

Запускаю и вижу C#.

Раньше find_if возвращал первый элемент, который удовлетворяет заданному условию,

и теперь он все еще возвращает первый элемент,

но для диапазона обратных итераторов, то есть, по сути, последний элемент.

Хорошо.

Куда еще можно подставлять обратные итераторы, чтобы в них разобраться?

Например, можно вызвать функцию sort.

Не от begin и end, как мы это делали в первом курсе, а от rbegin и rend.

Как вы думаете, что получится?

Сейчас мы это проверим.

PrintRange (begin (langs), end (langs)).

Вывожу теперь в прямом порядке свой диапазон.

Компилирую.

У меня, конечно, тут не всё очень хорошо, потому что sort не возвращает итератор.

Вот я поправился, снова компилирую.

Сейчас я увижу, как отсортировался вектор.

Он отсортировался в обратном порядке.

Сначала у меня Python, потом Java и так далее по убыванию.

Действительно, sort изначально сортирует по возрастанию,

а мы передали ему обратный диапазон.

Он отсортировал его по возрастанию, а поскольку он обратный,

то в итоге мы отсортировали по убыванию.

Очень удобно, на самом деле, не писать никакой компаратор, не передавать в sort,

а передать обратный итератор и отсортировать по убыванию.

Давайте еще какой-нибудь пример рассмотрим.

Например, reverse.

Если в reverse передать обратные итераторы, как вы думаете,

он перевернет или не перевернет, и что вообще произойдет?

Оказывается, что какая разница?

Перевернуть прямой диапазон, перевернуть обратный диапазон — это одно и то же.

Итак, что мы узнали в этом видео?

Мы узнали про обратные итераторы, которые получаются функциями rbegin и rend,

позволяют упростить итерирование по диапазону в обратную сторону,

как по вектору, так и по множеству, например.

Их можно спокойно передавать спокойно в алгоритмы, как в те, которые мы написали,

тот же PrintRange, так и в какие-то другие алгоритмы, кем-то уже написанные.

И в частности, если передать эти обратные итераторы в алгоритм sort,

вы получите сортировку по убыванию, а не по возрастанию.

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

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

© Coursera Inc., 2018 Все права защищены.

Загрузить из App Store

Загрузить в Google Play