ВСТАНОВЛЕНО В СТАНДАРТНІЙ БІБЛІОТЕЦІ ШАБЛОНІВ C++ (STL) - TECHCODEVIEW.COM

Набори — це тип асоціативного контейнера, у якому кожен елемент має бути унікальним, оскільки значення елемента ідентифікує його. Значення зберігаються в певному порядку, тобто за зростанням або спаданням.

The std::set є частиною стандартної бібліотеки шаблонів C++ (STL) і визначено всередині файл заголовка.

Синтаксис:

std::set set_name;

Тип даних: Набір може приймати будь-який тип даних залежно від значень, напр. int, char, float тощо.

приклад:

set val; // defining an empty set set val = {6, 10, 5, 1}; // defining a set with values

програма:

C++

// C++ Program to Demonstrate> // the basic working of STL> #include> #include> int> main()> {> > std::set <> char> >a;> > a.insert(> 'G'> );> > a.insert(> 'F'> );> > a.insert(> 'G'> );> > for> (> auto> & str : a) {> > std::cout < < str < <> ' '> ;> > }> > std::cout < <>

'
'>

;> > return> 0;> }>

Вихід

F G

Часова складність: O(N) // N — розмір набору.

Допоміжний простір: O(N)

Причина, по якій він друкує лише F і G, полягає в тому, що набір не приймає кілька однакових значень, він приймає лише унікальне значення. Ми можемо використовувати Мультинабір якщо ми хочемо зберегти кілька однакових значень.

Набір відсортовано за спаданням

За замовчуванням std::set відсортовано в порядку зростання. Однак у нас є можливість змінити порядок сортування за допомогою наступного синтаксису.

std::set  set_name;

приклад:

C++

// C++ program to demonstrate the creation of descending> // order set container> #include> #include> using> namespace> std;> int> main()> {> > set <> int> , greater <> int> >> s1;> > s1.insert(10);> > s1.insert(5);> > s1.insert(12);> > s1.insert(4);> > for> (> auto> i : s1) {> > cout < < i < <> ' '> ;> > }> > return> 0;> }>

Вихід

12 10 5 4

Часова складність: O(N) // N — розмір набору.

Допоміжний простір: O(N)

Примітка: Ми можемо використовувати будь-який компаратор замість більшого, щоб надати набору власний порядок сортування.

Властивості

Порядок зберігання – Набір зберігає елементи в відсортований порядок.
Цінності Характеристики – Усі елементи в наборі мають унікальні цінності .
Цінності Природа – Значення елемента не можна змінити після його додавання до набору, хоча можна видалити, а потім додати змінене значення цього елемента. Отже, цінності є незмінний .
Техніка пошуку – Набори слідують Двійкове дерево пошуку впровадження.
Організація замовлення – Значення в наборі є неіндексований .

Примітка: Щоб зберегти елементи в несортованому (випадковому) порядку, unordered_set() може бути використаний.

Деякі основні функції, пов’язані з Set

почати() – Повертає ітератор до першого елемента в наборі.
кінець() – Повертає ітератор до теоретичного елемента, який слідує за останнім елементом у наборі.
розмір() – Повертає кількість елементів у наборі.
max_size() – Повертає максимальну кількість елементів, яку може містити набір.
порожній() – Повертає, чи набір порожній.

Часова складність для виконання різних операцій над множинами:

Вставка елементів – O(log N)
Видалення елементів – O(log N)

CPP

// C++ program to demonstrate various functions of> // STL> #include> #include> #include> using> namespace> std;> int> main()> {> > // empty set container> > set <> int> , greater <> int> >> s1;> > // insert elements in random order> > s1.insert(40);> > s1.insert(30);> > s1.insert(60);> > s1.insert(20);> > s1.insert(50);> > // only one 50 will be added to the set> > s1.insert(50);> > s1.insert(10);> > // printing set s1> > set <> int> , greater <> int> >>::ітератор itr;> > cout < <>

'
The set s1 is : 
'>

;> > for> (itr = s1.begin(); itr != s1.end(); itr++) {> > cout < < *itr < <> ' '> ;> > }> > cout < < endl;> > // assigning the elements from s1 to s2> > set <> int> >s2(s1.begin(), s1.end());> > // print all elements of the set s2> > cout < <>

'
The set s2 after assign from s1 is : 
'>

;> > for> (itr = s2.begin(); itr != s2.end(); itr++) {> > cout < < *itr < <> ' '> ;> > }> > cout < < endl;> > // remove all elements up to 30 in s2> > cout < <>

'
s2 after removal of elements less than 30 '>

>

':
'>

;> > s2.erase(s2.begin(), s2.find(30));> > for> (itr = s2.begin(); itr != s2.end(); itr++) {> > cout < < *itr < <> ' '> ;> > }> > // remove element with value 50 in s2> > int> num;> > num = s2.erase(50);> > cout < <>

