Множества

Множество (set) представляет такой контейнер, который может хранить только уникальные значения. Как правило, множества применяются для создания коллекций, которые не должны иметь дубликатов.

Множества представлены типом std::set<>, который определен в заголовочном файле <set>. Создание пустого множества:

#include <iostream>
#include <set>

int main()
{
    std::set<int> numbers;   // пустое множество чисел int
}

Поскольку тип std::set представляет шаблон, то в угловых скобках после названия типа указывается тип элементов, которые будет хранить множество. В данном случае множество будет хранить числа типа int.

Также можно инициализировать множество с помощью другого множества или списка инициализации:

std::set<int> numbers {1, 2, 3, 4, 5};

Размер множества

Функция size() возвращает количество элементов множества. Кроме того, с помощью функции empty() можно проверить, пустое ли множество (возвращает true, если множество пусто):

#include <iostream>
#include <set>

int main()
{
    std::set<int> numbers{1, 2, 3};

    std::cout << "Empty: " << std::boolalpha <<  numbers.empty() << std::endl;    // Empty: false
    std::cout << "Size: " << numbers.size() << std::endl;     // Size: 3
}

Перебор множества

Для перебора множества можно применять циклы for. Например, в стиле for-each:

#include <iostream>
#include <set>

int main()
{
    std::set<int> numbers{1, 2, 3, 4, 5};

    for (int n : numbers)
        std::cout << n << "\t";
    std::cout << std::endl;
}

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

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

#include <iostream>
#include <set>

int main()
{
    std::set<int> numbers{3, 4, 5};

    numbers.insert(1);
    numbers.insert(2);
    numbers.insert(2);
    numbers.insert(2);
    numbers.insert(6);

    for (int n : numbers)
        std::cout << n << "\t";
    std::cout << std::endl;
}

И поскольку множество может хранить только уникальные значения, мы не можем добавить одно и то же значения несколько раз. Поэтому несколько вызовов numbers.insert(2) никак не скажутся на соджержимом множества - число 2 будет добавлено только один раз.

Другой момент, который стоит учитывать, что множество упорядочивает элементы. По умолчанию элементы располагаются по возрастанию. То есть при выводе содержимого множества мы получим следующий консольный вывод:

1       2       3       4       5       6

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

Для удаления из множества применяется функция erase(), в которую передается удаляемый элемент:

#include <iostream>
#include <set>


int main()
{
    std::set<int> numbers{2, 3, 4, 5};

    numbers.erase(1);
    numbers.erase(2);
    numbers.erase(3);

    for (int n : numbers)
        std::cout << n << "\t";
    std::cout << std::endl;
}

Удаление отсутствующего элемента (как в случае вызова numbers.erase(1)) никак не сказывается. Консольный вывод:

4 5

Проверка наличия элемента

Функция count() позволяет проверить, есть ли определенное значение во множестве. Если определенное значение имеется во множестве, то функция возвращает 1, если нет - то 0:

#include <iostream>
#include <set>


int main()
{
    std::set<int> numbers{2, 3, 4, 5};

    std::cout << "10 is in set: " << numbers.count(10) << std::endl;    // 10 is in set: 0
    std::cout << "2 is in set: " << numbers.count(2) << std::endl;      // 2 is in set: 1
}

Начиная со стандарта C++20 также для проверки наличия элемента можно применять функцию constains(), которая возвращает true, если элемент есть, и false, если элемент отсутствует:

#include <iostream>
#include <set>


int main()
{
    std::set<int> numbers{2, 3, 4, 5};

    std::cout << "10 is in set: " << std::boolalpha << numbers.contains(10) << std::endl;    // 10 is in set: false
    std::cout << "2 is in set: " << std::boolalpha << numbers.contains(2) << std::endl;      // 2 is in set: true
}

Неупорядоченное множество unordered_set

Выше был рассмотрен объект std::set<>, который представляет упорядоченное множество и который упорядочивает все свои элементы по определенному критерию (по умолчанию - по возрастанию). Но также в стандартной библиотеке C++ (заголовочный файл unordered_set<>) есть тип неупорядоченных множеств std::unordered_set<>. Он поддерживает практически все те же функции, только не упорядочивает элементы. Например, если мы возьмем простое множество:

#include <iostream>
#include <set>

int main()
{
    std::set<int> numbers{3, 2, 5, 4};

    numbers.insert(1);
    numbers.insert(6);

    for (int n : numbers)
        std::cout << n << "\t";
    std::cout << std::endl;
}

То есть элементы будут расположены во множестве по умолчанию по возрастанию:

1       2       3       4       5       6

Теперь применим неупорядоченное множество unordered_set

#include <iostream>
#include <unordered_set>

int main()
{
    std::unordered_set<int> numbers{3, 2, 5, 4};

    numbers.insert(1);
    numbers.insert(6);

    for (int n : numbers)
        std::cout << n << "\t";
    std::cout << std::endl;
}

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

6       1       4       5       2       3

Причем функция insert() добавляет элементы в начало множества