Множество в STL

В этой статье мы подробно рассмотрим контейнер 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.

Читать также: Бинарное дерево поиска в C++

Ниже представлена программа, демонстрирующая использование некоторых важных функций SET:

#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;
 
 }

#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.

Теперь мы непосредственно обсудим пример мультимножества, который демонстрирует используемую операцию:

#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;
 
 }

#include <iostream>

#include <set>

#include <iterator>

using namespace std;

int main()

{

multiset <int> myset;

myset.insert(11);

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 в мультимножестве и вызываем функцию стирания для этих элементов. Наконец, мы отображаем мультимножество.

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

Хотя множество представляет собой упорядоченную последовательность уникальных ключей, у нас есть еще один ассоциативный контейнер, который называется «неупорядоченное множество» и представляет собой набор ключей или элементов, хранящихся в любом порядке. Это означает, что элементы в неупорядоченном множестве «неупорядочены».

Читать также: Операторы C++, типы и примеры

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

Заголовок для реализации неупорядоченного множества — <unordered_set>:

#include<unordered_set>

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

Unordered_set<int> uset;

Операции, поддерживаемые unordered_set, аналогичны операциям, поддерживаемым unordered_map.

Ниже приведен пример, демонстрирующий различные операции с unordered_set:

#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;
}

#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 и его различные контейнеры.

С Уважением, МониторБанк

Операции с SET

Мультимножество (multiset)

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

Итог

Вам также может понравиться

Операторы C++, типы и примеры

Преобразование типов в C++

Карты в STL

Добавить комментарий Отменить ответ