'
s2.erase(50) : '>

;> > cout < < num < <>

' removed
'>

;> > for> (itr = s2.begin(); itr != s2.end(); itr++) {> > cout < < *itr < <> ' '> ;> > }> > cout < < endl;> > // lower bound and upper bound for set s1> > cout < <> 's1.lower_bound(40) : '> > < < *s1.lower_bound(40) < < endl;> > cout < <> 's1.upper_bound(40) : '> > < < *s1.upper_bound(40) < < endl;> > // lower bound and upper bound for set s2> > cout < <> 's2.lower_bound(40) : '> > < < *s2.lower_bound(40) < < endl;> > cout < <> 's2.upper_bound(40) : '> > < < *s2.upper_bound(40) < < endl;> > return> 0;> }>

Вихід

The set s1 is : 60 50 40 30 20 10 The set s2 after assign from s1 is : 10 20 30 40 50 60 s2 after removal of elements less than 30 : 30 40 50 60 s2.erase(50) : 1 removed 30 40 60 s1.lower_bound(40) : 40 s1.upper_bound(40) : 30 s2.lower_bound(40) : 40 s2.upper_bound(40) : 60

Інша функція набору в C++ STL

функція	опис
почати()	Повертає ітератор до першого елемента в наборі.
кінець()	Повертає ітератор до теоретичного елемента, який слідує за останнім елементом у наборі.
rbegin()	Повертає зворотний ітератор, що вказує на останній елемент у контейнері.
render()	Повертає зворотний ітератор, що вказує на теоретичний елемент безпосередньо перед першим елементом у контейнері набору.
crbegin()	Повертає постійний ітератор, що вказує на останній елемент у контейнері.
crend()	Повертає постійний ітератор, що вказує на позицію безпосередньо перед першим елементом у контейнері.
cbegin()	Повертає постійний ітератор, що вказує на перший елемент у контейнері.
декілька()	Повертає постійний ітератор, що вказує на позицію після останнього елемента в контейнері.
розмір()	Повертає кількість елементів у наборі.
max_size()	Повертає максимальну кількість елементів, яку може містити набір.
порожній()	Повертає, чи набір порожній.
вставити (const g)	Додає новий елемент «g» до набору.
вставка ітератора (позиція ітератора, const g)	Додає новий елемент «g» у позиції, на яку вказує ітератор.
стерти (позиція ітератора)	Видаляє елемент у позиції, на яку вказує ітератор.
стерти (const g)	Вилучає значення «g» із набору.
очистити()	Вилучає всі елементи з набору.
key_comp() / value_comp()	Повертає об’єкт, який визначає порядок розташування елементів у наборі (« <» за замовчуванням).
знайти (const g)	Повертає ітератор до елемента «g» у наборі, якщо він знайдений, інакше повертає ітератор до кінця.
кількість (const g)	Повертає 1 або 0 залежно від того, присутній елемент «g» у наборі чи ні.
нижня_межа (const g)	Повертає ітератор до першого елемента, який еквівалентний «g» або точно не буде передувати елементу «g» у наборі.
верхня_межа (const g)	Повертає ітератор до першого елемента, який буде йти після елемента «g» у наборі.
рівний_діапазон()	Функція повертає ітератор пар. (key_comp). Пара відноситься до діапазону, який включає всі елементи в контейнері, які мають ключ, еквівалентний k.
поставити()	Ця функція використовується для вставки нового елемента в контейнер набору, лише якщо елемент, який потрібно вставити, унікальний і ще не існує в наборі.
emplace_hint()	Повертає ітератор, що вказує на позицію, де виконується вставка. Якщо елемент, переданий у параметрі, уже існує, він повертає ітератор, що вказує на позицію, де знаходиться існуючий елемент.
своп()	Ця функція використовується для обміну вмістом двох наборів, але набори мають бути одного типу, хоча розміри можуть відрізнятися.
оператор=	«=» — це оператор у C++ STL, який копіює (або переміщує) набір до іншого набору, а set::operator= — це відповідна операторна функція.
get_allocator()	Повертає копію об’єкта розподілювача, пов’язаного з набором.

Різниця між набором і невпорядкованим набором

встановити	Невпорядкований набір
Набір зберігає елементи в упорядкованому порядку	Unordered Set зберігає елементи в несортованому порядку
Набір магазинів/отримання тільки унікальних елементів	Невпорядкований набір зберігає/отримує лише унікальні значення
Set використовує двійкові дерева пошуку для реалізації	Unordered Set використовує хеш-таблиці для реалізації
Більш ніж один елемент можна стерти, вказавши початковий і кінцевий ітератори	Ми можемо стерти той елемент, для якого вказана позиція ітератора
встановити Set_Name;	unordered_set UnorderedSet_Name;