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:
system.out.println
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;> }> |
>
slovník c#
>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;> }> |
localdate
>
>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;> }> |
>
>
npm vymazať vyrovnávaciu pamäť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; |
Viac informácií nájdete v článku – Sady vs Neusporiadaná sada .