Множества

Множество - это неупорядоченный набор элементов одного типа. В отличие от массива элементы не имеют четкого места для хранения, все что можно сказать - есть ли элемент во множестве или нет. Повторное добавление одного и того же элемента не допускается (ошибка не возникает, просто операция не выполняется).

Множества, к примеру, удобно использовать для сокращения операций сравнения. Например, в задаче "проверить, принадлежит ли символ к определенному набору" вместо большого количества сравнений можно сформировать множество и выполнять поиск по нему.

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

#include <set>

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

Пример

set<int> used_numbers; // создается множество из целых чисел с именем used_numbers

Пример

set<float> filter_data; // создается множество из действительных чисел с именем filter_data

Добавление элемента

Для добавления элемента служит функция insert().

Пример

set<int> data_set; // создается множество data_set.insert(10); // добавить число 10 for (int x = 1; x <= 5; x++) data_set.insert(x * 5); // добавить числа 5, 10, 15, 20, 25

Ввод данных напрямую во множество невозможен. Следует считывать переменные и добавлять их во множество с помощью функции insert().

Запрос количества элементов

Функция size() возвращает количество элементов.

Пример

if (data_set.size() > 0) { // какие-то команды }

Удаление элемента

Функция erase() удаляет указанный элемент.

Пример

data_set.insert(1); data_set.insert(2); // во множестве 2 элемента: 1 и 2 data_set.erase(1); // теперь во множестве 1 элемент: 2

Поиск элемента

Функция find() ищет указанное число. При успешном поиске возвращает указатель на это число, при неуспешном - специальную величину - множество::end().

Пример

if (data_set.find(10) != values.end()) { // команды, которые надо выполнить, если такой элемент есть }

Вывод множества

Для вывода множества следует организовать цикл по всем указателями на его элементы:

Пример

for (set::iterator p = data_set.begin(); p != data_set.end(); p++) cout << *p;

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

В стандарте C++ 11 возможен также такой вариант вывода элементов:

for (auto& element : some_set) { cout << element; }

Нахождение наименьшего элемента

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

int min_element = cout << *some_set.begin();

Время выполнения операций

Операции над отдельными элементами - find(), erase(), insert() выполняются за время, пропорциональное log N, где N - количество элементов множества.

Дополнительно

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

Подробное описание см. в документации по языку программирования и библиотекам.

Последнее изменение: Суббота, 15 Август 2020, 02:34