Sets zijn een soort associatieve container waarin elk element uniek moet zijn omdat de waarde van het element het identificeert. De waarden worden opgeslagen in een specifieke gesorteerde volgorde, d.w.z. oplopend of aflopend.
De standaard::set class is het onderdeel van de C++ Standard Template Library (STL) en wordt gedefinieerd in de header-bestand.
Syntaxis:
vergelijkbare tekenreeks in Java
std::set set_name;>
Data type: Set kan elk gegevenstype aannemen, afhankelijk van de waarden, b.v. int, char, float, enz.
Voorbeeld:
set val; // defining an empty set set val = {6, 10, 5, 1}; // defining a set with values> Programma:
C++
// C++ Program to Demonstrate> // the basic working of STL> #include> #include> int> main()> {> >std::set<>char>>een;> >a.insert(>'G'>);> >a.insert(>'F'>);> >a.insert(>'G'>);> >for> (>auto>& str : a) {> >std::cout << str <<>' '>;> >}> >std::cout <<>'
'>;> >return> 0;> }> |
>
>Uitvoer
F G>
Tijdcomplexiteit: O(N) // N is de grootte van de set.
Hulpruimte: OP)
De reden dat alleen F en G zijn afgedrukt, is dat de set niet meerdere dezelfde waarden aanneemt, maar alleen een unieke waarde. We kunnen gebruiken Multiset als we meerdere dezelfde waarden willen opslaan.
Stel gesorteerd in aflopende volgorde in
Standaard wordt de std::set in oplopende volgorde gesorteerd. We hebben echter de mogelijkheid om de sorteervolgorde te wijzigen met behulp van de volgende syntaxis.
std::set set_name;>
Voorbeeld:
C++
oeps concepten in Java
// 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;> }> |
>
>Uitvoer
12 10 5 4>
Tijdcomplexiteit: O(N) // N is de grootte van de set.
scripts uitvoeren onder Linux
Hulpruimte: OP)
Opmerking: We kunnen elke vergelijker gebruiken in plaats van een grotere om een aangepaste sortering te geven.
Eigenschappen
- Bestelling opslaan – In de set worden de elementen opgeslagen gesorteerd volgorde.
- Waarden Kenmerken – Alle elementen in een set hebben unieke waarden .
- Waarden Natuur – De waarde van het element kan niet worden gewijzigd zodra het aan de set is toegevoegd, maar het is wel mogelijk om de gewijzigde waarde van dat element te verwijderen en vervolgens toe te voegen. De waarden dus Zijn onveranderlijk .
- Zoektechniek – Sets volgen de Binaire zoekboom implementatie.
- Bestelling regelen – De waarden in een set zijn niet-geïndexeerd .
Opmerking: Om de elementen in een ongesorteerde (willekeurige) volgorde op te slaan, ongeordende_set() kan worden gebruikt.
Enkele basisfuncties die verband houden met Set
- beginnen() – Retourneert een iterator naar het eerste element in de set.
- einde() – Retourneert een iterator naar het theoretische element dat volgt op het laatste element in de set.
- maat() – Geeft het aantal elementen in de set terug.
- max_grootte() – Retourneert het maximale aantal elementen dat de set kan bevatten.
- leeg() – Geeft terug of de set leeg is.
De tijdscomplexiteiten voor het uitvoeren van verschillende bewerkingen op sets zijn:
- Invoeging van elementen – O(log N)
- Verwijdering van elementen – 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 cache leegmakenUitvoer
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>
Verschillende functies van Set in C++ STL
| Functie | Beschrijving |
|---|---|
| beginnen() | Retourneert een iterator naar het eerste element in de set. |
| einde() | Retourneert een iterator naar het theoretische element dat volgt op het laatste element in de set. |
| rbegin() | Retourneert een omgekeerde iterator die naar het laatste element in de container verwijst. |
| veroorzaken() | Retourneert een omgekeerde iterator die verwijst naar het theoretische element vlak vóór het eerste element in de set-container. |
| crbegin() | Retourneert een constante iterator die naar het laatste element in de container verwijst. |
| crend() | Retourneert een constante iterator die naar de positie vlak vóór het eerste element in de container wijst. |
| cbegin() | Retourneert een constante iterator die naar het eerste element in de container verwijst. |
| een paar() | Retourneert een constante iterator die verwijst naar de positie voorbij het laatste element in de container. |
| maat() | Retourneert het aantal elementen in de set. |
| max_grootte() | Retourneert het maximale aantal elementen dat de set kan bevatten. |
| leeg() | Geeft terug of de set leeg is. |
| invoegen(const g) | Voegt een nieuw element ‘g’ toe aan de set. |
| iteratorinvoeging (iteratorpositie, const g) | Voegt een nieuw element ‘g’ toe op de positie die door de iterator wordt aangegeven. |
| wissen (iteratorpositie) | Verwijdert het element op de positie die door de iterator wordt aangegeven. |
| wissen(const g) | Verwijdert de waarde ‘g’ uit de set. |
| duidelijk() | Verwijdert alle elementen uit de set. |
| sleutel_comp() / waarde_comp() | Geeft het object terug dat bepaalt hoe de elementen in de set worden geordend (standaard ‘<‘). |
| vind(const g) | Retourneert een iterator naar het element ‘g’ in de set, indien gevonden, en retourneert anders de iterator naar het einde. |
| tellen(const g) | Retourneert 1 of 0, afhankelijk van of het element ‘g’ aanwezig is in de set of niet. |
| ondergrens(const g) | Geeft een iterator terug naar het eerste element dat gelijkwaardig is aan ‘g’ of dat zeker niet vóór het element ‘g’ in de set komt. |
| bovengrens(const g) | Retourneert een iterator naar het eerste element dat na het element ‘g’ in de set komt. |
| gelijk_bereik() | De functie retourneert een iterator van paren. (sleutel_comp). Het paar verwijst naar het bereik dat alle elementen in de container omvat die een sleutel hebben die equivalent is aan k. |
| plaats() | Deze functie wordt alleen gebruikt om een nieuw element in de setcontainer in te voegen als het in te voegen element uniek is en nog niet in de set bestaat. |
| emplace_hint() | Retourneert een iterator die verwijst naar de positie waar de invoeging is voltooid. Als het in de parameter doorgegeven element al bestaat, retourneert het een iterator die verwijst naar de positie waar het bestaande element zich bevindt. |
| ruil() | Deze functie wordt gebruikt om de inhoud van twee sets uit te wisselen, maar de sets moeten van hetzelfde type zijn, hoewel de maten kunnen verschillen. |
| exploitant= | De ‘=’ is een operator in C++ STL die een set naar een andere set kopieert (of verplaatst) en set::operator= is de overeenkomstige operatorfunctie. |
| get_allocator() | Retourneert de kopie van het allocatorobject dat aan de set is gekoppeld. |
Verschil tussen set en ongeordende set
| Set | Ongeordende set |
|---|---|
| Stel winkelelementen in een gesorteerde volgorde in | Ongeordende set slaat elementen in een ongesorteerde volgorde op |
| Stel alleen winkels in/verkrijg unieke elementen | Ongeordend Winkels instellen/alleen unieke waarden verkrijgen |
| Set gebruikt binaire zoekbomen voor implementatie | Unordered Set gebruikt hashtabellen voor implementatie |
| Er kan meer dan één element worden gewist door de begin- en einditerator op te geven | We kunnen dat element wissen waarvoor de iteratorpositie is gegeven |
| stel Set_Name in; | ongeordende_set ongeordendeset_naam; |
Voor meer informatie kunt u het artikel raadplegen – Sets versus ongeordende set .