[БЕЗ_ЗВУКА] Продолжим
рассматривать различные алгоритмы, которые работают с итераторами.
Мы рассматривали алгоритм 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, которые позволяют работать со множествами.
Лежанкин Иван Андреевич
Парамонов Евгений Анатольевич
Полднев Антон Вячеславович
Шишков Илья Ивановичкандидат технических наук
