Множество SET

Set — ассоциативный контейнер, который содержит упорядоченный набор уникальных объектов типа Key. Сортировка элементов осуществляется применением функции Compare к ключам множества. Операции поиска, удаления и вставки имеют логарифмическую сложность.

Чтобы подключить библиотеку Set используем :

In [1]:
#include <set>
In [2]:
#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;

Функции для работы с Set

В работе с Множеством чаще всего используются следующие функции:

  • s.insert(s1); - добавляет элемент S1 во множество S
  • s.erase(s2); -удаляет подмножество S2 из множества S
  • s.clear(); - очищает Множество S
  • s.size(); - считает размер множества S
  • s.max_size(); - выводит максимальный размер множества S

Больше функций можно найти по ссылке
https://en.cppreference.com/w/cpp/container/set

Сложность алгоритмов

Тк Set является упорядоченным множеством :

Структура Добавление Доступ Удаление Поиск
std::set $$O(\log{n})$$ $$O(\log{n})$$ $$O(\log{n})$$ $$O(\log{n})$$

Функция Печати Set

In [3]:
void print_Set(const std::set<std::string>& s)
{
    std::cout<<"Size = " << s.size() << " ; "<< endl;
    std::cout<<" { ";
    for ( auto x : s) {
        std::cout << x << " ; ";
    }
    std::cout<<" } ";
}
In [4]:
#include <bitset>


{
    std::set<std::string> a = {"1", "3", "4", "6"};
    std::bitset<64> bs(a.max_size());
    std::cout << "Max size: " << bs << std::endl;
    print_Set(a);
}
Max size: 0000001111111111111111111111111111111111111111111111111111111111
Size = 4 ; 
 { 1 ; 3 ; 4 ; 6 ;  } 

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

Добавление в Set осуществляется с помощью функции insert.

In [5]:
{
    std::set<std::string> my_Set;
    my_Set.insert("Stroustrup");
    my_Set.insert("BinPoisk");
    my_Set.insert("Sirius1Love");
    print_Set(my_Set);
}
Size = 3 ; 
 { BinPoisk ; Sirius1Love ; Stroustrup ;  } 

Рассмотрим случай с добавлением двух одинаковых элементов.

In [6]:
{
    std::set<std::string> my_Set;
    my_Set.insert("Stroustrup");
    my_Set.insert("BinPoisk");
    my_Set.insert("Sirius1Love");
    my_Set.insert("Stroustrup");
    print_Set(my_Set);
}
Size = 3 ; 
 { BinPoisk ; Sirius1Love ; Stroustrup ;  } 

Обратим внимание, что ни один из лементов не был добавлен дважды.

Рассмострим случай, когда все элементы Множества нам изместны

In [7]:
{
    std::set<std::string> months = {"Jan","March", "Feb", "March"};
    print_Set(months);
}
Size = 3 ; 
 { Feb ; Jan ; March ;  } 

Операции над Множествами:

Возможны следующие операции :

  • Сравнение
  • Объединение
  • Пересечнение
  • Разность
  • Симмерическая разность

Рассмотрим их на примерах:

Сравнение Множеств

In [8]:
// данные множества равны
{
    std::set<std::string> months_1 = {"Jan","March", "Feb", "March"};
    std::set<std::string> months_2 = {"Feb", "March","Jan"};
    std::cout << (months_1 == months_2) << endl;
}
1
In [9]:
//данные множества не равны
{
    std::set<std::string> months_1 = {"Janv","March", "Feb", "March"};
    std::set<std::string> months_2 = {"Feb", "March","Jan"};
    std::cout << (months_1 == months_2) << endl;
}
0

Объединение множеств

Новое множество содержит элементы обоих множеств без повторов;
In [10]:
{
    std::set<int> my_set_Comb1{ 1, 2, 3, 4, 5, 6, 7, 8 };
    std::set<int> my_set_Comb2{ 5, 7, 9, 10 };

    std::set<int> sets_combo;

    std::set_union(
    my_set_Comb1.begin(), my_set_Comb1.end(),
    my_set_Comb2.begin(), my_set_Comb2.end(),
    std::inserter(sets_combo, sets_combo.begin()));
    
    std::cout<<"{ ";
    for (int n : sets_combo)
        std::cout << n << " ; ";
    std::cout<<"}";
}
{ 1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 ; 8 ; 9 ; 10 ; }

Пересечение Множеств

Новое множество содержит элементы, принадлежащие обоим множествам
In [11]:
{
    std::set<int> m1{ 1, 2, 3, 4, 5, 6, 7, 8 };
    std::set<int> m2{ 5, 7, 9, 10 };
    
    std::set<int> s_intersection;

    std::set_intersection(m1.begin(), m1.end(),
        m2.begin(), m2.end(),
        std::inserter(s_intersection , s_intersection.begin()));
    std::cout<<"{ ";
    for (int n : s_intersection)
        std::cout << n << " ; ";
    std::cout<<"}";
}
{ 5 ; 7 ; }

Разность двух множеств

Новое множество состоит из элементов первого множества с вычетом элементов, которые совпадают с элементами второго
In [12]:
{
    std::set<int> set_3 = { 1, 2, 3, 5, 9 };
    std::set<int> set_4 = { 2, 5, 9 };
    std::set<int> diff;

    std::set_difference(set_3.begin(), set_3.end(), set_4.begin(), set_4.end(),
        std::inserter(diff, diff.begin()));
    
    std::cout<<"{ ";
    for (auto i : set_3) 
        std::cout << i << " ; ";
    std::cout<<"}"<<endl;
    std::cout << "     minus "<<endl;
    std::cout<<"{ ";
    for (auto i : set_4) 
        std::cout << i << " ; ";
    std::cout<<"}"<<endl;
    std::cout << "     is " << endl;
    std::cout<<"{ ";
    for (auto i : diff) 
        std::cout << i << " ; ";
    std::cout<<"}"<<endl;
}
{ 1 ; 2 ; 3 ; 5 ; 9 ; }
     minus 
{ 2 ; 5 ; 9 ; }
     is 
{ 1 ; 3 ; }

