set en multiset
De klasse std::set<T> en std::multiset<T> in <set>
zijn STL-implementaties van verzamelingen (Eng. sets).
Deze implementaties zijn gebaseerd op een efficiënte binaire zoekboom (rood-zwarte boom of AVL-boom).
Hierdoor hebben de meeste operaties logaritmische performantie.
In een set is ieder element uniek, in een multiset kunnen duplicaten voorkomen.
Je kunt een element toevoegen via de methode insert(x) waarbij x uiteraard van het type T is.
Deze methode is O(log N).
Aangezien de implementatie steunt op een binaire zoekboom moeten er een ordening voor de elementen gedefinieerd zijn.
Standaard wordt hiervoor operator< gebruikt, maar er kan ook een ander criterium worden opgegeven via een optionele tweede template-parameter.
[voorbeeld: zie priority_queue]
Het overlopen van elementen gebeurt aan de hand van iteratoren (indexering via operator[] is niet gedefinieerd).
Zoals elders in de STL geeft de methode begin() een iterator naar het eerste element, en end()
een iterator voorbij het laatste element. Zoals andere containerklassen definiëren set
en multiset een intern type iterator en const_iterator.
Dereferentie (*) en opschuiven (++) van een iterator gebeurt geamortizeerd in O(1).
Een voorbeeld:
set<int> verz; verz.insert(20); verz.insert(10); verz.insert(15); cout << verz[0]; // FOUT, niet gedefinieerd for (set<int>::const_iterator it = verz.begin(); it != verz.end(); ++it) cout << *it << endl;
Vreemd genoeg is er geen methode contains(x) voorzien! Er zijn twee alternatieven om (in O(log N)) na te gaan of een element in de collectie voorkomt:
count(x) geeft het aantal keer dat x voorkomt. Bij een set is dit 0 of 1, bij een multiset kan het meer dan 1 zijn.
find(x) geeft een iterator terug naar het (eerste) element dat gelijk is aan x. Indien x
niet voorkomt is de geretourneerde iterator gelijk aan end().
Je kunt een element wissen via erase(x) (O(log N)) of via erase(it) (O(1)).
Dit laatste is vooral handig in combinatie met find():
set<int>::iterator it = verz.find(x); if (it != verz.end()) verz.erase(it);
Er zijn verder nog interessante methodes voor het toevoegen en verwijderen van reeksen van elementen, voor het zoeken van onder- en bovengrenzen etc.
Volgende algoritmen, gedefinieerd in <algorithm>, zijn bijzonder handig in combinatie met sets:
set_intersection: doorsnede
set_union : unie
set_difference: verschil
includes: deelverzameling
set<int> v1, v2; for (int i=0; i<10; i++) v1.insert(i*i); for (int i=0; i<50; i++) v2.insert(2*i-1); set_intersection(v1.begin(), v1.end(), v2.begin(), v2.end(), ostream_iterator<int>(cout, " "));schrijft "1 9 25 49 81" uit.
std::map en std::multimap
De klasse std::map<S, T> in <map>
implementeert een afbeelding (Eng. mapping) of woordenboek (Eng. dictionary)
van sleutels (type S) naar waarden (type T).
Men spreekt van een associatieve container.
Een map<S, T> komt in grote lijnen overeen met een set<pair<S,T> >: elementen zijn paren waarvan het eerste deel (first) de sleutel is, en het tweede deel (second) de overeenkomstige waarde.
Dit zie je duidelijk bij de iterator:
typedef map<int, double> IDMap;
void write(const IDMap &m) {
for (IDMap::const_iterator it=m.begin(); it!=m.end(); ++it)
cout << it->first << " -> " << it->second << endl;
}
waarbij it->first uiteraard gelijk is aan (*it).first en analoog voor second.
Doordat de onderliggende representatie een binaire zoekboom is, zijn de iterator-waarden gesorteerd
op sleutel, default van klein naar groot. de operator< voor pairs kijkt immers
(eerst) naar het eerste deel (first). Zoals bij set kun je de ordening opgeven
d.m.v. een comparator.
Het opzoeken van de waarde voor een gegeven sleutel s kan via find(s).
Dit geeft een iterator terug, wijzend naar een pair waarvan het tweede deel de gezochte waarde is.
Ook het toevoegen van een sleutel-waarde-paar gebeurt met pair:
IDMap m; m.insert(make_pair(10, 3.14)); //... IDMap::iterator it = m.find(10); if (it == m.end()) cout << "niet gevonden" << endl; else cout << "waarde: " << it->second << endl;
Merk op dat insert(s,w) geen effect heeft indien er al een sleutel s voorkomt, ongeacht de waarde w! Indien je de waarde wil wijzigen moet dit via de iterator:
void force_insert(IDMap &m, int s, double w) {
IDMap::iterator it = m.find(s);
if (it == m.end())
m.insert(it, make_pair(s, w)); // eerste arg. is hint -> O(1) toevoegen
else
it->second = w;
}
Voor het "gemak" wordt de operator[] in map overladen, zodat je kunt schrijven:
IDMap m; m[10] = 3.14; cout << m[10] << endl;Dit ziet er uit als een tabel of vector, maar de container bevat hier slecht één element. Je kunt ook niet-gehele indices gebruiken:
map<string, int> leeftijd; leeftijd["jan"]=12; cout << leeftijd["jan"] << endl;In tegenstelling tot
insert kan operator[] wel een waarde vervangen:
m[10] = 1.0; m[10] = 2.0; // ok
Opgelet: er zit een addertje onder het gras: indien een sleutel niet in de collectie zit, zal de operator[]
die toevoegen (met default waarde),zelfs in het rechterlid van een uitdrukking:
int l = leeftijd["piet"]; // !! GEVAAR !!voegt de mapping "piet"→0 toe (en
l krijgt de waarde nul)! Typische fout:
if (leeftijd[s]==0) doe_iets(); // !! GEVAAR !!Indien sleutel
s niet voorkwam in de collectie wordt hij toegevoegd met waarde nul, zodat de if
voorwaarde voldaan is en doet_iets opgeroepen wordt.
Omdat operator[] dit "neveneffect" kan hebben, is hij niet const. Dat betekent dat je geen vierkante haakjes kunt gebruiken op een const-map:
void foo(const map<string, int> &leeftijd) {
cout << leeftijd["jan"] << endl; // MAG NIET, zelfs indien "jan" in de container zit!
}
Opmerking over de terminologie: zoals alle containertypes definieert map interne types voor elementen, iteratoren etc.
Let wel dat value_type staat voor pair<S, T>, terwijl key_type voor S
staat en data_type voor T. Ook in de documentatie gebruikt men de term waarde voor elementen,
en de term data voor "waarden" (van sleutels).
multimap
Een std::multimap<S, T> is een mapping van sleutels S naar waarden T
waarbij duplicaten mogen voorkomen (zowel qua sleutels als qua waarden). Bv.
multimap<int, char> mm; mm.insert(make_pair(10, 'a')); mm.insert(make_pair(10, 'a')); mm.insert(make_pair(10, 'b'));maakt een multimap met drie elementen.
De operator[] is hier niet gedefinieerd!
Vreemd genoeg maakten hash-structuren oorspronkelijk geen deel uit van de STL. Ze zijn later toegevoegd. Het gebruik ervan verschilt lichtjes van compiler tot compiler: zie praktische uitleg.
In <hash_set> vind je hash_set<T> en hash_multiset<T>.
In <hash_map> vind je hash_map<T> en hash_multimap<T>.
De interfaces zijn grotendeels gelijk aan de overeenkomstige niet-hash-containers.
In hash-containers kan men in principe elementen opzoeken in O(1), op voorwaarde dat de hash-functie voldoende kwalitatief is.
Let wel dat elementen/sleutels niet geordend zijn: een iterator overloopt alle elementen in willekeurige volgorde.
De operator< moet dan ook niet gedefinieerd zijn.
In principe kun je de te gebruiken hash-functie opgeven, maar hierin volgen compilers niet altijd de standaard (met name in Visual C++ is het mechanisme afwijkend).
[W. Schepens okt. 2008]