set и multiset в C++

Set и multiset в C++: что это такое и как с ними работать

Сегодня мы разберем еще два контейнера STL, которые очень похожи между собой — set и multiset.

Что такое set и multiset

set — это контейнер, который автоматически сортирует добавляемые элементы в порядке возрастания. Но при добавлении одинаковых значений, set будет хранить только один его экземпляр. По другому его еще называют множеством.

добавление элементов в SET

multiset — это контейнер, который также будет содержать элементы в отсортированном порядке при добавлении, но он хранит повторяющееся элементы, по сравнению с множеством set. Часто его называют мультимножество.

 

добавление элементов в MULTISET

Из-за того, что set построен на списках нельзя обратиться к определенному элементу по индексу, как в массиве или векторе:

Для этого придется оперировать итераторами.

Как создать set и multiset

Для использование, с самого начала нужно подключить единственную библиотеку — <set>.

Далее используем данную конструкцию:

  • [тип] — это тип данных для нашего контейнера.
  • [имя]— название нашего контейнера.

Чтобы добавить новый элемент нужно использовать функцию insert():

Добавление происходит за log n. n — это размер контейнера.

Возможно понадобиться изменить сторону сортировки в обратную (по-убыванию) для этого можно сделать с помощью greater, вот так:

  • В каждом из пунктов [тип] должен быть одинаковый.

Также можно добавлять значения при инициализации контейнеров:

Но это можно делать только в C++ 11 и выше.

Итераторы для multiset и set

Вот как выглядит создание итератора:

Чтобы итератор работал на определенный set или multiset, [тип] должен совпадать с типом контейнера.

Для использование итераторов подключение посторонних библиотек будет лишним. Итераторы уже включены в библиотеку — <iostream>. А если будут нужны, то они находятся в библиотеке — <iterator>.

При создании итератора для set и multiset нужно знать, что мы сможем только наблюдать за их значением. Это значит, что мы не сможем изменять значения существующих элементов.

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

Вот что можно делать с итератором на множество и мультимножество:

  • Использование операции разыменования — *.
  • Сравнивать итераторы на равенство (==) и неравенство (!=).
  • Увеличивать или уменьшать итератор, с помощью инкремента (++) и декремента (--).

Но также у него есть свои ограничения:

  • Нельзя изменять итератор используя операции сложения (+), умножение (*), деления (/).
  • Также нельзя сравнивать итераторы знаками больше (>) и меньше (<).

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

Также можно сравнивать итераторы на равенство (==) и неравенство (!=). Мы часто будем пользоваться данной возможностью. Например, чтобы вывести все элементы.

  • В строке 11: создали multiset — mst.
  • В строках 14 — 18: заполняем мультимножество случайными значениями.
  • В строке 20: инициализируем итератор на mst.
  • В строках 22 — 25: выводим значения mst пользователю.
  • В строке 23: мы сравнивали итераторы на неравенство (!=), чтобы не выйти за диапазон значений контейнера и в последствии чтобы этот цикл не выполнялся бесконечно.

Вот пример данной программы:

==_and_!=_in_multiset.cpp
Добавление случайных чисел:
1) 7
2) 5
3) 1
4) 5
5) 9
Отсортированный вариант: 1 5 5 7 9
Process returned 0 (0x0) execution time : 0.010 s
Press any key to continue.

Методы для set и multiset

Давайте рассмотрим функции, которые можно использовать, как с set, так и с multiset.

copy

Сначала подключите библиотеку — <iterator>, она понадобится нам для использования — ostream_iterator.

Эта функция используется для различных операций, о которых вы можете посмотреть здесь. Одна из таких операций вывод элементов контейнера. Снизу находится конструкция вызова данной функции:

  • [начала] — итератор указывающий на первый элемент, который мы хотим вывести. Так мы можем начать выводить со второго или третьего элемента.
  • [конец] — итератор указывающий на ячейку, до которой будет производиться вывод.
  • [тип] — тип данных выводимых элементов (тип контейнера).
  • <отступ> — здесь можно указать, что выводить между элементами. Обычно указывают пробел (cout, " ").

Вот пример использования copy для set:

  • В строках 14 — 18: считываем значения пользователя.
  • В строке 22: выводим все элементы контейнера st.

Вот как будет выглядеть выполненная программа:

copy_for_set.cpp
Введите 5 чисел:
1) 15
2) 19
3) 3
4) 12
5) 7
Содержимое set: 3 7 12 15 19
Process returned 0 (0x0) execution time : 0.010 s
Press any key to continue.

erase

С помощь нее вы сможете:

  1. Удалить какой-то конкретный элемент — <имя>.erase([итератор]).
  2. Удалить все элементы с данным значением — <название>.erase([ключ]). Это отличная функция для мультимножества. А для set мы как раз удалим конкретный элемент, это удобнее чем:
    • Найти итератор на определенное значение через функции find или lower_bound
    • А потом его удалить
  3. Либо удалить определенный диапазон значений.

    • [начала] — с какого элемента будет происходить удаление (включительно).
    • [конец] — до какого элемента будет продолжаться (не включительно).

