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

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

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

Что такое set и multiset

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

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

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

st[3] = 19; // ошибка

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

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

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

#include <set>

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

set < [тип] > <имя>;
multiset < [тип] > <имя>

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

set <int> st; // пример
multiset <int> mst;

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

st.insert(<значение>);

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

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

set < [тип], greater [тип] > [имя];
set <long long, greater <long long> > st;  // пример

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

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

set <int> st{1,2,3,4,5};

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

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

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

set < [тип] > :: iterator it;
multiset < [тип] > :: iterator it2;

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

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

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

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

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

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

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

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

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

#include <iostream>
#include <set>
using namespace std;

int main() {
    set <int> st;

    for (int i = 0; i < 5; i++) {
        st.insert(i + 1);
    }

    set <int> :: iterator it = st.begin();

    cout << *it; // 1
    it++;
    cout << *it; // 2
    return 0;
}

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

#include <iostream>
#include <ctime>
#include <set>

using namespace std;

int main() {
    setlocale(LC_ALL, "Russian");
    srand(time(NULL));

    multiset <int> mst;

    cout << "Добавление случайных значений: " << endl;
    for (int i = 0; i < 10; i++) {
        int random = rand() % 10 + 1;
        mst.insert(random);
        cout << i + 1 << ") " << random << endl;
    }

    multiset <int> :: iterator it = mst.begin();

    cout << "Отсортированный вариант: " << endl;
    for (int i = 1; it != mst.end(); i++, it++) {
        cout << *it << " ";
    }
    
    system("pause");
    return 0;
}

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

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

Добавление случайных чисел:
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.

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

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

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

• copy
• erase
• lower_bound
• upper_bound
• find
• count
• equal_range

copy

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

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

copy ([начала], [конец], ostream_iterator< [тип] >(cout, [отступ]));

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

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

#include <iostream>
#include <iterator>  // ostream_iterator
#include <set>       // set
#include <ctime>     // time
using namespace std;

int main() {
    setlocale(LC_ALL, "Russian");

    set <int> st;

    cout << "Введите 5 чисел: " << endl;

    for (int i = 0; i < 5; i++) {
        cout << i + 1 << ") "; 
        int dig; cin >> dig;
        st.insert(dig);  
    }

    cout << "Содержимое set: ";

    copy(st.begin(), st.end(), ostream_iterator<int>(cout, " "));
    
    system("pause");
    return 0;
}

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

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

Введите 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. Либо удалить определенный диапазон значений.

   <имя>.erase([начала], [конец]);

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

Пример:

mst.erase(3);  // удалим все элементы со значением 3

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

lower_bound

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

<имя>.lower_bound(key);

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

upper_bound

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

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

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

find

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

find([ключ]);

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

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

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

if ([контейнер].find([ключ]) == [контейнер].end()) {
    cout << "Такого значение не существует";
}

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

set <int> numbers;

... считывание значений для numbers ...

for (int i = 1; i <= 30; i++) {
    dig = i;

    if (numbers.find(dig) == numbers.end()) {
        cout << "Такого значение " << dig << " не существует" << endl;
    }
}

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

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

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

count

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

st.count([ключ]);

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

equal_range

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

<имя>.equal_range([ключ]);

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

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

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

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

multiset <int> chisla;
multiset <int> :: iterator
pair <multiset <int> :: iterator, 
      multiset <int> :: iterator> it;
    
... инициализация ...       // 1 1 1 2 2 3 4 8 9 10 end()
    
it = chisla.equal_range(1);    ^     ^
    
it = chisla.equal_range(4);                ^ ^
    
chisla.insert(4);           // 1 1 1 2 2 3 4 4 8 9 10 end()
    
it = chisla.equal_range(4);                ^   ^
    
it = chisla.equal_range(10);                       ^^ ^

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

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

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

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

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

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

cout << "Введите начальное количество файлов: "; 
int n; cin >> n;

multiset <int> files;

for (int i = 0; i < n; i++) {
    cout << i + 1 << ") Введите индекс папки для добавления: "; 
    int a; cin >> a;
    files.insert(a);
}

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

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

if (operation == "add" || operation == "+") {
    cout << "Введите индекс новой папки: "; 
    int value; cin >> value;

    files.insert(value);

    cout << "Новые значения индексов: ";
    copy(files.begin(), files.end(), ostream_iterator(cout, " "));

    cout << endl;
}

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

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

