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

Loading...

Из курса от партнера Moscow Institute of Physics and Technology

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

138 оценок

Moscow Institute of Physics and Technology

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

138 оценок

Курс 2 из 5 — Specialization Искусство разработки на современном C++

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

Из урока

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

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

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

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

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

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

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

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

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

Познакомьтесь с преподавателями

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

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

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

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

[БЕЗ_ЗВУКА] Продолжим

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

Мы рассматривали алгоритм remove_if, например, который позволяет удалить

элемент по какому-то критерию в массиве, в диапазоне элементов в векторе, например.

А что, если мы хотим эти элементы не удалить, а аккуратно отложить,

например, в конец вектора?

Для этого есть алгоритм partition.

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

и передаю критерий, по которому я хочу разбить.

Опять же, в виде λ-функции.

Скажем, давайте я перемещу все языки,

которые начинаются с буквы C, в начало своего вектора.

Соответственно, λ-функции я верну, опять же,

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

Я вызову partition.

И могу теперь распечатать свой вектор.

И увидеть, как он теперь выглядит.

[БЕЗ_ЗВУКА] У меня сначала идут все языки, которые начинаются с буквы

C в каком-то порядке, как получилось: C#, C++ и C, а потом все остальные языки.

То есть все элементы, которые удовлетворяют критерию,

для которых λ-функция возвращает true, перемещаются в начало диапазона.

При этом partition возвращает как раз то место, где заканчивается тот самый

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

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

только те элементы, которые удовлетворяют моему критерию, а те,

которые не удовлетворяют, я пока просто отложил в сторонку, в конец вектора,

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

Хорошо, а что, если я хочу элементы из вектора по какому-то

условию тоже отложить, но не в этот вектор, а в какой-то другой?

Такая задача часто встречается.

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

Что мне делать?

Я могу вызвать алгоритм copy_if.

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

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

Я должен создать заранее вектор, в который я хочу скопировать (естественно,

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

Назову его target или нет, наверное, c_langs его назову,

я же языки на букву C копирую, и этому вектору сразу задам нужный размер.

Задам с запасом — (langs.size()); того же размера, что и тот вектор.

И ничем его не заполняю.

И в copy_if третьим аргументом передаю, куда мне нужно сохранять

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

Вот так.

И распечатываю диапазон.

Распечатаю мой новый вектор.

Наверное, я ожидаю, что там будут только языки на букву C.

Скомпилирую.

Запущу.

Увижу, что в новом векторе языки на букву C.

Тут, правда, есть некоторый подвох.

Давайте распечатаем элементы через запятую.

Поправим нашу функцию PrintRange, чтобы увидеть,

что на самом деле,

наш новый вектор, который имел изначально размер 5, все еще имеет размер 5.

Вот видите, у нас тут пять запятых.

У нас там в конце остались две пустые строки.

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

В данном случае это тоже так.

Мы просто записали C++, C и C#.

А то, что вектор изначально имел какой-то больший размер, это проблема того,

кто вызывал copy_if.

Однако copy_if, опять же, помогает нам и возвращает итератор на новый конец

того вектора, который я в него подставлял.

Можно распечатать, например,

этот новый вектор, от begin(c_langs) до итератора.

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

И теперь у меня только языки на букву C.

Прекрасно!

Теперь у меня есть, получается, алгоритм,

который возвращает ни boolean, как or off, ни число, как count,

ни итератор, как find, а по сути, он возвращает какой-то набор элементов.

В данном случае, набор элементов, который удовлетворяет какому-то условию.

Наверное, есть много таких разных алгоритмов.

Давайте вспомним наш разговор про множества.

Когда мы говорили про множества в самом-самом начале, мы говорили,

что множества — это какой-то аналог математической абстракции,

математического понятия множества.

А что в математике делают со множествами?

Например, их объединяют, пересекают.

Давайте рассмотрим алгоритм, который поможет, например,

нам пересечь два множества.

Рассмотрим два множества чисел для простоты: множество a из чисел 1, 8, 3.

И множество b из чисел, например, 3, 6 и 8.

Есть алгоритм, называется set_intersection,

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

второе множество в виде диапазона

элементов и

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

Опять же, мне нужно подготовить какой-то контейнер,

в который сохранялся бы результат.

Я сделаю его вектором.

И опять же, заранее мне нужен какой-то размер.

Наверное, пересечение двух множеств не будет превышать по размеру

первое множество.

Поэтому я здесь возьму вектор размера a.size.

И в begin(v) я сохраню все, что у меня получилось.

Сразу выведу свой вектор v

от begin(v) до end(v).

Давайте посмотрим, что же получилось.

Скомпилируем.

Запустим.

И если не

обращать внимание на наш старый вывод, у нас здесь элементы 3, 8 и 0.

То есть ожидаемые 3 и 8 и тот самый лишний элемент,

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

Если я выведу, если я получу итератор из set_intersection,

он как раз возвращает конец нового диапазона,

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

вызвать erase от вектора и удалить из него все лишнее.

Сейчас мы увидим только 3 и 8.

[БЕЗ_ЗВУКА] Если только переименуем переменную так,

чтобы она не конфликтовала по названию с предыдущей переменной it.

Компилируем.

Запускаем.

[БЕЗ_ЗВУКА} И видим только 3 и 8.

Прекрасно, мы увидели алгоритм set_intersection, который

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

Единственное, конечно, вы, наверное, могли заметить, что не очень удобно то,

что мы должны приготовить какой-то вектор, заранее оценить,

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

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

Посмотрю, что у меня получится.

Я должен создать вектор, заранее оценить его размер,

потом передать его в этот алгоритм, а затем как-то его поправить.

Сделать для него erase или ограничить каким-то конкретным диапазоном.

Видите, я создал пустой вектор, и у меня все упало.

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

который возвращает набор элементов на примере простейшего copy_if, который,

в принципе, можно было и циклом for заменить.

И на примере алгоритма set_intersection, у которого есть и аналоги, на самом деле,

например, set_union, set_difference, которые позволяют работать со множествами.

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

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

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

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

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

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