C++
std :: set und std :: multiset
Suche…
Einführung
set ist ein Typ von Container, dessen Elemente sortiert und eindeutig sind. multiset ist ähnlich, aber bei multiset können mehrere Elemente denselben Wert haben.
Bemerkungen
In diesen Beispielen wurden verschiedene C ++ - Stile verwendet. Seien Sie vorsichtig, wenn Sie einen C ++ 98-Compiler verwenden. Ein Teil dieses Codes ist möglicherweise nicht verwendbar.
Werte in einen Satz einfügen
Drei verschiedene Einfügemethoden können mit Sets verwendet werden.
- Zuerst eine einfache Einfügung des Wertes. Diese Methode gibt ein Paar zurück, mit dem der Aufrufer prüfen kann, ob die Einfügung tatsächlich erfolgt ist.
- Zweitens eine Einfügung, indem ein Hinweis gegeben wird, wo der Wert eingefügt wird. Das Ziel besteht darin, die Einfügungszeit in einem solchen Fall zu optimieren, aber zu wissen, wo ein Wert eingefügt werden sollte, ist nicht üblich. Seien Sie in diesem Fall vorsichtig. Die Art, einen Hinweis zu geben, unterscheidet sich von Compiler-Versionen .
- Schließlich können Sie einen Wertebereich einfügen, indem Sie einen Start- und einen Endzeiger angeben. Die Startnummer wird in die Einfügung aufgenommen, die Endung wird ausgeschlossen.
#include <iostream>
#include <set>
int main ()
{
std::set<int> sut;
std::set<int>::iterator it;
std::pair<std::set<int>::iterator,bool> ret;
// Basic insert
sut.insert(7);
sut.insert(5);
sut.insert(12);
ret = sut.insert(23);
if (ret.second==true)
std::cout << "# 23 has been inserted!" << std::endl;
ret = sut.insert(23); // since it's a set and 23 is already present in it, this insert should fail
if (ret.second==false)
std::cout << "# 23 already present in set!" << std::endl;
// Insert with hint for optimization
it = sut.end();
// This case is optimized for C++11 and above
// For earlier version, point to the element preceding your insertion
sut.insert(it, 30);
// inserting a range of values
std::set<int> sut2;
sut2.insert(20);
sut2.insert(30);
sut2.insert(45);
std::set<int>::iterator itStart = sut2.begin();
std::set<int>::iterator itEnd = sut2.end();
sut.insert (itStart, itEnd); // second iterator is excluded from insertion
std::cout << std::endl << "Set under test contains:" << std::endl;
for (it = sut.begin(); it != sut.end(); ++it)
{
std::cout << *it << std::endl;
}
return 0;
}
Ausgabe wird sein:
# 23 has been inserted!
# 23 already present in set!
Set under test contains:
5
7
12
20
23
30
45
Werte in ein Multiset einfügen
Alle Einfügemethoden aus Sets gelten auch für Multisets. Es besteht jedoch eine weitere Möglichkeit, die eine initializer_list bereitstellt:
auto il = { 7, 5, 12 };
std::multiset<int> msut;
msut.insert(il);
Ändern der Standardart einer Gruppe
set und multiset verfügen über Standardvergleichsmethoden, in einigen Fällen müssen Sie sie jedoch überladen.
Stellen wir uns vor, wir speichern String-Werte in einer Menge, aber wir wissen, dass diese Strings nur numerische Werte enthalten. Standardmäßig handelt es sich bei der Sortierung um einen lexikographischen Stringvergleich, sodass die Sortierung nicht mit der numerischen Sortierung übereinstimmt. Wenn Sie eine Sortierung verwenden möchten, die dem entspricht, was Sie mit int Werten hätten, benötigen Sie einen Functor, um die Compare-Methode zu überladen:
#include <iostream>
#include <set>
#include <stdlib.h>
struct custom_compare final
{
bool operator() (const std::string& left, const std::string& right) const
{
int nLeft = atoi(left.c_str());
int nRight = atoi(right.c_str());
return nLeft < nRight;
}
};
int main ()
{
std::set<std::string> sut({"1", "2", "5", "23", "6", "290"});
std::cout << "### Default sort on std::set<std::string> :" << std::endl;
for (auto &&data: sut)
std::cout << data << std::endl;
std::set<std::string, custom_compare> sut_custom({"1", "2", "5", "23", "6", "290"},
custom_compare{}); //< Compare object optional as its default constructible.
std::cout << std::endl << "### Custom sort on set :" << std::endl;
for (auto &&data : sut_custom)
std::cout << data << std::endl;
auto compare_via_lambda = [](auto &&lhs, auto &&rhs){ return lhs > rhs; };
using set_via_lambda = std::set<std::string, decltype(compare_via_lambda)>;
set_via_lambda sut_reverse_via_lambda({"1", "2", "5", "23", "6", "290"},
compare_via_lambda);
std::cout << std::endl << "### Lambda sort on set :" << std::endl;
for (auto &&data : sut_reverse_via_lambda)
std::cout << data << std::endl;
return 0;
}
Ausgabe wird sein:
### Default sort on std::set<std::string> :
1
2
23
290
5
6
### Custom sort on set :
1
2
5
6
23
290
### Lambda sort on set :
6
5
290
23
2
1
Im obigen Beispiel gibt es drei verschiedene Möglichkeiten, Vergleichsoperationen zum std::set hinzuzufügen. Jede davon ist in ihrem eigenen Kontext nützlich.
Standardsortierung
Der Vergleichsoperator des Schlüssels wird verwendet (erstes Vorlagenargument). Häufig bietet der Schlüssel bereits einen guten Standard für die Funktion std::less<T> . Wenn diese Funktion nicht spezialisiert ist, verwendet sie den operator< des Objekts. Dies ist besonders nützlich, wenn auch anderer Code versucht, eine bestimmte Reihenfolge zu verwenden, da dies die Konsistenz über die gesamte Codebasis ermöglicht.
Wenn Sie den Code auf diese Weise schreiben, verringert sich der Aufwand für die Aktualisierung Ihres Codes, wenn der Schlüssel die API ändert, z. B. eine Klasse mit 2 Mitgliedern, die in eine Klasse mit 3 Mitgliedern geändert wird. Durch das Aktualisieren des operator< in der Klasse werden alle Vorkommen aktualisiert.
Wie zu erwarten, ist die Verwendung der Standardsortierung eine sinnvolle Standardeinstellung.
Benutzerdefinierte Sortierung
Das Hinzufügen einer benutzerdefinierten Sortierung über ein Objekt mit einem Vergleichsoperator wird häufig verwendet, wenn der Standardvergleich nicht entspricht. Im obigen Beispiel liegt dies daran, dass sich die Zeichenfolgen auf Ganzzahlen beziehen. In anderen Fällen wird es häufig verwendet, wenn Sie (intelligente) Zeiger basierend auf dem Objekt, auf das sie sich beziehen, vergleichen möchten oder weil Sie zum Vergleichen unterschiedliche Einschränkungen benötigen (Beispiel: Vergleich von std::pair mit dem Wert von first ).
Beim Erstellen eines Vergleichsoperators sollte dies eine stabile Sortierung sein. Wenn sich das Ergebnis des Vergleichsoperators nach dem Einfügen ändert, haben Sie undefiniertes Verhalten. In der Regel sollte Ihr Vergleichsoperator nur die konstanten Daten (const-Member, const-Funktionen ...) verwenden.
Wie im obigen Beispiel werden Sie Klassen ohne Mitglieder häufig als Vergleichsoperatoren begegnen. Dies führt zu Standardkonstruktoren und Kopierkonstruktoren. Mit dem Standardkonstruktor können Sie die Instanz zur Konstruktionszeit weglassen, und der Kopierkonstruktor ist erforderlich, da der Satz eine Kopie des Vergleichsoperators übernimmt.
Lambda Art
Lambdas sind eine kürzere Möglichkeit, Funktionsobjekte zu schreiben. Dies ermöglicht das Schreiben des Vergleichsoperators in weniger Zeilen, wodurch der gesamte Code lesbarer wird.
Der Nachteil der Verwendung von Lambdas besteht darin, dass jedes Lambda zur Kompilierzeit einen bestimmten Typ erhält, sodass der decltype(lambda) bei jeder Kompilierung derselben Kompilierungseinheit (cpp-Datei) anders ist als bei mehreren Kompilierungseinheiten (wenn sie über eine Headerdatei eingefügt werden) ). Aus diesem Grund wird empfohlen, Funktionsobjekte als Vergleichsoperator zu verwenden, wenn sie in Header-Dateien verwendet werden.
Diese Konstruktion wird häufig angetroffen, wenn stattdessen ein std::set im lokalen Gültigkeitsbereich einer Funktion verwendet wird, während das Funktionsobjekt bevorzugt wird, wenn es als Funktionsargument oder Klassenmitglied verwendet wird.
Andere Sortieroptionen
Da der Vergleichsoperator von std::set ein Vorlagenargument ist, können alle aufrufbaren Objekte als Vergleichsoperator verwendet werden, und die obigen Beispiele sind nur Sonderfälle. Die einzigen Einschränkungen, die diese aufrufbaren Objekte haben, sind:
- Sie müssen kopierfähig sein
- Sie müssen mit 2 Argumenten des Schlüsseltyps aufrufbar sein. (Implizite Konvertierungen sind zulässig, werden jedoch nicht empfohlen, da dies die Leistung beeinträchtigen kann.)
Suche nach Werten in Set und Multiset
Es gibt mehrere Möglichkeiten, einen bestimmten Wert in std::set oder in std::multiset zu suchen:
Um den Iterator des ersten Vorkommens eines Schlüssels zu erhalten, kann die Funktion find() verwendet werden. Es gibt end() wenn der Schlüssel nicht vorhanden ist.
std::set<int> sut;
sut.insert(10);
sut.insert(15);
sut.insert(22);
sut.insert(3); // contains 3, 10, 15, 22
auto itS = sut.find(10); // the value is found, so *itS == 10
itS = sut.find(555); // the value is not found, so itS == sut.end()
std::multiset<int> msut;
sut.insert(10);
sut.insert(15);
sut.insert(22);
sut.insert(15);
sut.insert(3); // contains 3, 10, 15, 15, 22
auto itMS = msut.find(10);
Ein anderer Weg wird mit der count() Funktion, die zählt , wie viele entsprechenden Werte in dem festgestellt worden set / multiset (im Fall eines set , der Rückgabewert 0 sein kann nur oder 1). Mit den gleichen Werten wie oben werden wir haben:
int result = sut.count(10); // result == 1
result = sut.count(555); // result == 0
result = msut.count(10); // result == 1
result = msut.count(15); // result == 2
Im Fall von std::multiset könnten mehrere Elemente den gleichen Wert haben. Um diesen Bereich zu erhalten, kann die Funktion equal_range() verwendet werden. Es gibt std::pair , das die untere Schranke des Iterators (einschließlich) und die obere Schranke (exklusiv) aufweist. Wenn der Schlüssel nicht vorhanden ist, zeigen beide Iteratoren auf den nächsten übergeordneten Wert (basierend auf der zum Sortieren des angegebenen multiset verwendeten Vergleichsmethode).
auto eqr = msut.equal_range(15);
auto st = eqr.first; // point to first element '15'
auto en = eqr.second; // point to element '22'
eqr = msut.equal_range(9); // both eqr.first and eqr.second point to element '10'
Werte aus einem Satz löschen
Die naheliegendste Methode, wenn Sie nur Ihr Set / Multiset auf ein leeres zurücksetzen möchten, ist clear :
std::set<int> sut;
sut.insert(10);
sut.insert(15);
sut.insert(22);
sut.insert(3);
sut.clear(); //size of sut is 0
Dann kann die erase verwendet werden. Es bietet einige Möglichkeiten, die der Einfügung etwas ähneln:
std::set<int> sut;
std::set<int>::iterator it;
sut.insert(10);
sut.insert(15);
sut.insert(22);
sut.insert(3);
sut.insert(30);
sut.insert(33);
sut.insert(45);
// Basic deletion
sut.erase(3);
// Using iterator
it = sut.find(22);
sut.erase(it);
// Deleting a range of values
it = sut.find(33);
sut.erase(it, sut.end());
std::cout << std::endl << "Set under test contains:" << std::endl;
for (it = sut.begin(); it != sut.end(); ++it)
{
std::cout << *it << std::endl;
}
Ausgabe wird sein:
Set under test contains:
10
15
30
Alle diese Methoden gelten auch für multiset . Wenn Sie ein Element aus einem multiset löschen multiset und dieses mehrmals vorhanden ist, werden alle entsprechenden Werte gelöscht .