if (operation == "erase" || operation == "-") {
    cout << "Укажите какой именно тип операции вам подходит: "; 
    string temp; cin >> temp;

    if (temp == "one" || temp == "1") {  
        cout << "Введите значение: "; 
        int value; cin >> value;

        multiset <int> :: iterator it = files.find(value);
        if (it == files.end()) {
            cout << "Такого индекса не существует!" << endl;
            continue;
        }

        files.erase(it);
    }

    if (temp == "all" || temp == "*") {
        cout << "Введите значение: "; int value; cin >> value;

        multiset <int> :: iterator it = files.find(value);

        if (!files.count(value)) {
            cout << "Таких индексов не существует!" << endl;
            continue;
        }

        files.erase(value);
    }
    cout << "Новые значения индексов: ";
    copy(files.begin(), files.end(), ostream_iterator(cout, " ")); // выводим
    cout << endl; 
}

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

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

if (operation == "lower_bound" || operation == ">=") {
    cout << "Введите значение для поиска: "; 
    int value; cin >> value;  

    multiset <int> :: iterator it;
    it = files.lower_bound(value);  // получаем итератор

    if (it == files.end()) {  // проверяем существует ли данный элемент
        cout << "Элемента >= " << value << " не существует!" << endl;
        continue;
    }
    cout << *it << endl;  
}

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

if (operation == "upper_bound" || operation == ">") {
    cout << "Введите значение для поиска: ";
    int value; cin >> value;

    multiset <int> :: iterator it;
    it = files.upper_bound(value);  // получаем местоположение

    if (it == files.end()) {  // проверяем существование
        cout << "Элемента > " << value << " не существует!" << endl;
        continue;
    }

    cout << *it << endl;
}

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

#include <iostream>
#include <set>
#include <iterator>

using namespace std;

int main() {
    setlocale(0, "");
    cout << "Введите начальное количество файлов: "; 
    int n; cin >> n;

    multiset <int> files;

    for (int i = 0; i < n; i++) {
        cout << i + 1 << ") Введите индекс папки для добавления: "; 
        int a; cin >> a;
        files.insert(a);
    }

    cout << endl << "Укажите количество операций: "; 
    q; cin >> q;

    for (int i = 0; i < q; i++) {
        cout << i + 1 << ") "; 
        string operation; cin >> operation;

        if (operation == "add" || operation == "+") {
            cout << "Введите индекс новой папки: "; 
            int value; cin >> value;

            files.insert(value);

            cout << "Новые значения индексов: ";
            copy(files.begin(), files.end(), ostream_iterator(cout, " "));

            cout << endl;
        }

        if (operation == "erase" || operation == "-") {
            cout << "Укажите какой именно тип операции вам подходит: "; 
            string temp; cin >> temp;

            if (temp == "one" || temp == "1") {  
                cout << "Введите значение: "; 
                int value; cin >> value;

                multiset <int> :: iterator it = files.find(value);
                if (it == files.end()) {
                    cout << "Такого индекса не существует!" << endl;
                    continue;
                }

                files.erase(it);
            }

            if (temp == "all" || temp == "*") {
                cout << "Введите значение: "; 
                int value; cin >> value;

                multiset <int> :: iterator it = files.find(value);

                if (!files.count(value)) {
                    cout << "Таких индексов не существует!" << endl;
                    continue;
                }

                files.erase(value);
            }
            cout << "Новые значения индексов: ";
            copy(files.begin(), files.end(), ostream_iterator(cout, " "));
            cout << endl; 
        } 

        if (operation == "lower_bound" || operation == ">=") {
            cout << "Введите значение для поиска: "; 
            int value; cin >> value;

            multiset <int> :: iterator it;
            it = files.lower_bound(value);

            if (it == files.end()) {
                cout << "Элемента >= " << value << " не существует!" << endl;
                continue;
            }
            cout << *it << endl; 
        } 

        if (operation == "upper_bound" || operation == ">") {
            cout << "Введите значение для поиска: "; 
            int value; cin >> value;

            multiset <int> :: iterator it;
            it = files.upper_bound(value);

            if (it == files.end()) {
                cout << "Элемента > " << value << " не существует!" << endl;
                continue;
            }

            cout << *it << endl;
        }
    }

    system("pause");
    return 0;
}

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

Введите начальное количество файлов: 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.

Интересное

Последние новости в мире программирования

Самые свежие новости и полезные материалы в моем telegram канале.

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

Плюсы:

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

Минусы:

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

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

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

Упражнение

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

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

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

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