Продвинутое итерирование по контейнерам

Loading...

From the course by Moscow Institute of Physics and Technology

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

70 оценки

Moscow Institute of Physics and Technology

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

70 оценки

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

From the lesson

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

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

Введение в итераторы10:59

Концепция полуинтервалов итераторов11:43

Итераторы множеств и словарей5:18

Продвинутое итерирование по контейнерам5:28

Meet the Instructors

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

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

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

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

[БЕЗ_ЗВУКА] Продемонстрируем,

что итераторы универсальнее чем range-based for,

что их можно использовать в гораздо более широком числе случаев.

Как я это продемонстрирую?

Давайте я вернусь к множеству языков,

словарь пока уберу.

[ЗВУК] И снова

сделаю множество строк

[ЗВУК] с языками.

Снова Python, C++,

C, Java и C#.

Давайте я выведу с помощью итераторов это множество.

Наверное, даже проще будет с вектором.

Этот вектор выведу в обратном порядке.

Как это можно сделать с помощью итераторов?

Логично было бы ожидать, на самом деле, что если у меня...

Я подключу сейчас модуль vector.

Логично было бы ожидать, что если у меня у итераторов есть ++, который двигает их на

следующий элемент, то есть и −−, который двигает на предыдущий.

Давайте попробуем.

Наверное, цикл for нам тут уже не поможет.

Я изначально...

Мне нужно начать с конца итерироваться, поэтому я начну с end от langs,

и теперь у меня будет некий цикл while, условия которого я пока не придумал.

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

И теперь давайте думать.

Мы хотим как-то двигать этот итератор в обратную сторону, делать от него −−.

Если я сделаю −−it вот здесь, то у меня цикл начнется с того,

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

Так делать нельзя, поэтому наверное, надо делать −−it,

декрементировать итератор в начале.

Тогда условие, наверное, должно быть таким: как только у меня итератор стал

равен begin от langs, я уже не могу делать от него −−, поэтому должен закончить.

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

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

Все работает.

Давайте подробнее разберемся, как это все происходит.

Итак, изначально итератор указывает на конец вектора, точнее, даже за концом.

Я проверяю, что он не begin, поэтому могу зайти внутрь цикла, подвинуть

его теперь уже на последний элемент вектора и вывести этот последний элемент.

Затем опять же проверяю, что у меня все еще не begin,

двигаю обратно влево, вывожу, двигаю, вывожу.

Подвинул на begin, опять же вывел, пока все хорошо.

Затем я вижу, что у меня итератор указывает на begin,

равен begin, поэтому я уже не могу сделать −−.

Цикл while завершается, все.

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

А такой вопрос: вот смотрите, мы внутри цикла делали −− итератор.

И у нас условие уже было, этот самый итератор.

Зная постфиксные операторы, инкременты и декременты,

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

То есть написать там while (it−− != begin(langs)) Какая будет разница между

изначальным циклом, который мы написали, и циклом с этим декрементом в условии?

Оказывается, разница лишь в одном.

Вы, когда итератор уже стал указывать на begin, вы, конечно,

из цикла выйдете, но все-таки сделаете к нему −−.

Вот этого делать нельзя, это опасно.

Перед begin нет никаких итераторов.

Компилятор имеет право, если вы от begin сделали −−, сделать все, что угодно.

Это очень опасно, делать так не надо.

Итак, какие у нас есть опасные операции над итераторами.

Это, во-первых, *end, мы видели, что у нас программа падает в этом случае.

И операции, при которых программа может упасть,

а может и не упасть: это увеличение end — за end нет вообще ничего,

и уменьшение begin — перед begin тоже ничего нет.

У внимательных слушателей мог возникнуть вопрос: чем отличаются

итераторы от ссылок?

Казалось бы, и те, и другие указывают на элементы.

И ссылки, когда мы передавали в функцию, у нас элементы не копировались,

и итераторы тоже можно было дешево передавать в функции.

В чем же разница?

А разницу, на самом деле, мы уже прочувствовали.

Во-первых, итераторы могут указывать на end, то есть как бы в никуда.

С помощью итераторов можно сказать, что элемента там нет,

а ссылка всегда указывает на конкретный элемент.

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

И во-вторых, когда мы ссылку к чему-то привязали,

она не может переместиться уже на какой-то другой элемент.

А итераторы, к ним можно делать ++.

Вот как мы видим на примере на слайде, если вы к итератору сделаете ++,

он подвинется на следующий элемент.

А если вы к ссылке сделаете ++, то если это число, то оно само увеличится на 1,

ссылка никуда не подвинется.

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

Мы узнали, что итераторы есть у всех контейнеров,

которые мы знаем: у векторов, у строк, у множеств, у словарей.

И итераторы предоставляют универсальный интерфейс,

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

Но правда, если вы можете использовать range-based for, используйте его, потому

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

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

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

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

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

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

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