Mengen sind eine Art assoziativer Container, in dem jedes Element eindeutig sein muss, da der Wert des Elements es identifiziert. Die Werte werden in einer bestimmten Sortierreihenfolge gespeichert, d. h. entweder aufsteigend oder absteigend.
Der std::set Die Klasse ist Teil der C++ Standard Template Library (STL) und wird innerhalb der definiert Header-Datei.
Syntax:
Java generiert Zufallszahlen
std::set set_name;>
Datentyp: Set kann abhängig von den Werten jeden Datentyp annehmen, z. B. int, char, float usw.
Beispiel:
set val; // defining an empty set set val = {6, 10, 5, 1}; // defining a set with values> Programm:
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;> }> |
>
>Ausgabe
F G>
Zeitkomplexität: O(N) // N ist die Größe der Menge.
Hilfsraum: AN)
Der Grund dafür, dass nur F und G gedruckt wurden, liegt darin, dass set nicht mehrere gleiche Werte annimmt, sondern nur einen eindeutigen Wert. Wir können benutzen Multiset wenn wir mehrere gleiche Werte speichern möchten.
In absteigender Reihenfolge sortiert
Standardmäßig ist std::set in aufsteigender Reihenfolge sortiert. Wir haben jedoch die Möglichkeit, die Sortierreihenfolge mithilfe der folgenden Syntax zu ändern.
std::set set_name;>
Beispiel:
C++
Vererbung 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;> }> |
>
>Ausgabe
12 10 5 4>
Zeitkomplexität: O(N) // N ist die Größe der Menge.
Palindrom in Java
Hilfsraum: AN)
Notiz: Wir können einen beliebigen Komparator anstelle eines größeren verwenden, um dem Satz eine benutzerdefinierte Sortierreihenfolge zu geben.
Eigenschaften
- Reihenfolge speichern – Das Set speichert die Elemente in sortiert Befehl.
- Werte Eigenschaften – Alle Elemente in einer Menge haben einzigartige Werte .
- Werte Natur – Der Wert des Elements kann nicht mehr geändert werden, sobald es zum Satz hinzugefügt wurde. Es ist jedoch möglich, den geänderten Wert dieses Elements zu entfernen und dann hinzuzufügen. Also die Werte Sind unveränderlich .
- Suchtechnik – Sätze folgen dem Binärer Suchbaum Implementierung.
- Ordnung schaffen – Die Werte in einer Menge sind nicht indiziert .
Notiz: Um die Elemente in unsortierter (zufälliger) Reihenfolge zu speichern, unordered_set() kann verwendet werden.
Einige mit Set verbundene Grundfunktionen
- beginnen() – Gibt einen Iterator zum ersten Element in der Menge zurück.
- Ende() – Gibt einen Iterator zum theoretischen Element zurück, das auf das letzte Element in der Menge folgt.
- Größe() – Gibt die Anzahl der Elemente in der Menge zurück.
- maximale Größe() – Gibt die maximale Anzahl von Elementen zurück, die die Menge enthalten kann.
- leer() – Gibt zurück, ob die Menge leer ist.
Die Zeitkomplexität für die Ausführung verschiedener Operationen an Mengen beträgt:
- Einfügen von Elementen – O(log N)
- Löschen von 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 leerenAusgabe
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>
Unterschiedliche Funktion von Set in C++ STL
| Funktion | Beschreibung |
|---|---|
| beginnen() | Gibt einen Iterator zum ersten Element in der Menge zurück. |
| Ende() | Gibt einen Iterator zum theoretischen Element zurück, das auf das letzte Element in der Menge folgt. |
| rbegin() | Gibt einen umgekehrten Iterator zurück, der auf das letzte Element im Container zeigt. |
| machen() | Gibt einen umgekehrten Iterator zurück, der auf das theoretische Element direkt vor dem ersten Element im Set-Container zeigt. |
| crbegin() | Gibt einen konstanten Iterator zurück, der auf das letzte Element im Container zeigt. |
| crend() | Gibt einen konstanten Iterator zurück, der auf die Position direkt vor dem ersten Element im Container zeigt. |
| cbegin() | Gibt einen konstanten Iterator zurück, der auf das erste Element im Container zeigt. |
| ein paar() | Gibt einen konstanten Iterator zurück, der auf die Position hinter dem letzten Element im Container zeigt. |
| Größe() | Gibt die Anzahl der Elemente in der Menge zurück. |
| maximale Größe() | Gibt die maximale Anzahl von Elementen zurück, die die Menge enthalten kann. |
| leer() | Gibt zurück, ob die Menge leer ist. |
| einfügen(const g) | Fügt der Menge ein neues Element „g“ hinzu. |
| Iterator-Einsatz (Iteratorposition, const g) | Fügt ein neues Element „g“ an der Position hinzu, auf die der Iterator zeigt. |
| löschen (Iteratorposition) | Entfernt das Element an der Position, auf die der Iterator zeigt. |
| löschen(const g) | Entfernt den Wert „g“ aus der Menge. |
| klar() | Entfernt alle Elemente aus der Menge. |
| key_comp() / value_comp() | Gibt das Objekt zurück, das bestimmt, wie die Elemente in der Menge angeordnet sind (standardmäßig „<“). |
| find(const g) | Gibt einen Iterator zum Element „g“ in der Menge zurück, falls gefunden, andernfalls wird der Iterator bis zum Ende zurückgegeben. |
| count(const g) | Gibt 1 oder 0 zurück, je nachdem, ob das Element „g“ in der Menge vorhanden ist oder nicht. |
| untere_Grenze(const g) | Gibt einen Iterator zum ersten Element zurück, das „g“ entspricht oder definitiv nicht vor dem Element „g“ in der Menge steht. |
| obere_Grenze(const g) | Gibt einen Iterator zum ersten Element zurück, das nach dem Element „g“ in der Menge folgt. |
| equal_range() | Die Funktion gibt einen Iterator von Paaren zurück. (key_comp). Das Paar bezieht sich auf den Bereich, der alle Elemente im Container umfasst, die ein Schlüsseläquivalent zu k haben. |
| emplace() | Mit dieser Funktion wird nur dann ein neues Element in den Set-Container eingefügt, wenn das einzufügende Element eindeutig ist und nicht bereits im Set vorhanden ist. |
| emplace_hint() | Gibt einen Iterator zurück, der auf die Position zeigt, an der die Einfügung erfolgt. Wenn das im Parameter übergebene Element bereits vorhanden ist, wird ein Iterator zurückgegeben, der auf die Position zeigt, an der sich das vorhandene Element befindet. |
| tauschen() | Diese Funktion wird verwendet, um den Inhalt zweier Sets auszutauschen. Die Sets müssen jedoch vom gleichen Typ sein, obwohl die Größen unterschiedlich sein können. |
| Operator= | „=“ ist ein Operator in C++ STL, der eine Menge in eine andere Menge kopiert (oder verschiebt), und set::operator= ist die entsprechende Operatorfunktion. |
| get_allocator() | Gibt die Kopie des Allokatorobjekts zurück, das der Menge zugeordnet ist. |
Unterschied zwischen Menge und ungeordneter Menge
| Satz | Ungeordneter Satz |
|---|---|
| Set speichert Elemente in sortierter Reihenfolge | Unordered Set speichert Elemente in unsortierter Reihenfolge |
| Legen Sie nur einzigartige Elemente fest bzw. erwerben Sie diese | Ungeordnete Mengen speichern/erfassen nur eindeutige Werte |
| Set verwendet für die Implementierung binäre Suchbäume | Unordered Set verwendet Hash-Tabellen zur Implementierung |
| Durch Angabe des Start- und Enditerators können mehr als ein Element gelöscht werden | Wir können das Element löschen, für das die Iteratorposition angegeben ist |
| set Set_Name; | unordered_set UnorderedSet_Name; |
Weitere Informationen finden Sie im Artikel – Mengen vs. ungeordnete Mengen .