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

Loading...

From the course by Moscow Institute of Physics and Technology

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

80 ratings

Moscow Institute of Physics and Technology

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

80 ratings

Этот курс является продолжением курса "Основы разработки на 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

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

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

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

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

[БЕЗ_ЗВУКА] Итак,

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

Во-первых, мы видели итераторы множества, в которые записывать ничего нельзя,

там remove_if мы не могли вызвать.

Во-вторых, сейчас мы увидели итераторы inserter и back_inserter, из которых

нельзя читать, у вас не получится из них ничего прочитать, потому что они только

push_back умеют делать и больше ничего, они не ссылаются на конкретные элементы.

Итераторы, более того, зависят от того контейнера, на который они ссылаются.

Давайте мы это увидим на примере вектора и множества, все-таки вектор и множество

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

кроме того, что мы в них не можем записывать.

Например, давайте код множества уберем и рассмотрим такую задачу.

Найти в моем векторе строк, векторе названия языков, язык,

который начинается с буквы C, и найти позицию этого элемента.

Мы умеем находить итератор с помощью find_if, find_if (begin (langs),

end (langs)) и лямбда-функция.

И find_if возвращал итератор на этот элемент.

Как нам найти по итератору позицию?

Логично было бы предположить, что это можно сделать,

потому что итератор указывает как раз на конкретную позицию контейнера.

Оказывается, для этого достаточно из итератора,

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

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

Запущу, увижу 1.

Действительно, у строки C++ в векторе позиция № 1.

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

Такое не пройдет с итераторами множества.

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

Пустое множество целых чисел И попробую из end вычесть begin.

Что произойдет?

Вот у меня ничего не скомпилировалось.

В частности, у меня проблема в этом выражении end − begin.

В частности, если тут пролистать сообщение об ошибке, то видно будет,

что компилятор не смог найти оператор «минус» для этих итераторов.

Помните, что вы когда определяли свои типы данных, например, рациональные числа,

вы там переопределяли оператор «плюс», оператор «минус» могли переопределить.

То же самое для итераторов.

Для итераторов множеств оператор «минус» не переопределен,

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

Векторы элемента хранятся подряд, и вы легко можете просто вычесть один

итератор из другого и понять, какое между ними расстояние.

У множества итераторы указывают на какую-то структуру данных,

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

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

на равно / не равно, но и на меньше / больше.

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

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

Но иногда возникает соблазн использовать одно конкретное запрещенное выражение

для итераторов множества.

Какое именно, о каком идет речь?

Смотрите, я взял множество целых чисел, 1, 6, 8, 9,

нашел в этом множестве auto it = s.

find (6).

Нашел конкретную 6 и хочу вывести все элементы, больше этого.

Как мне это сделать?

Если я выведу диапазон от it до end, то это будут все элементы,

больше либо равные этому.

Как мне этот элемент исключить из рассмотрения?

Я мог бы сделать ++it и потом вывести

PrintRange (it, end (s)).

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

Хотя нет...

У меня переменная it уже занята, давайте будет it2.

Выведу всё от it2 до end(s).

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

Вижу, что у меня 8 и 9.

Действительно, вот все элементы, больше 6.

Но часто такое в коде случается,

что нельзя просто эту переменную взять и изменить, то есть переменную it2.

Может быть, она константная, этот итератор константный и нельзя его менять.

Может быть, просто неудобно в данном месте его менять.

Очень хочется ++it2 не писать, а написать вот здесь it2 + 1.

Но такой код не скомпилируется,

даже 1 прибавить нельзя, видите, сколько у нас ошибок.

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

Видите, оператор «плюс» у нас отсутствует.

Поэтому есть специальная функция next,

которая помогает вам сделать из + 1 с помощью ++, не меняя саму переменную it2.

По сути, это аналог it2 + 1 для множества.

Проверяем, да, действительно работает.

И у функции next есть аналог — функция prev, которая за вас делает минус-минус,

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

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play