Code Submission Evaluation System Login

Algoritmit ongelmanratkaisussa 2019


Tasks | Statistics


CSES - Vektori ja järjestäminen

Vektori ja järjestäminen


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).