Seturile sunt un tip de container asociativ în care fiecare element trebuie să fie unic deoarece valoarea elementului îl identifică. Valorile sunt stocate într-o anumită ordine sortată, adică fie crescător, fie descrescător.
The std::set clasa este o parte a bibliotecii standard de șabloane (STL) C++ și este definită în interiorul fișier antet.
Sintaxă:
șir de matrice în c
std::set set_name;>
Tip de date: Setul poate lua orice tip de date în funcție de valori, de ex. int, char, float etc.
Exemplu:
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;> }> |
>
>Ieșire
F G>
Complexitatea timpului: O(N) // N este dimensiunea mulțimii.
Spațiu auxiliar: PE)
Motivul pentru care a imprimat doar F și G este că setul nu ia mai multe aceleași valori, ci acceptă doar o valoare unică. Putem folosi Multiset dacă dorim să stocăm mai multe valori identice.
Setați sortat în ordine descrescătoare
În mod implicit, setul std:: este sortat în ordine crescătoare. Cu toate acestea, avem opțiunea de a schimba ordinea de sortare utilizând următoarea sintaxă.
std::set set_name;>
Exemplu:
C++
imagine de reducere
// 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;> }> |
>
>Ieșire
12 10 5 4>
Complexitatea timpului: O(N) // N este dimensiunea mulțimii.
Spațiu auxiliar: PE)
Notă: Putem folosi orice comparator în loc de mai mare pentru a oferi setului o sortare personalizată a comenzii.
arbore binar java
Proprietăți
- Stocarea comenzii - Setul stochează elementele în sortat Ordin.
- Valori Caracteristici – Toate elementele dintr-un set au valori unice .
- Valori Natura – Valoarea elementului nu poate fi modificată odată ce este adăugat la set, deși este posibil să eliminați și apoi să adăugați valoarea modificată a acelui element. Astfel, valorile sunt imuabil .
- Tehnica de căutare – Seturile urmează Arborele de căutare binar implementare.
- Aranjarea ordinii - Valorile dintr-un set sunt neindexate .
Notă: Pentru a stoca elementele într-o ordine nesortată (aleatorie), set_neordonat() poate fi folosit.
Câteva funcții de bază asociate cu Set
- ÎNCEPE() – Returnează un iterator la primul element din set.
- Sfârşit() – Returnează un iterator la elementul teoretic care urmează ultimul element din set.
- mărimea() – Returnează numărul de elemente din set.
- max_size() – Returnează numărul maxim de elemente pe care setul le poate conține.
- gol() – Returnează dacă setul este gol.
Complexitățile de timp pentru efectuarea diferitelor operații pe platouri sunt:
- Inserarea elementelor - O(log N)
- Ștergerea elementelor - 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 șterge memoria cacheIeșire
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>
Funcție diferită a setului în C++ STL
| Funcţie | Descriere |
|---|---|
| ÎNCEPE() | Returnează un iterator la primul element din set. |
| Sfârşit() | Returnează un iterator la elementul teoretic care urmează ultimul element din set. |
| rbegin() | Returnează un iterator invers care indică ultimul element din container. |
| face() | Returnează un iterator invers care indică elementul teoretic chiar înaintea primului element din containerul set. |
| crbegin() | Returnează un iterator constant care indică ultimul element din container. |
| crez() | Returnează un iterator constant care indică poziția chiar înaintea primului element din container. |
| cbegin() | Returnează un iterator constant care indică primul element din container. |
| câțiva() | Returnează un iterator constant care indică poziția dincolo de ultimul element din container. |
| mărimea() | Returnează numărul de elemente din set. |
| max_size() | Returnează numărul maxim de elemente pe care setul le poate conține. |
| gol() | Returnează dacă setul este gol. |
| inserare (const g) | Adaugă un nou element „g” la set. |
| inserare iterator (poziție iterator, const g) | Adaugă un nou element „g” în poziția indicată de iterator. |
| ștergere (poziția iteratorului) | Îndepărtează elementul în poziția indicată de iterator. |
| șterge (const g) | Îndepărtează valoarea „g” din set. |
| clar() | Îndepărtează toate elementele din set. |
| key_comp() / value_comp() | Returnează obiectul care determină modul în care sunt ordonate elementele din set („<‘ implicit). |
| găsi (const g) | Returnează un iterator la elementul „g” din set dacă este găsit, altfel returnează iteratorul la sfârșit. |
| numărare (const g) | Returnează 1 sau 0 în funcție de faptul dacă elementul „g” este prezent sau nu în mulțime. |
| limita_inferioară (const g) | Returnează un iterator la primul element care este echivalent cu „g” sau cu siguranță nu va merge înaintea elementului „g” din set. |
| upper_bound(const g) | Returnează un iterator la primul element care va merge după elementul „g” din set. |
| equal_range() | Funcția returnează un iterator de perechi. (key_comp). Perechea se referă la gama care include toate elementele din container care au o cheie echivalentă cu k. |
| plasează() | Această funcție este folosită pentru a introduce un nou element în containerul setului, numai dacă elementul de inserat este unic și nu există deja în set. |
| emplace_hint() | Returnează un iterator care indică poziția în care se face inserarea. Dacă elementul trecut în parametru există deja, atunci returnează un iterator care indică poziția în care se află elementul existent. |
| swap() | Această funcție este utilizată pentru a schimba conținutul a două seturi, dar seturile trebuie să fie de același tip, deși dimensiunile pot diferi. |
| operator= | „=” este un operator în C++ STL care copiază (sau mută) un set într-un alt set și set::operator= este funcția de operator corespunzătoare. |
| get_allocator() | Returnează copia obiectului alocător asociat cu setul. |
Diferența dintre set și set neordonat
| A stabilit | Set necomandat |
|---|---|
| Set stochează elemente într-o ordine sortată | Set neordonat stochează elemente într-o ordine nesortată |
| Setați magazine/achiziționați doar elemente unice | Set neordonat stochează/obține numai valori unice |
| Set utilizează arbori de căutare binari pentru implementare | Unordoned Set folosește Hash Tables pentru implementare |
| Mai mult de un element poate fi șters dând iteratorul de început și de sfârșit | Putem șterge acel element pentru care este dată poziția iteratorului |
| setează Set_Name; | unordered_set UnorderedSet_Name; |
Pentru mai multe informații, puteți consulta articolul - Seturi vs Set neordonat .