Sett er en type assosiativ beholder der hvert element må være unikt fordi verdien til elementet identifiserer det. Verdiene lagres i en bestemt sortert rekkefølge, dvs. enten stigende eller synkende.
De std::sett klasse er en del av C++ Standard Template Library (STL) og den er definert inne i header-fil.
Syntaks:
legge til en array java
std::set set_name;>
Data-type: Sett kan ta hvilken som helst datatype avhengig av verdiene, f.eks. int, char, float, etc.
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;> }> |
>
>
java lang til strengProduksjon
F G>
Tidskompleksitet: O(N) // N er størrelsen på settet.
Hjelpeplass: PÅ)
Grunnen til at det bare ble skrevet ut F og G er at settet ikke tar flere samme verdier, det aksepterer bare en unik verdi. Vi kan bruke Multisett hvis vi ønsker å lagre flere samme verdier.
Sett sortert i synkende rekkefølge
Som standard er std::settet sortert i stigende rekkefølge. Vi har imidlertid muligheten til å endre sorteringsrekkefølgen ved å bruke 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 heltallProduksjon
12 10 5 4>
Tidskompleksitet: O(N) // N er størrelsen på settet.
Hjelpeplass: PÅ)
Merk: Vi kan bruke hvilken som helst komparator i stedet for større for å gi en tilpasset sortering.
Egenskaper
- Lagre ordre – Settet lagrer elementene i sortert rekkefølge.
- Verdier Kjennetegn – Alle elementene i et sett har unike verdier .
- Verdier naturen – Verdien til elementet kan ikke endres når det først er lagt til settet, selv om det er mulig å fjerne og deretter legge til den endrede verdien til det elementet. Altså verdiene er uforanderlig .
- Søketeknikk – Settene følger Binært søketre gjennomføring.
- Ordne rekkefølge - Verdiene i et sett er uindeksert .
Merk: For å lagre elementene i en usortert (tilfeldig) rekkefølge, unordered_set() kan bli brukt.
Noen grunnleggende funksjoner knyttet til Set
- begynne() – Returnerer en iterator til det første elementet i settet.
- slutt() – Returnerer en iterator til det teoretiske elementet som følger det siste elementet i settet.
- størrelse() – Returnerer antall elementer i settet.
- max_size() – Returnerer det maksimale antallet elementer som settet kan inneholde.
- tømme() – Returnerer om settet er tomt.
Tidskompleksitetene for å utføre ulike operasjoner på sett er:
- Innsetting av elementer – O(log N)
- Sletting av 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 tøm cacheProduksjon
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>
Forskjellig funksjon av settet i C++ STL
| Funksjon | Beskrivelse |
|---|---|
| begynne() | Returnerer en iterator til det første elementet i settet. |
| slutt() | Returnerer en iterator til det teoretiske elementet som følger det siste elementet i settet. |
| rbegin() | Returnerer en omvendt iterator som peker til det siste elementet i beholderen. |
| gjengi() | Returnerer en omvendt iterator som peker til det teoretiske elementet rett før det første elementet i settbeholderen. |
| crbegin() | Returnerer en konstant iterator som peker til det siste elementet i beholderen. |
| trosbekjennelse() | Returnerer en konstant iterator som peker til posisjonen rett før det første elementet i beholderen. |
| cbegin() | Returnerer en konstant iterator som peker til det første elementet i beholderen. |
| Noen() | Returnerer en konstant iterator som peker til posisjonen forbi det siste elementet i beholderen. |
| størrelse() | Returnerer antall elementer i settet. |
| max_size() | Returnerer det maksimale antallet elementer som settet kan inneholde. |
| tømme() | Returnerer om settet er tomt. |
| sette inn (konst g) | Legger til et nytt element 'g' til settet. |
| iteratorinnlegg (iteratorposisjon, konstant g) | Legger til et nytt element 'g' på posisjonen pekt av iteratoren. |
| slett (iteratorposisjon) | Fjerner elementet i posisjonen pekt av iteratoren. |
| slette(konst g) | Fjerner verdien 'g' fra settet. |
| klar() | Fjerner alle elementene fra settet. |
| key_comp() / verdi_komp() | Returnerer objektet som bestemmer hvordan elementene i settet er sortert («<» som standard). |
| finne (konst g) | Returnerer en iterator til elementet 'g' i settet hvis den finnes, ellers returnerer iteratoren til slutten. |
| telle(konst g) | Returnerer 1 eller 0 basert på om elementet 'g' er til stede i settet eller ikke. |
| nedre_grense(konst g) | Returnerer en iterator til det første elementet som tilsvarer 'g' eller definitivt ikke vil gå før elementet 'g' i settet. |
| øvre_grense(konst g) | Returnerer en iterator til det første elementet som vil gå etter elementet 'g' i settet. |
| like_område() | Funksjonen returnerer en iterator av par. (key_comp). Paret refererer til området som inkluderer alle elementene i beholderen som har en nøkkel som tilsvarer k. |
| emplace() | Denne funksjonen brukes til å sette inn et nytt element i settbeholderen, bare hvis elementet som skal settes inn er unikt og ikke allerede eksisterer i settet. |
| emplace_hint() | Returnerer en iterator som peker til posisjonen der innsettingen er utført. Hvis elementet som sendes i parameteren allerede eksisterer, returnerer det en iterator som peker til posisjonen der det eksisterende elementet er. |
| bytte() | Denne funksjonen brukes til å bytte ut innholdet i to sett, men settene må være av samme type, selv om størrelsene kan variere. |
| operatør= | '=' er en operator i C++ STL som kopierer (eller flytter) et sett til et annet sett og set::operator= er den tilsvarende operatorfunksjonen. |
| get_allocator() | Returnerer kopien av allokeringsobjektet som er knyttet til settet. |
Forskjellen mellom sett og uordnet sett
| Sett | Uordnet sett |
|---|---|
| Settet lagrer elementer i en sortert rekkefølge | Uordnet sett lagrer elementer i en usortert rekkefølge |
| Lagre/skaff kun unike elementer | Uordnet sett lagrer/erverver kun unike verdier |
| Settet bruker binære søketrær for implementering | Unordered Set bruker Hash-tabeller for implementering |
| Mer enn ett element kan slettes ved å gi start- og sluttiteratoren | Vi kan slette det elementet som iteratorposisjonen er gitt for |
| sett Set_Name; | unordered_set UnorderedSet_Name; |
For mer informasjon kan du se artikkelen – Sett vs uordnet sett .