C++:n standardikirjasto sisältää valmiita toteutuksia tutuista tietorakenteista, kuten Javan standardikirjasto. Saatavilla on joukkoja ja hakemistoja, jotka perustuvat puu- ja hajautusrakenteisiin.

C++:n rakenteiden nimet ja käyttötavat eroavat hieman Javasta, mutta periaate on sama. Erona on kuitenkin, että iteraattorit (jotka esitellään tässä tekstissä) ovat C++:ssa suuremmassa roolissa kuin Javassa.

Joukko

C++:n set-rakenne perustuu tasapainoiseen binäärihakupuuhun, ja sen operaatiot toimivat O(\log n)-ajassa.

Joukon käyttäminen vaatii, että koodin alussa on rivi #include <set>.

Seuraava koodi luo joukon, lisää siihen luvut 3, 7 ja 5 funktiolla insert ja hakee sitten alkioiden määrän funktiolla size.

set<int> s;
s.insert(3);
s.insert(7);
s.insert(5);
cout << s.size() << "\n"; // 3

Funktio count kertoo, onko joukossa tiettyä alkiota. Koska tietty alkio voi esiintyä vain kerran joukossa, funktio palauttaa aina 0 tai 1.

cout << s.count(5) << "\n"; // 1
cout << s.count(6) << "\n"; // 0

Funktio erase poistaa alkion joukosta:

s.insert(4);
cout << s.count(4) << "\n"; // 1
s.erase(4);
cout << s.count(4) << "\n"; // 0

Hakemisto

Hakemisto on taulukon yleistys, joka sisältää joukon avain-arvo-pareja. C++:n map-rakenne perustuu tasapainoiseen binäärihakupuuhun, ja sen operaatiot toimivat O(\log n)-ajassa.

Hakemiston käyttäminen vaatii, että koodin alussa on rivi #include <map>.

Esimerkiksi seuraava koodi luo hakemiston, jossa avaimet ovat merkkijonoja ja arvot ovat kokonaislukuja:

map<string,int> x;
x["apina"] = 1;
x["banaani"] = 2;
x["cembalo"] = 3;
cout << x["banaani"] << "\n"; // 2

Jos haettua avainta ei ole hakemistossa, sen oletusarvona on 0 tai tyhjä:

map<string,int> x;
cout << x["aybabtu"] << "\n"; // 0

Huomaa, että yllä oleva koodi myös lisää avaimen hakemistoon oletusarvolla.

Prioriteettijono

Prioriteettijonoon voi lisätä alkioita sekä hakea ja poistaa pienimmän tai suurimman alkion. C++:n priority_queue rakenne toteuttaa prioriteettijonon, jossa voi oletuksena hakea ja poistaa suurimman alkion.

Prioriteettijonon käyttäminen vaatii, että koodin alussa on rivi #include <queue>.

Seuraava koodi esittelee prioriteettijonon operaatioita:

priority_queue<int> q;
q.push(3);
q.push(7);
q.push(5);
cout << q.top() << "\n"; // 7
q.pop();
cout << q.top() << "\n"; // 5

Huomaa ero Javaan: Javassa prioriteettijono antaa oletuksena pienimmän alkion, mutta C++:ssä suurimman alkion.

Iteraattorit

Iteraattori on muuttuja, joka osoittaa tietorakenteen alkioon. Iteraattori begin osoittaa ensimmäiseen alkioon ja iteraattori end osoittaa viimeisen alkion jälkeiseen alkioon. Iteraattorin osoittamaan alkioon pääsee käsiksi *-merkinnällä, ja iteraattoria pystyy siirtämään operaatioilla ++ ja --.

Esimerkiksi seuraava koodi tulostaa kaikki joukon alkiot iteraattorin avulla. Koska joukko säilyttää järjestyksen, alkiot käydään läpi pienimmästä suurimpaan.

set<int> s = {2,3,5,7};
auto it = s.begin();
while (it != s.end()) {
    cout << *it << "\n";
    it++;
}

Tämä koodi tulostaa joukon pienimmän ja suurimman alkion:

set<int> s = {2,3,5,7};
auto it1 = s.begin();
auto it2 = s.end(); it2--;
cout << *it1 << " " << *it2 << "\n"; // 2 7

Funktio find antaa iteraattorin tiettyyn alkioon. Funktio lower_bound antaa iteraattorin pienimpään alkioon, joka on ainakin yhtä suuri kuin annettu alkio. Funktio upper_bound antaa iteraattorin pienimpään alkioon, joka on suurempi kuin annettu alkio. Jos alkiota ei ole olemassa, nämä funktiot antavat tuloksena iteraattorin end.

Seuraava koodi etsii iteraattoriin alkioon 5:

auto it = s.find(5);
if (it == s.end()) {
    // alkiota ei löytynyt
}

Seuraava koodi tulostaa pienimmän alkion, joka on ainakin yhtä suuri kuin 5, sekä pienimmän alkion, joka on suurempi kuin 5:

set<int> s = {2,3,5,7};
cout << *s.lower_bound(5) << "\n"; // 5
cout << *s.upper_bound(5) << "\n"; // 7

Toistot joukossa

Joukkoon set ei voi lisätä samaa alkiota monta kertaa:

set<int> s;
s.insert(5);
s.insert(5);
s.insert(5);
cout << s.count(5) << "\n"; // 1

Tämä on kuitenkin mahdollista joukossa multiset, joka on muuten kuin set, mutta sallii toistuvat alkiot:

multiset<int> s;
s.insert(5);
s.insert(5);
s.insert(5);
cout << s.count(5) << "\n"; // 3

Huomaa, että multiset-rakenteessa funktio count vie aikaa O(\log n + k), missä k on toistojen määrä.

Funktio erase poistaa alkion kaikki esiintymät joukosta:

multiset<int> s;
s.insert(5);
s.insert(5);
s.insert(5);
cout << s.count(5); << "\n"; // 3
s.erase(5);
cout << s.count(5); << "\n"; // 0

Vain yhden esiintymän pystyy kuitenkin poistamaan näin:

multiset<int> s;
s.insert(5);
s.insert(5);
s.insert(5);
cout << s.count(5); << "\n"; // 3
s.erase(s.find(5));
cout << s.count(5); << "\n"; // 2

Tällöin poistettavaksi annetaan alkion asemesta iteraattori alkioon.

Parit joukossa

Joskus on kätevää luoda joukko, jonka alkiot ovat pareja. Esimerkiksi seuraava koodi tekee näin:

set<pair<int,int>> s;
s.insert({3,5});
s.insert({6,1});
s.insert({3,4});

Tällöin parit ovat järjestyksessä joukossa ensisijaisesti ensimmäisen jäsenen ja toissijaisesti toisen jäsenen mukaan:

auto it = s.lower_bound({4,2});
cout << it->first << " " << it->second << "\n"; // 6 1

Hajautusrakenteet

C++ sisältää tasapainoiseen binäärihakupuuhun perustuvien rakenteiden rinnalla vastaavat hajautustauluun perustuvat rakenteet. Niissä on etuliitteenä unordered ja operaatiot vievät aikaa (yleensä) O(1).

Esimerkiksi seuraava koodi luo hajautustauluun perustuvan joukon:

unordered_set<int> s;
s.insert(3);
s.insert(7);
s.insert(5);

Hajautustauluun perustuvat rakenteet ovat usein hieman nopeampia kuin binäärihakupuuhun perustuvat rakenteet. Niissä ei voi kuitenkaan käyttää funktioita, jotka vaativat alkioiden järjestystä (kuten lower_bound ja upper_bound).