C++:n standardikirjasto sisältää suuren määrän valmiita tietorakenteita ja algoritmeja. Näistä usein tarvittavia ovat vector
(muuttuvan kokoinen taulukko) sekä sort
(tehokas järjestäminen).
C++11-standardi
Oletamme jatkossa, että käytössä C++11-standardi, jossa on hyödyllisiä lisäyksiä aiempaan standardiin. Koodin voi kääntää näin C++11-standardin mukaisesti:
g++ -std=c++11 koodi.cpp -o koodi -O2
Vektorin luominen
Vektorin käyttäminen vaatii, että koodin alussa on seuraava rivi:
#include <vector>
Seuraava koodi luo vektorin v
, jonka alkiot ovat int
-lukuja, ja lisää siihen kolme alkiota:
vector<int> v; v.push_back(1); v.push_back(2); v.push_back(3);
Vektorin voi myös luoda antamalla suoraan sen sisällön:
vector<int> v = {1,2,3};
Funktio size
kertoo, montako alkiota vektorissa on:
cout << v.size() << "\n"; // 3
Vektori taulukkona
Vektoria voi käyttää samalla syntaksilla kuin taulukkoa. Esimerkiksi seuraava koodi muuttaa vektorin ensimmäistä alkiota:
vector<int> v = {1,2,3}; cout << v[0] << "\n"; // 1 v[0] = 5; cout << v[0] << "\n"; // 5
Javassa ArrayList
on selvästi hitaampi kuin taulukko. C++:ssa sen sijaan vector
on lähes yhtä nopea kuin taulukko. Voit siis käyttää vektoria huoletta, vaikka olisi paljon tietoa.
Vektorin läpikäynti
Vektorin alkiot voi tulostaa for-silmukalla näin:
vector<int> v = {1,2,3}; for (int i = 0; i < v.size(); i++) { cout << v[i] << " "; } cout << "\n"; // tulostus: 1 2 3
Vastaavan koodin voi toteuttaa myös näin lyhyemmin:
vector<int> v = {1,2,3}; for (auto x : v) { cout << x << " "; } cout << "\n"; // tulostus: 1 2 3
Javassa tietorakenteen sisällön voi tulostaa suoraan antamalla sen tulostusmetodille, koska tietorakenteissa on valmiit toString
-metodit. C++:ssa näin ei ole, vaan tulostaminen on hankalampaa.
Järjestäminen
Järjestämisen käyttäminen vaatii, että koodin alussa on seuraava rivi:
#include <algorithm>
Seuraava koodi luo vektorin ja järjestää sitten sen sisällön:
vector<int> v = {4,2,5,1,3}; sort(v.begin(),v.end()); // v = {1,2,3,4,5}
Tässä funktiot begin
ja end
viittaavat vektorin alkuun ja loppuun. Järjestyksen saa käänteiseksi näin:
vector<int> v = {4,2,5,1,3}; sort(v.rbegin(),v.rend()); // v = {5,4,3,2,1}
Myös merkkijonon voi järjestää vastaavalla tavalla:
string s = "apina"; sort(s.begin(),s.end()); // s = "aainp"
Parit
Parin avulla voi tallentaa kaksi tietoa yhtenä alkiona. Esimerkiksi seuraava koodi luo vektorin, jossa on pareja:
vector<pair<int,string>> v; v.push_back({1,"apina"}); v.push_back({2,"banaani"}); v.push_back({3,"cembalo"});
Tässä tapauksessa parin ensimmäinen jäsen on int
-luku ja toinen jäsen on merkkijono. Parin jäseniä voi käsitellä kenttien first
ja second
avulla:
cout << v[0].first << "\n"; // 1 cout << v[0].second << "\n"; // apina
Kun vektorissa on pareja, ne järjestyvät ensisijaisesti ensimmäisen jäsenen mukaan ja toissijaisesti toisen jäsenen mukaan. Seuraava esimerkki esittelee tätä:
vector<pair<int,int>> v; v.push_back({3,5}); v.push_back({2,8}); v.push_back({3,2}); sort(v.begin(),v.end()); // v = {{2,8},{3,2},{3,5}}
Kopioiminen
Tärkeä ero Javan ja C++:n välillä on, että Javassa tietorakenteen sijoitus kopioi vain viitteen mutta C++:ssa se kopioi sisällön. Seuraava koodi esittelee tätä:
vector<int> a, b; a.push_back(1); a.push_back(2); a.push_back(3); b = a; b[0] = 5; // a = {1,2,3}, b = {5,2,3}
Koska sijoitus kopioi sisällön, vektorin b
ensimmäisen alkion muuttaminen ei vaikuta vektoriin a
vaan tietorakenteet ovat erilliset.
C++:n tapa on siinä mielessä intuitiivinen, että alkeistyyppien (esim. int
) ja tietorakenteiden sijoitus toimii samalla tavalla (aina kopioidaan).