SADA V C++ STANDARD TEMPLATE LIBRARY (STL) - TECHCODEVIEW.COM

Množiny sú typom asociatívneho kontajnera, v ktorom musí byť každý prvok jedinečný, pretože ho identifikuje hodnota prvku. Hodnoty sú uložené v špecifickom zoradenom poradí, tj buď vzostupne alebo zostupne.

The std::set trieda je súčasťou C++ Standard Template Library (STL) a je definovaná vo vnútri hlavičkový súbor.

Syntax:

std::set set_name;

Dátový typ: Set môže mať ľubovoľný dátový typ v závislosti od hodnôt, napr. int, char, float atď.

Príklad:

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

Program:

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

Výkon

F G

Časová zložitosť: O(N) // N je veľkosť súpravy.

Pomocný priestor: O(N)

Dôvod, prečo vytlačil iba F a G, je ten, že množina nemá viacero rovnakých hodnôt, akceptuje iba jedinečnú hodnotu. Môžeme použiť Multiset ak chceme uložiť viacero rovnakých hodnôt.

Nastaviť Zoradené v zostupnom poradí

Štandardne je std::set zoradený vzostupne. Máme však možnosť zmeniť poradie zoradenia pomocou nasledujúcej syntaxe.

std::set  set_name;

Príklad:

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

Výkon

12 10 5 4

Časová zložitosť: O(N) // N je veľkosť súpravy.

Pomocný priestor: O(N)

Poznámka: Môžeme použiť ľubovoľný porovnávač namiesto väčšieho, aby sme získali vlastné triedenie poradia.

Vlastnosti

Uloženie objednávky - Sada ukladá prvky do triedené objednať.
Hodnoty Charakteristika – Všetky prvky v súprave majú jedinečné hodnoty .
Hodnoty Príroda – Hodnotu prvku nie je možné po pridaní do množiny zmeniť, je však možné odstrániť a potom pridať upravenú hodnotu tohto prvku. Teda hodnoty sú nemenný .
Technika vyhľadávania – Sady nasledujú Binárny vyhľadávací strom implementáciu.
Vybavovanie objednávky - Hodnoty v sade sú neindexované .

Poznámka: Ak chcete prvky uložiť v netriedenom (náhodnom) poradí, unordered_set() môže byť použité.

Niektoré základné funkcie spojené so súpravou

začať() – Vráti iterátor na prvý prvok v množine.
koniec() – Vráti iterátor teoretického prvku, ktorý nasleduje po poslednom prvku v množine.
veľkosť () – Vráti počet prvkov v množine.
max_size() – Vráti maximálny počet prvkov, ktoré môže množina obsahovať.
prázdne () – Vráti, či je množina prázdna.

Časová zložitosť vykonávania rôznych operácií na množinách je:

Vkladanie prvkov - O (log N)
Vymazanie prvkov - 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> >>::iterator 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;> }>

Výkon

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

Iná funkcia množiny v C++ STL

Funkcia	Popis
začať()	Vráti iterátor na prvý prvok v množine.
koniec()	Vráti iterátor teoretického prvku, ktorý nasleduje po poslednom prvku v množine.
rbegin()	Vráti spätný iterátor ukazujúci na posledný prvok v kontajneri.
render()	Vráti spätný iterátor ukazujúci na teoretický prvok tesne pred prvým prvkom v kontajneri množiny.
crbegin()	Vráti konštantný iterátor ukazujúci na posledný prvok v kontajneri.
vyznanie ()	Vráti konštantný iterátor ukazujúci na pozíciu tesne pred prvým prvkom v kontajneri.
cbegin()	Vráti konštantný iterátor ukazujúci na prvý prvok v kontajneri.
zopár()	Vráti konštantný iterátor ukazujúci na pozíciu za posledným prvkom v kontajneri.
veľkosť ()	Vráti počet prvkov v množine.
max_size()	Vráti maximálny počet prvkov, ktoré môže množina obsahovať.
prázdne ()	Vráti, či je množina prázdna.
vložiť (konšt. g)	Pridá do množiny nový prvok „g“.
vložka iterátora (pozícia iterátora, const g)	Pridá nový prvok „g“ na pozíciu, na ktorú ukazuje iterátor.
vymazať (pozícia iterátora)	Odstráni prvok na pozícii, na ktorú ukazuje iterátor.
vymazať (konšt. g)	Odstráni hodnotu „g“ zo súboru.
jasný()	Odstráni všetky prvky zo sady.
key_comp() / value_comp()	Vráti objekt, ktorý určuje, ako sú prvky v množine usporiadané (predvolene „ <“.
nájsť (konšt. g)	Vráti iterátor prvku „g“ v množine, ak sa nájde, inak vráti iterátor na koniec.
počet (konšt. g)	Vráti 1 alebo 0 podľa toho, či je prvok „g“ prítomný v množine alebo nie.
dolná_medza (konšt. g)	Vráti iterátor k prvému prvku, ktorý je ekvivalentný prvku „g“ alebo určite nebude pred prvkom „g“ v množine.
horná_medza(konst g)	Vráti iterátor na prvý prvok, ktorý bude nasledovať po prvku „g“ v množine.
rovnaký_rozsah()	Funkcia vracia iterátor párov. (key_comp). Dvojica sa týka rozsahu, ktorý zahŕňa všetky prvky v kontajneri, ktoré majú kľúč ekvivalentný k.
umiestniť()	Táto funkcia sa používa na vloženie nového prvku do kontajnera sady, iba ak je prvok, ktorý sa má vložiť, jedinečný a v sade ešte neexistuje.
emplace_hint()	Vráti iterátor ukazujúci na pozíciu, kde je vkladanie dokončené. Ak prvok odovzdaný v parametri už existuje, vráti iterátor ukazujúci na pozíciu, kde sa nachádza existujúci prvok.
vymeniť ()	Táto funkcia sa používa na výmenu obsahu dvoch sád, ale sady musia byť rovnakého typu, aj keď veľkosti sa môžu líšiť.
operátor=	„=“ je operátor v C++ STL, ktorý kopíruje (alebo presúva) množinu do inej množiny a množina::operator= je zodpovedajúca funkcia operátora.
get_allocator()	Vráti kópiu objektu alokátora priradeného k množine.

Rozdiel medzi súpravou a neusporiadanou súpravou

Set	Neusporiadaná sada
Set ukladá prvky v zoradenom poradí	Unordered Set ukladá prvky v nezoradenom poradí
Nastaviť ukladá/získať iba jedinečné prvky	Unordered Set ukladá/získava iba jedinečné hodnoty
Sada používa na implementáciu binárne vyhľadávacie stromy	Unordered Set používa na implementáciu hash tabuľky
Viac ako jeden prvok je možné vymazať zadaním počiatočného a koncového iterátora	Môžeme vymazať ten prvok, pre ktorý je daná pozícia iterátora
set Set_Name;	unordered_set UnorderedSet_Name;