Симметрическая разность

Новое множество содержит элементы обоих множеств за исключением их пересечения

ДОПИСАТЬ ФОРМУЛЫ МАТЕМАТИЧЕСКИЕ!

In [13]:
{
    std::set<int> my_set_1{ 1,2,3,4,5,6,7,8 };
    std::set<int> my_set_2{ 5,7,9,10 };

    std::set<int> sets_intersection;

    std::set_symmetric_difference(
        my_set_1.begin(), my_set_1.end(),
        my_set_2.begin(), my_set_2.end(),
        std::inserter(sets_intersection,sets_intersection.begin()));
    std::cout<<"{ ";
    for (int n : sets_intersection)
        std::cout << n << " ; ";
    std::cout<<"}";
}
{ 1 ; 2 ; 3 ; 4 ; 6 ; 8 ; 9 ; 10 ; }

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

Как узнать, содержит ли наше множетсво заданный элемент? Воспользуемся функцией Count

In [14]:
{
    std::set<std::string> my_Month = {"Jan","March", "Feb", "March"};
    std::cout << my_Month.count("March");
}
1

Преобразования структур

Мы можем переходить от одной структуры к другой, применяя преобразования.

Например, сделаем переход от Вектора во Множество.

In [15]:
{
    std::vector<std::string> my_Vect={"a", "b", "a"};
    std::vector<int> a(10, 10);
    std::set<std::string> my_Set(begin(my_Vect), end(my_Vect));
    print_Set(my_Set);
}
Size = 2 ; 
 { a ; b ;  } 

Правила обхода Множества

Для прямого обхода Множества используются
s.begin() , s.begin()
Для реверсивного обхода
s.rbegin(); s.rend();

при этом

  • s.begin() == r.end()
  • s.end() == r.begin()

Посмотрим на их отличие:

In [16]:
{
    set<int> my_Int_Set{1, 2, 3, 4, 5};    
        cout << "prime" << endl;
    std::cout<<"{";
    for (auto it=my_Int_Set.begin(); it != my_Int_Set.end(); ++it) 
        cout << ' ' << *it;
    std::cout<<"}" << endl;
    
        cout << "reverse" << endl;
    std::cout<<"{";
    for (auto itr=my_Int_Set.rbegin(); itr != my_Int_Set.rend(); ++itr) 
        cout << ' ' << *itr;
    std::cout<<"}";
    return 0; 
}
prime
{ 1 2 3 4 5}
reverse
{ 5 4 3 2 1}
Out[16]:
0

Задача 1:

Среди заданного набора строк необходимо найти количество уникальных строк.

Формат ввода

  • N - число сторок,
  • Строки

Формат вывода
Количество уникальных строк в данном наборе.

Пример для понимания:

input output
6 3
first
second
first
third
second
second
In [17]:
{ 
    int Q;
    std::string str;
    set<string> bs;
    std::cin >> Q; //узнаем склолько строк будет
    for (Q; Q > 0; Q--) 
    {
        std::cin >> str;
        bs.insert(str);//вставляем в set
    }
    std::cout << bs.size(); //узнаем размер
}
1
1
1

Задача 2

Автобусы и Остановки. Условие : Для каждого маршрута, заданного множеством названий остановок, нужно либо выдать новый номер (первому маршруту — 1, второму — 2 и т. д.), либо вернуть номер существующего маршрута, которому соответствует такое множество остановок. Наборы остановок, которые можно получить друг из друга перестановкой элементов или добавлением/удалением повторяющихся, следует считать одинаковыми.

input output
5
2 Marushkino Kokoshkino New bus 1
1 Kokoshkino New bus 2
2 Marushkino Kokoshkino Already exists for 1
2 Kokoshkino Marushkino Already exists for 1
2 Kokoshkino Kokoshkino Already exists for 2
In [ ]:
{    
    /*сюда будем остановки складывать*/
    std::set<std::string> bus_stops; 
    /*каждому набору остановок будем давать номер маршрута*/
    std::map<set<std::string>, int> marshrut;
    int i, count_stop, number_marshrut = 0;
    string stop;
    std::cin >> i; /*количество запросов*/
    for (i; i > 0; i--) {
        std::cin >> count_stop; /*количество остановок*/
        for (count_stop; count_stop > 0; --count_stop) {
            std::cin >> stop; /*читаем остановки*/
            bus_stops.insert(stop); /*и добавляем в набор остановок*/
        }
        if (!marshrut.count(bus_stops)) {
            /*проверяем наличие данного набора остановок и если не нашли*/
            marshrut[bus_stops] = ++number_marshrut; /*то добавляем набор и приписываем новый маршрут по-порядку*/
            std::cout << "New bus " << number_marshrut << endl; /*пишем номер нового маршрута*/
        }
        else 
        { /*иначе, если есть такой набор*/
            std::cout << "Already exists for " << marshrut[bus_stops] << endl; /*пишем номер существующего маршрута*/
        }
        bus_stops.clear(); /*очистим набор остановок*/
    }
    return 0;
}
In [ ]: