Sæt er en type associativ beholder, hvor hvert element skal være unikt, fordi værdien af elementet identificerer det. Værdierne gemmes i en bestemt sorteret rækkefølge, dvs. enten stigende eller faldende.
Det std::sæt klasse er en del af C++ Standard Template Library (STL), og den er defineret inde i header-fil.
Syntaks:
tilføje til en matrix java
std::set set_name;>
Datatype: Set kan tage enhver datatype afhængigt af værdierne, f.eks. int, char, float osv.
Eksempel:
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;> }> |
>
>
css kommentarProduktion
F G>
Tidskompleksitet: O(N) // N er størrelsen af sættet.
Hjælpeplads: PÅ)
Grunden til, at det kun udskrev F og G, er, at sættet ikke tager flere samme værdier, det accepterer kun en unik værdi. Vi kan bruge Multisæt hvis vi ønsker at gemme flere samme værdier.
Sæt sorteret i faldende rækkefølge
Som standard er std::sættet sorteret i stigende rækkefølge. Vi har dog mulighed for at ændre sorteringsrækkefølgen ved at bruge følgende syntaks.
std::set set_name;>
Eksempel:
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;> }> |
>
>
java char til heltalProduktion
12 10 5 4>
Tidskompleksitet: O(N) // N er størrelsen af sættet.
Hjælpeplads: PÅ)
Bemærk: Vi kan bruge en hvilken som helst komparator i stedet for større for at give sæt en tilpasset sortering.
Ejendomme
- Opbevaring af ordre – Sættet gemmer elementerne i sorteret bestille.
- Værdier Karakteristika – Alle elementerne i et sæt har unikke værdier .
- Værdier Naturen – Værdien af elementet kan ikke ændres, når det først er føjet til sættet, selvom det er muligt at fjerne og derefter tilføje den ændrede værdi af dette element. Således værdierne er uforanderlig .
- Søgeteknik – Sæt følger Binært søgetræ implementering.
- Ordne orden – Værdierne i et sæt er uindekseret .
Bemærk: For at gemme elementerne i en usorteret (tilfældig) rækkefølge, unordered_set() Kan bruges.
Nogle grundlæggende funktioner forbundet med sæt
- begynde() – Returnerer en iterator til det første element i sættet.
- ende() – Returnerer en iterator til det teoretiske element, der følger efter det sidste element i sættet.
- størrelse() – Returnerer antallet af elementer i sættet.
- max_size() – Returnerer det maksimale antal elementer, som sættet kan indeholde.
- tom() – Returnerer, om sættet er tomt.
Tidskompleksiteten for at udføre forskellige operationer på sæt er:
- Indsættelse af elementer - O(log N)
- Sletning af elementer – 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 ryd cacheProduktion
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>
Forskellig funktion af sæt i C++ STL
| Fungere | Beskrivelse |
|---|---|
| begynde() | Returnerer en iterator til det første element i sættet. |
| ende() | Returnerer en iterator til det teoretiske element, der følger efter det sidste element i sættet. |
| rbegin() | Returnerer en omvendt iterator, der peger på det sidste element i beholderen. |
| render() | Returnerer en omvendt iterator, der peger på det teoretiske element lige før det første element i sætbeholderen. |
| crbegin() | Returnerer en konstant iterator, der peger på det sidste element i beholderen. |
| crend() | Returnerer en konstant iterator, der peger på positionen lige før det første element i beholderen. |
| cbegin() | Returnerer en konstant iterator, der peger på det første element i beholderen. |
| nogle få() | Returnerer en konstant iterator, der peger på positionen forbi det sidste element i beholderen. |
| størrelse() | Returnerer antallet af elementer i sættet. |
| max_size() | Returnerer det maksimale antal elementer, som sættet kan indeholde. |
| tom() | Returnerer, om sættet er tomt. |
| indsæt (konst g) | Tilføjer et nyt element 'g' til sættet. |
| iteratorindsats (iteratorposition, konstant g) | Tilføjer et nyt element 'g' ved den position, som iteratoren peger på. |
| slet (iterator position) | Fjerner elementet ved den position, som iteratoren peger på. |
| slette(konst g) | Fjerner værdien 'g' fra sættet. |
| klar() | Fjerner alle elementer fra sættet. |
| key_comp() / værdi_komp() | Returnerer det objekt, der bestemmer, hvordan elementerne i sættet er ordnet ('<' som standard). |
| find(konst g) | Returnerer en iterator til elementet 'g' i sættet, hvis den findes, ellers returnerer iteratoren til slutningen. |
| tæller (konst g) | Returnerer 1 eller 0 baseret på om elementet 'g' er til stede i sættet eller ej. |
| nedre_grænse(konst g) | Returnerer en iterator til det første element, der svarer til 'g' eller absolut ikke vil gå før elementet 'g' i sættet. |
| øvre_grænse(konst g) | Returnerer en iterator til det første element, der vil gå efter elementet 'g' i sættet. |
| lige_område() | Funktionen returnerer en iterator af par. (key_comp). Parret refererer til det område, der inkluderer alle elementer i beholderen, som har en nøgle svarende til k. |
| emplace() | Denne funktion bruges kun til at indsætte et nyt element i sætbeholderen, hvis elementet, der skal indsættes, er unikt og ikke allerede findes i sættet. |
| emplace_hint() | Returnerer en iterator, der peger på den position, hvor indsættelsen er udført. Hvis elementet, der sendes i parameteren, allerede eksisterer, returnerer det en iterator, der peger på den position, hvor det eksisterende element er. |
| bytte rundt() | Denne funktion bruges til at udveksle indholdet af to sæt, men sættene skal være af samme type, selvom størrelserne kan variere. |
| operatør= | '=' er en operator i C++ STL, der kopierer (eller flytter) et sæt til et andet sæt og set::operator= er den tilsvarende operatorfunktion. |
| get_allocator() | Returnerer kopien af allokeringsobjektet, der er knyttet til sættet. |
Forskellen mellem sæt og uordnet sæt
| Sæt | Uordnet sæt |
|---|---|
| Set gemmer elementer i en sorteret rækkefølge | Uordnet sæt gemmer elementer i en usorteret rækkefølge |
| Sæt lagre/anskaffe kun unikke elementer | Uordnet sæt lagrer/indhenter kun unikke værdier |
| Set bruger binære søgetræer til implementering | Unordered Set bruger Hash-tabeller til implementering |
| Mere end ét element kan slettes ved at angive start- og slutiteratoren | Vi kan slette det element, som iteratorpositionen er givet for |
| sæt Sæt_Navn; | unordered_set UnorderedSet_Name; |
For mere information kan du henvise til artiklen – Sæt vs uordnet sæt .