C++
std :: set en std :: multiset
Zoeken…
Invoering
set is een type container waarvan de elementen zijn gesorteerd en uniek. multiset is vergelijkbaar, maar in het geval van multiset kunnen meerdere elementen dezelfde waarde hebben.
Opmerkingen
Verschillende stijlen van C ++ zijn in die voorbeelden gebruikt. Let op dat als u een C ++ 98-compiler gebruikt; een deel van deze code is mogelijk niet bruikbaar.
Waarden in een set invoegen
Drie verschillende invoegmethoden kunnen worden gebruikt met sets.
- Eerst een eenvoudige invoeging van de waarde. Met deze methode wordt een paar geretourneerd waarmee de beller kan controleren of de invoeging echt heeft plaatsgevonden.
- Ten tweede, een invoeging door een hint te geven van waar de waarde zal worden ingevoegd. Het doel is om de invoegtijd in een dergelijk geval te optimaliseren, maar het is niet gebruikelijk om te weten waar een waarde moet worden ingevoegd. Wees in dat geval voorzichtig; de manier om een hint te geven verschilt met compilerversies .
- Eindelijk kunt u een reeks waarden invoegen door een begin- en een eindwijzer te geven. De eerste wordt opgenomen in de invoeging, de laatste wordt uitgesloten.
#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;
}
Uitgang zal zijn:
# 23 has been inserted!
# 23 already present in set!
Set under test contains:
5
7
12
20
23
30
45
Waarden invoegen in een multiset
Alle invoegmethoden uit sets zijn ook van toepassing op multisets. Niettemin bestaat er een andere mogelijkheid, die een initialisatielijst biedt:
auto il = { 7, 5, 12 };
std::multiset<int> msut;
msut.insert(il);
De standaardsoort van een set wijzigen
set en multiset hebben standaard vergelijkingsmethoden, maar in sommige gevallen moet u ze wellicht overbelasten.
Stel dat we tekenreekswaarden in een set opslaan, maar we weten dat die tekenreeksen alleen numerieke waarden bevatten. Standaard is de sortering een lexicografische stringvergelijking, zodat de volgorde niet overeenkomt met de numerieke sortering. Als u een soort wilt toepassen dat equivalent is aan wat u zou hebben met int waarden, hebt u een functor nodig om de vergelijkingsmethode te overbelasten:
#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;
}
Uitgang zal zijn:
### 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
In het bovenstaande voorbeeld kan men 3 verschillende manieren vinden om vergelijkingsbewerkingen toe te voegen aan de std::set , elk van hen is nuttig in zijn eigen context.
Standaard sortering
Dit zal de vergelijkingsoperator van de sleutel gebruiken (eerste sjabloonargument). Vaak biedt de sleutel al een goede standaard voor de functie std::less<T> . Tenzij deze functie gespecialiseerd is, gebruikt deze de operator< van het object. Dit is vooral handig wanneer andere code ook wat ordening probeert te gebruiken, omdat dit consistentie over de hele codebasis mogelijk maakt.
Als u de code op deze manier schrijft, vermindert u de moeite om uw code bij te werken wanneer de sleutel verandert API is, zoals: een klasse met 2 leden die verandert in een klasse met 3 leden. Door de operator< in de klasse bij te werken, worden alle gebeurtenissen bijgewerkt.
Zoals je zou verwachten, is het gebruik van de standaardsoort een redelijke standaard.
Aangepast sorteren
Het toevoegen van een aangepaste sortering via een object met een vergelijkingsoperator wordt vaak gebruikt wanneer de standaardvergelijking niet voldoet. In het bovenstaande voorbeeld is dit omdat de tekenreeksen verwijzen naar gehele getallen. In andere gevallen wordt het vaak gebruikt wanneer u (slimme) pointers wilt vergelijken op basis van het object waarnaar ze verwijzen of omdat u verschillende beperkingen nodig hebt om te vergelijken (bijvoorbeeld: std::pair vergelijken met de waarde van first ).
Bij het maken van een vergelijkingsoperator moet dit een stabiele sortering zijn. Als het resultaat van de vergelijkingsoperator na het invoegen verandert, zult u ongedefinieerd gedrag vertonen. Als een goede praktijk moet uw vergelijkingsoperator alleen de constante gegevens gebruiken (const-leden, const-functies ...).
Net als in het bovenstaande voorbeeld zul je vaak klassen zonder leden tegenkomen als vergelijkingsoperatoren. Dit resulteert in standaardconstructors en kopieerconstructors. Met de standaardconstructor kunt u de instantie tijdens de constructie weglaten en is de kopieconstructor vereist omdat de set een kopie van de vergelijkingsoperator neemt.
Lambda soort
Lambdas zijn een kortere manier om functieobjecten te schrijven. Hierdoor kan de vergelijkingsoperator op minder regels worden geschreven, waardoor de algehele code leesbaarder wordt.
Het nadeel van het gebruik van lambdas is dat elke lambda tijdens het compileren een specifiek type krijgt, dus decltype(lambda) zal voor elke compilatie van dezelfde compilatie-eenheid (cpp-bestand) anders zijn dan voor meerdere compilatie-eenheden (indien opgenomen via header-bestand) ). Om deze reden wordt aanbevolen om functieobjecten te gebruiken als vergelijkingsoperator bij gebruik in header-bestanden.
Deze constructie wordt vaak aangetroffen wanneer in plaats daarvan een std::set wordt gebruikt binnen het lokale bereik van een functie, terwijl het functieobject de voorkeur heeft als het wordt gebruikt als functieargumenten of klasseleden.
Andere sorteeropties
Aangezien de vergelijk-operator van std::set een sjabloonargument is, kunnen alle opvraagbare objecten worden gebruikt als vergelijk-operator en de bovenstaande voorbeelden zijn slechts specifieke gevallen. De enige beperkingen voor deze opvraagbare objecten zijn:
- Ze moeten kopieerbaar zijn
- Ze moeten opvraagbaar zijn met 2 argumenten van het type sleutel. (impliciete conversies zijn toegestaan, maar worden niet aanbevolen omdat dit de prestaties kan schaden)
Waarden zoeken in set en multiset
Er zijn verschillende manieren om een bepaalde waarde te zoeken in std::set of in std::multiset :
Om de iterator te krijgen van de eerste keer dat een sleutel voorkomt, kan de functie find() worden gebruikt. Retourneert end() als de sleutel niet bestaat.
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);
Een andere manier is het gebruik van de functie count() , die telt hoeveel overeenkomstige waarden zijn gevonden in de set / multiset (in het geval van een set kan de retourwaarde slechts 0 of 1 zijn). Met dezelfde waarden als hierboven hebben we:
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
In het geval van std::multiset kunnen er verschillende elementen zijn met dezelfde waarde. Om dit bereik te krijgen, kan de functie equal_range() worden gebruikt. Het retourneert respectievelijk std::pair met iterator ondergrens (inclusief) en bovengrens (exclusief). Als de sleutel niet bestaat, verwijzen beide iterators naar de dichtstbijzijnde superieure waarde (gebaseerd op de vergelijkingsmethode die is gebruikt om de opgegeven multiset te sorteren).
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'
Waarden uit een set verwijderen
De meest voor de hand liggende methode, als u gewoon uw set / multiset wilt resetten naar een lege, is het gebruik van clear :
std::set<int> sut;
sut.insert(10);
sut.insert(15);
sut.insert(22);
sut.insert(3);
sut.clear(); //size of sut is 0
Dan kan de erase worden gebruikt. Het biedt enkele mogelijkheden die enigszins vergelijkbaar zijn met de invoeging:
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;
}
Uitgang zal zijn:
Set under test contains:
10
15
30
Al die methoden zijn ook van toepassing op multiset . Let op: als u vraagt om een element uit een multiset te verwijderen en het is meerdere keren aanwezig, worden alle equivalente waarden verwijderd .