Пример:

lower_bound

Часто приходится проверить есть ли элемент, который равен определенному ключу, либо больше его. Это функция находит элемент который больше или равен ключ (>= key).

  • key — это наш ключ. Значение, с которым будут сравниваться элементы.

lower_bound для set

upper_bound

Этот метод идентичен функции lower_bound:

  • У него такая же конструкция вызова
  • При поиске также используется бинарный поиск

Но искать она будет элемент, который именно больше ключа —  > key.

upper_bound для set

find

Сравнительно часто может пригодиться нахождение итератора на элемент, либо проверить существует ли он вообще.

Эта функция может возвратить:

  • Местонахождение [ключа] — итератор.
  • Значение на конец контейнера ( оно будет равняться вызову st.end()), если ячейки с таким значением не существует.

Чтобы проверить есть ли данный элемент, можно воспользоваться данным кодом:

Если условие верно, то такого элемента нет (он равен концу контейнера). Вот пример:

Выше мы проверяем, есть ли значения меньшие 31 и большие 0 в контейнере.

  • Если нет, то выводим это значение.

count

Возвращает количество элементов с заданным значением.

Для обычного set эту функцию можно использовать, чтобы проверить существует ли заданное значение. А вот для multiset данная функция может пригодиться гораздо лучше из-за возможных повторяющих значений.

equal_range

Эта функция предназначена для multiset. Допустим вы добавили несколько одинаковых чисел, и вам требуется узнать: от куда этот диапазон начинается и до куда заканчивается.

  • <имя> — название нашего мультимножества.

Возвращаемым значением этой функции будет — pair.

  • В первой ячейке будет находится значение итератора, который указывает на начала этого диапазона. Если мы вызовем lower_bound([ключ]) (ключ при этом одинаковый), то значение итераторов будут одинаковые. Найдет число >= [ключ].
  • Во второй ячейке будет находится значение итератора, если бы мы вызвали upper_bound([ключ])с тем же ключом. Найдет число > [ключ].

Вот пример использования этой функции:

Создание простого приложения

Давайте закрепим свои навыки на создании простой игры.

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

Вот какой функционал она будет иметь:

  1. Добавление новых элементов.
  2. Удаление одного или сразу всех элементов со значением value.
  3. Использование операции lower_bound для поиска папок.
  4. Оперирование операцией upper_bound для поиска папок.

Давайте начнем! Для начала хотелось бы чтобы пользователь уже имел какую-то файловую систему — так сказать «бэграунд».

  • В строке 4: мы создали наше мультимножество.
  • В строках 6 — 10: считываем начальные индексы папок.

Далее давайте реализуем каждую операцию. Начнем с добавление нового элемента.

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

Вторая операция будет удаление — это уже сложнее. Потому что у нас два вида выполнения данной функции: удаление одного элемента и удаление всех элементов с заданным ключом.

  • В строке 3: считываем вид операции.
  • В строках 5 — 15: выполняется операции с удалением одной ячейки.
  • В строках 18 — 29: выполняется операции с удалением всех значений.
  • В строках 10 и 23: реализованы условия для проверки существования данных значений в мультимножестве.
    1. В строке 10 это реализовано с помощью функции find(). Использования find() необходимо в данном случае, чтобы потом удалить значение данного итератора.
    2. В строке 23 это реализовано с помощью count(), потому что для удаление нам не понадобится на их итератор — erase([значение]).

Третья и четвертая операция похожие и просты. Вот реализация операции lower_bound:

И последняя операция upper_bound:

А вот полностью все приложение:

Вот пример выполнения данной программы:

game_on_multiset.cpp
Введите начальное количество файлов: 5
1) Введите индекс папки для добавления: 1
2) Введите индекс папки для добавления: 2
3) Введите индекс папки для добавления: 3
4) Введите индекс папки для добавления: 5
5) Введите индекс папки для добавления: 7
Укажите количество операций: 5
1) +
Введите индекс новой папки: 3
Новые значения индексов: 1 2 3 3 5 7
2) —
Укажите какой именно тип операции вам подходит: all
Введите значение: 3
Новые значения индексов: 1 2 5 7
3) >=
Введите значение для поиска: 6
7
4) —
Укажите какой именно тип операции вам подходит: 1
Введите значение: 2
Новые значения индексов: 1 5 7
5) >
Введите значение для поиска: 7
Элемента > 7 не существует!
Process returned 0 (0x0) execution time : 0.010 s
Press any key to continue.

Плюсы и минусы использования set и multiset

Плюсы:

  • Быстрая сортировка элементов.

Минусы:

  • Нельзя обратится к конкретной ячейке по индексу [].

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

Если же вам придется очень часто обращаться к произвольным ячейкам — то использовать лучше vector или массив, если это возможно.

Упражнение

Чтобы закрепить свои знания предлагаем вам создать следующую программу.

Создайте set и сделайте так чтобы пользователь смог введя определенный символ использовать отдельную операцию:

  • Добавление — при вводе push и значение нового элемента.
  • Удаление — при вводе delete и значение удаляемого элемента.

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


Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *