Множества (set) в C++
Множество (set) — это контейнер, который автоматически сортирует добавляемые элементы в порядке возрастания. Но при добавлении одинаковых значений, set будет хранить только один его экземпляр (multiset - мультимножество - может содержать дубликаты). При добавлении нового элемента в множество, он сразу становится на свое место так, чтобы не нарушать порядка сортировки.
Множества на языке C++ определены в стандартной библиотеки шаблонов STL через класс set (multiset).
В основе множеств лежат бинарные красно-черные деревья. Операции поиска, удаления и вставки имеют логарифмическую сложность.
Для использования множеств необходимо подключить библиотеку “
set”:
#include <set>
Объявление множества:
set<int> mySet; // Объявление пустого множества.
multiset<int> mySet; // Объявление пустого мультимножества.
Функции работы с множеством (set)
empty() - проверяет отсутствие элементов в контейнере
size() - Возвращает количество элементов в контейнере
clear() - Очищает контейнер
insert() - Вставляет элементы
erase() - Удаляет элементы
count() - Возвращает количество элементов, соответствующих определенному ключу
find() - Находит элемент с конкретным ключом
lower_bound() - Возвращает итератор на первый элемент не менее, чем заданное значение
upper_bound() - Возвращает итератор на первый элемент больше, чем определенное значение
Пример использования множества и мультимножества
#include <iostream>
#include <set>
using namespace std;
int main()
{
set<int> mySet1; // объявили пустое множество
multiset<int> mySet2; // объявили пустое мультимножество
// добавляем элементы в множество
mySet1.insert(1);
mySet1.insert(2);
mySet1.insert(3);
mySet1.insert(1);
// добавляем элементы в мультимножество
mySet2.insert(1);
mySet2.insert(2);
mySet2.insert(3);
mySet2.insert(1);
set<int>::iterator it; //создание итератора
for(it = mySet1.begin(); it != mySet1.end(); it++) { // Вывод всех элементов
cout << (*it) << " "; // множества
}
cout << endl;
for(it = mySet2.begin(); it != mySet2.end(); it++) { // Вывод всех элементов
cout << (*it) << " "; // мультимножества
}
return 0;
}