Uppsättningar är en typ av associativ behållare där varje element måste vara unikt eftersom värdet på elementet identifierar det. Värdena lagras i en specifik sorterad ordning, dvs antingen stigande eller fallande.
De std::set klass är en del av C++ Standard Template Library (STL) och den är definierad inuti header-fil.
Syntax:
uppdatera i sql med join
std::set set_name;>
Data typ: Set kan ta vilken datatyp som helst beroende på värdena, t.ex. int, char, float, etc.
Exempel:
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;> }> |
>
pandor skapar dataram
>Produktion
F G>
Tidskomplexitet: O(N) // N är storleken på mängden.
Hjälputrymme: PÅ)
Anledningen till att det bara skrevs ut F och G är att uppsättningen inte tar flera samma värden utan bara accepterar ett unikt värde. Vi kan använda Multiset om vi vill lagra flera samma värden.
Uppsättningen sorterad i fallande ordning
Som standard sorteras std::set i stigande ordning. Vi har dock möjlighet att ändra sorteringsordningen genom att använda följande syntax.
std::set set_name;>
Exempel:
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;> }> |
objektiv java
>
>Produktion
12 10 5 4>
Tidskomplexitet: O(N) // N är storleken på mängden.
Hjälputrymme: PÅ)
Notera: Vi kan använda vilken komparator som helst i stället för större för att ge en anpassad sortering.
Egenskaper
- Lagring av order – Setet lagrar elementen i sorterad beställa.
- Värden Egenskaper – Alla element i en uppsättning har unika värden .
- Värderar naturen – Värdet på elementet kan inte ändras när det väl har lagts till i uppsättningen, men det är möjligt att ta bort och sedan lägga till det modifierade värdet för det elementet. Alltså värdena är oföränderlig .
- Sökteknik – Uppsättningar följer Binärt sökträd genomförande.
- Ordna ordning – Värdena i en uppsättning är oindexerad .
Notera: För att lagra elementen i en osorterad (slumpmässig) ordning, unordered_set() kan användas.
Några grundläggande funktioner associerade med Set
- Börja() – Returnerar en iterator till det första elementet i uppsättningen.
- slutet() – Returnerar en iterator till det teoretiska elementet som följer efter det sista elementet i mängden.
- storlek() – Returnerar antalet element i uppsättningen.
- max_size() – Returnerar det maximala antalet element som uppsättningen kan innehålla.
- tömma() – Returnerar om uppsättningen är tom.
Tidskomplexiteten för att utföra olika operationer på uppsättningar är:
- Insättning av element – O(log N)
- Radering av element – 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 rensa 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>
Olika funktioner för Set i C++ STL
| Fungera | Beskrivning |
|---|---|
| Börja() | Returnerar en iterator till det första elementet i uppsättningen. |
| slutet() | Returnerar en iterator till det teoretiska elementet som följer efter det sista elementet i mängden. |
| rbegin() | Returnerar en omvänd iterator som pekar på det sista elementet i behållaren. |
| framställa() | Returnerar en omvänd iterator som pekar på det teoretiska elementet precis före det första elementet i uppsättningsbehållaren. |
| crbegin() | Returnerar en konstant iterator som pekar på det sista elementet i behållaren. |
| crend() | Returnerar en konstant iterator som pekar på positionen precis före det första elementet i behållaren. |
| cbegin() | Returnerar en konstant iterator som pekar på det första elementet i behållaren. |
| några() | Returnerar en konstant iterator som pekar på positionen förbi det sista elementet i behållaren. |
| storlek() | Returnerar antalet element i uppsättningen. |
| max_size() | Returnerar det maximala antalet element som uppsättningen kan innehålla. |
| tömma() | Returnerar om uppsättningen är tom. |
| infoga (konst g) | Lägger till ett nytt element 'g' till uppsättningen. |
| iterator insert (iterator position, const g) | Lägger till ett nytt element 'g' vid den position som iteratorn pekar på. |
| radera (iteratorposition) | Tar bort elementet vid den position som iteratorn pekar på. |
| radera(konst g) | Tar bort värdet 'g' från uppsättningen. |
| klar() | Tar bort alla element från setet. |
| key_comp() / värde_komp() | Returnerar objektet som bestämmer hur elementen i uppsättningen är ordnade ('<' som standard). |
| hitta (konst g) | Returnerar en iterator till elementet 'g' i uppsättningen om den hittas, annars returnerar iteratorn till slutet. |
| räkna (konst g) | Returnerar 1 eller 0 baserat på om elementet 'g' finns i mängden eller inte. |
| nedre_gräns(konst g) | Returnerar en iterator till det första elementet som är ekvivalent med 'g' eller som definitivt inte kommer att gå före elementet 'g' i uppsättningen. |
| upper_bound(const g) | Returnerar en iterator till det första elementet som kommer efter elementet 'g' i uppsättningen. |
| lika_intervall() | Funktionen returnerar en iterator av par. (key_comp). Paret hänvisar till intervallet som inkluderar alla element i behållaren som har en nyckel som motsvarar k. |
| emplace() | Denna funktion används för att infoga ett nytt element i uppsättningsbehållaren, endast om elementet som ska infogas är unikt och inte redan finns i uppsättningen. |
| emplace_hint() | Returnerar en iterator som pekar på positionen där infogningen görs. Om elementet som skickas i parametern redan existerar, returnerar det en iterator som pekar på positionen där det befintliga elementet är. |
| byta() | Denna funktion används för att utbyta innehållet i två set men seten måste vara av samma typ, även om storlekarna kan skilja sig åt. |
| operator= | '=' är en operator i C++ STL som kopierar (eller flyttar) en uppsättning till en annan uppsättning och set::operator= är motsvarande operatorfunktion. |
| get_allocator() | Returnerar kopian av allokeringsobjektet som är associerat med uppsättningen. |
Skillnaden mellan uppsättning och oordnad uppsättning
| Uppsättning | Oordnat set |
|---|---|
| Set lagrar element i en sorterad ordning | Oordnad uppsättning lagrar element i osorterad ordning |
| Ställ in butiker/skaffa endast unika element | Oordnat set lagrar/skaffar endast unika värden |
| Set använder binära sökträd för implementering | Unordered Set använder Hash-tabeller för implementering |
| Mer än ett element kan raderas genom att ge start- och slutiteratorn | Vi kan radera det element för vilket iteratorpositionen är given |
| set Set_Name; | unordered_set UnorderedSet_Name; |
För mer information kan du hänvisa till artikeln – Uppsättningar vs oordnade uppsättningar .