В этой статье мы подробно рассмотрим контейнер Set в STL. Множество (set) — это ассоциативный контейнер с уникальными элементами расположенными в определенном порядке.
Значение элемента в set также является ключом, который используется для доступа к нему. Все элементы множества должны быть уникальными.
Чтобы реализовать set, нам нужно включить заголовок <set> в нашу программу:
#include<set> |
Мы можем объявить множество следующим образом:
set<datatype> myset; |
Например, если нам нужно множество myset элемента целочисленного типа, мы можем объявить set так:
set<int> myset; |
Операции с SET
Контейнер set также поддерживает аналогичные операции, такие как карта, которую мы обсуждали в предыдущей статье. Ниже приведены некоторые из основных операций, поддерживаемых set:
- begin: возвращает итератор к первому элементу множества.
- end: возвращает итератор к элементу, следующему за последним элементом множества.
- insert: вставляет новый элемент во множество.
Операция вставки множества имеет три варианта:
-
- insert(element): напрямую вставляет элемент в set и переупорядочивает его.
- insert(position, hint): указывает позицию для вставки элемента.
- insert(iterator.begin(), iterator.end()): в этом варианте мы можем напрямую вставить диапазон в set, как массив или другое множество.
- erase: удаляет элемент из set.
- size: возвращает размер set.
- max_size: возвращает максимальный размер, который может содержать set.
- empty: возвращает значение, является ли set пустым.
- clear: удаляет все элементы из set.
- find: Находит элемент в set. Если элемент найден, он возвращает итератор к этому элементу в set. Если не найден, возвращает итератор в конец set.
Ниже представлена программа, демонстрирующая использование некоторых важных функций SET:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include <iostream> #include <set> #include <iterator> using namespace std; int main() { set <int> myset; myset.insert(140); myset.insert(130); myset.insert(160); myset.insert(120); cout<<"\nSize of myset: "<<myset.size(); set <int > :: iterator itr; cout << "\nThe set myset is : "; for (itr = myset.begin(); itr != myset.end(); ++itr) { cout << '\t' << *itr; } cout << endl; set<int>::iterator it = myset.begin(); myset.insert(it,100); cout << "\nAfter inserting 100,the set myset is : "; for (itr = myset.begin(); itr != myset.end(); ++itr) { cout << '\t' << *itr; } cout << endl; int arr[3] = {110,150,150}; myset.insert(arr,arr+2); cout << "\nAfter inserting array arr,the set myset is : "; for (itr = myset.begin(); itr != myset.end(); ++itr) { cout << '\t' << *itr; } cout << endl; cout << "\nAfter removal of elements less than 130, myset: "; myset.erase(myset.begin(), myset.find(130)); for (itr = myset.begin(); itr != myset.end(); ++itr) { cout << '\t' << *itr; } cout << endl; } |
Вывод данных:
Size of myset: 4 The set myset is: 120 130 140 160 After inserting 100, the set myset is: 100 120 130 140 160 After inserting array arr, the set myset is: 100 110 120 130 140 150 160 After removal of elements less than 130, myset: 130 140 150 160 |
Как показано в выводе данных, мы создали набор, используя простую функцию вставки.
Затем мы вставили элемент 100 в set, используя другой вариант функции вставки, передавая ссылку на итератор и значение элемента 100. Вы можете видеть, что после завершения вставки множество переупорядочивается, и порядок элементов сохраняется.
Затем мы вставили массив {110,150,150}, используя функцию вставки. Если вы видите вывод set, отображаемый после вставки массива, то значит, что во множество введено только одно значение 150. Это связано с тем, что все элементы в set уникальны.
Мы также отобразили размер set. Затем, используя функцию поиска, мы находим элементы, число которых меньше 130, а затем вызываем функцию стирания для удаления этих элементов. Затем мы отображаем результирующий set.
На этом мы закончили разговор об этом контейнере. Далее мы обсудим мультимножество, которое является расширением контейнера множеств.
Мультимножество (multiset)
Multiset — это ассоциативный контейнер, похожий на множество во всех аспектах, за исключением одного отличия, т. е. несколько элементов могут иметь одно и то же значение.
Объявление для мультимножества выглядит следующим образом:
multiset<int> mset; |
Мультимножество целочисленных элементов может быть объявлено как:
multiset<int> mset; |
Различные операции, поддерживаемые multiset, аналогичны операциям, поддерживаемым set.
Теперь мы непосредственно обсудим пример мультимножества, который демонстрирует используемую операцию:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include <iostream> #include <set> #include <iterator> using namespace std; int main() { multiset <int> myset; myset.insert(11); myset.insert(13); myset.insert(13); myset.insert(10); cout<<"\nSize of myset: "<<myset.size(); set <int > :: iterator itr; cout << "\nAfter inserting four elements, the multiset myset is : "; for (itr = myset.begin(); itr != myset.end(); ++itr) { cout << '\t' << *itr; } cout << endl; set<int>::iterator it = myset.begin(); myset.insert(it,15); cout << "\nAfter inserting 15,the multiset myset is : "; for (itr = myset.begin(); itr != myset.end(); ++itr) { cout << '\t' << *itr; } cout << endl; cout << "\nAfter removal of elements less than 15, myset: "; myset.erase(myset.begin(), myset.find(15)); for (itr = myset.begin(); itr != myset.end(); ++itr) { cout << '\t' << *itr; } cout << endl; } |
Вывод данных:
Size of myset: 4 After inserting four elements, the multiset myset is: 10 11 13 13 After inserting 15, the multiset myset is: 10 11 13 13 15 After removal of elements less than 15, myset: 15 |
Как показано в приведенном выше выводе, изначально мы вводим в мультимножество четыре элемента, два из которых одинаковы. Но в отличие от set, эти элементы успешно вставляются в мультимножество. Затем мы вставляем еще один элемент 15, указав позицию через итератор, который успешно вставлен.
Далее мы находим элементы меньше 15 в мультимножестве и вызываем функцию стирания для этих элементов. Наконец, мы отображаем мультимножество.
Неупорядоченное множество
Хотя множество представляет собой упорядоченную последовательность уникальных ключей, у нас есть еще один ассоциативный контейнер, который называется «неупорядоченное множество» и представляет собой набор ключей или элементов, хранящихся в любом порядке. Это означает, что элементы в неупорядоченном множестве «неупорядочены».
Подобно неупорядоченной карте, неупорядоченное множество также реализуется с использованием хеш-таблицы, в которой ключи хэшируются в индексы хэш-таблицы. Из-за использования хеш-таблицы невозможно поддерживать порядок элементов, в отличие от множества, в котором используется сбалансированная древовидная структура.
Заголовок для реализации неупорядоченного множества — <unordered_set>:
#include<unordered_set> |
Мы объявляем неупорядоченное множество целочисленного типа следующим образом:
Unordered_set<int> uset; |
Операции, поддерживаемые unordered_set, аналогичны операциям, поддерживаемым unordered_map.
Ниже приведен пример, демонстрирующий различные операции с unordered_set:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
#include<iostream> #include <unordered_set> using namespace std; int main() { unordered_set<int> uset; unordered_set<int> :: iterator it; for(int i=0;i<5;i++){ uset.insert(i+2); } cout<<"\nSize of uset: "<<uset.size(); cout<<endl; it= uset.begin(); uset.insert(it,99); int ary[]= { 13, 26, 39}; uset.insert(ary, ary+3); // Вставка с использованием способа 3 cout<<"\nElements in unordered set are: "; for(it= uset.begin(); it!=uset.end(); it++) cout << *it << " "; cout<<endl; int key=13; if (uset.find(key) == uset.end()) cout<<"\nkey = "<< key << “not found\n\n"; else cout << "\nFound key = " << key << endl << endl; cout<<"umap bucket_count : "<<uset.bucket_count(); cout<<"\nbucket_size : "<<uset.bucket_size(2); return 0; } |
Вывод данных:
Size of uset: 5 Elements in unordered set are: 99 39 6 5 26 4 3 13 2 Found key = 13 umap bucket_count : 11 bucket_size : 2 |
Как показано в приведенном выше выводе, мы сначала вставляем 5 элементов в неупорядоченное множество, а затем вставляем еще 4 элемента, которые демонстрируют использование вариантов функции вставки. Затем мы отображаем содержимое неупорядоченного множества.
Затем мы используем функцию поиска, чтобы определить, присутствует ли ключ = 13 в неупорядоченном множестве или нет.
После этого мы демонстрируем еще две функции ‘bucket_count’ и ‘bucket_size’. Эти функции связаны с внутренней реализацией неупорядоченной карты.
Этот контейнер также поддерживает другие функции итератора и функции, такие как max_size, clear, erase, empty и т.д., которые аналогичны другим контейнерам в STL.
Итог
На этом наша серия статей, связанная со стандартной библиотекой шаблонов (STL) на С++, подошла к концу. Мы надеемся, что темы, затронутые в этой серии, помогут вам лучше понять STL и его различные контейнеры.
С Уважением, МониторБанк