====== 3. Standardní knihovna C++ ======

Ve cvičení se seznámíme se zástupci sekvenčních a asociativních kontejnerů. 

Vzorové příklady najdete buď v repozitáři v adresáři [[https://gitlab.fel.cvut.cz/viteks/ppc/-/tree/master/tutorials/tut04|tut04]].

===== Sekvenční kontejner =====

Typickým zástupcem sekvenčního kontejneru je [[http://www.cplusplus.com/reference/vector/vector/|std::vector]], který je flexibilní náhradou pole. V následujícím příkladu vytvoříme tři vektory: ''A'' bude inicializován na velikost 10 prvků typu ''int'', vektor ''B'' nulové velikosti bude připraven na ukládání prvků datového typu ''float'' a konečně vektor ''C'' bude inicializován třema znaky. 

<code cpp>
std::vector<int> A(10);
std::vector<float> B;
std::vector<char> C {'a', 'b', 'c'};
</code>

Velikost jednotlivých vektorů můžeme ověřit např. pomocí členské metody [[http://www.cplusplus.com/reference/vector/vector/size/|size]].

<code cpp>
std::cout << A.size << std::endl;
</code>

Výsledek si nebude žádným překvapením, stejně jako u ostatních vektorů. S velikostí vektoru lze ovšem různě pracovat. Kromě automatické realokace při použítím funkce [[http://www.cplusplus.com/reference/vector/vector/push_back/|push_back]] (viz níže), lze pro přímou realokaci využít metodu [[http://www.cplusplus.com/reference/vector/vector/resize/|resize]], nebo využít metodu [[http://www.cplusplus.com/reference/vector/vector/reserve/|reserve]] pro vyhrazení prostoru v paměti pro budoucí realokaci - realokace v rezervované paměti by měla být rychlejší, počet prvků rezervované paměti vrátí metoda [[http://www.cplusplus.com/reference/vector/vector/capacity/|capacity]]. A konečně, pokud by bylo z hlediska aplikace důležité, kolik na prvků daného typu lze kontejner zvětšit, poslouží metoda [[http://www.cplusplus.com/reference/vector/vector/max_size/|max_size]].

<code cpp>
std::cout << B.size() << std::endl;
std::cout << B.capacity() << std::endl;

B.reserve(100);
std::cout << B.size() << std::endl;
std::cout << B.capacity() << std::endl;

std::cout << C.max_size() << std::endl;
</code>

==== Přístup k jednotlivým položkám kontejneru ====

Pokud to dává smysl ((Některé kontejnery, jako např. [[http://www.cplusplus.com/reference/stack/stack/|std::stack]] přístup k jednotlivým položkám v paměťové struktuře neumožňují.)), lze existujícím položkám kontejneru přístupovat přímo, prostřednictvím [[http://www.cplusplus.com/reference/vector/vector/operator[]/|operátoru []]] a metody [[http://www.cplusplus.com/reference/vector/vector/at/|at]], nebo nepřímo s využitím iterátoru. Přímým přístupem lze provádět čtení i zápis, iterátor může být i konstantní, tj. pouze pro čtení. 

<code cpp>
A[3] = 100;
std::cout << A.at(3);
std::vector<int>::iterator a = A.begin();
std::cout << *(a+3);
</code>

Hlavní rozdíl mezi prvními dvěma způsoby je v tom, že u metody [[http://www.cplusplus.com/reference/vector/vector/at/|at]]' jsou kontrolovány meze a v případě jejich překročení je vyvolána výjimka [[http://www.cplusplus.com/reference/stdexcept/out_of_range/|std::out_of_range]]. Při použití [[http://www.cplusplus.com/reference/vector/vector/operator[]/|operátoru []]] meze kontrolovány nejsou.

<code cpp>
// vektor B je prázdný
try {
    B.at(0);
} 
catch (std::out_of_range &e) {
    std::cout << e.what();
}
</code>

Hlavní výhodou vektoru oproti poli je flexibilita při vkládání nových prvků - vektor v případě potřeby automaticky zvětšuje prostor podle potřeby (a pokud je v paměti místo).

<code cpp>
// vložení prvku na konec vektoru
B.push_back (10);
std::cout << B.size() << std::endl;
std::cout << B[0];

// vložení prvku na pozici iterátoru, v tomto případě na začátek
B.insert (B.begin(), 20);
</code>
==== Procházení kontejneru ====

<code cpp>
// konstatní iterátor, nelze měnit položky vektoru
for (std::vector<char>::const_iterator i = C.begin(); i != C.end(); ++i)
    std::cout << *i << ' ';
    
// protože iterátor je datovým typem, lze využít v C++11 kompilátorech auto
// v tomto případě půjde měnit položky, kompilátor volí nekonstantní iterátor
for (auto i = C.begin(); i != C.end(); ++i)
    std::cout << *i << ' ';
    
// pro zjednodušení zápisu lze využít typedef
typedef std::vector<char> pole;
pole C;

for (pole::const_iterator i = C.begin(); i != C.end; ++i)
    std::cout << *i << ' ';
</code>

<code cpp>
// C++11 range-based for loop
for (auto i : C)
    std::cout << i << ' ';
    
// pro případ, že chceme zajistit nemožnost změny proměnné i uvnitř smyčky
for (const auto i : C)
    std::cout << i << ' ';
    
// při použití reference lze měnit prvky uvnitř kontejneru
for (auto &i : C)
    std::cout << i << ' ';
    
// případně lze vytvořit konstatní referenci - to dává smysl v případě, 
// že nechceme umožnit změnu prvků kontejneru, ale časová režie kopírování 
// prvků z kontejneru je příliš velká
for (const auto &i : C)
    std::cout << i << ' ';
</code> 

<code cpp>
std::copy (C.begin(), C.end(), std::ostream_iterator<char>(std::cout, " "));
</code>

<code cpp>
// přetížený proudový operátor
std::ostream& operator<< (std::ostream& out, const std::vector<char>& v) {
  if (!v.empty()) {
    out << "[";
    std::copy (v.begin(), v.end(), std::ostream_iterator<int>(out, ", "));
    out << "]\n";
  }
  return out;
}

// lze vytvořit i šablonu, která zajistí nezávislost na datovém typu použitém ve vektoru
template <typename T>
std::ostream& operator<< (std::ostream& out, const std::vector<T>& v) {
  if (!v.empty()) {
    out << "[";
    std::copy (v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
    out << "]\n";
  }
  return out;
}
</code>

==== Řazení položek v kontejneru ====

Celkem často je třeba položky v kontejneru seřadit. Pro tento účel lze využít např. generickou funkci [[http://www.cplusplus.com/reference/algorithm/sort/|std::sort]]. Argumenty funkce jsou iterátory začátku a konce kontejneru.

<code cpp>
std::vector<char> R = {'r', 'j', 'l', 'k', 'a'};
std::sort (R.begin(), R.end());
</code>

Pokud bychom potřebovali reverzní řazení, lze využít hned několika možností

<code cpp>
// reverzní iterátory
std::sort (R.rbegin(), R.rend());
// generická funkce reverse
std::reverse (R.begin(), R.end());
</code>

Další možností, která je využívána v případech, kdy není známo třídicí kritérium (např. instance nově definované třídy), lze využít komparátoru - funkce, která bude porovnávat instance mezi sebou. Nejčastěji je komparátor definován jako třída, která obsahuje přetížený ''operator()'', takže je možné anonymní instanci třídy volat jako funkci (funkční objekt, funktor).

<code cpp>
struct comp {
     bool operator()(char a, char b) {
          return a > b;
     }
}; 

std::sort (R.begin(), R.end(), comp);
</code>


----


===== Asociativní kontejner =====

Na rozdíl od sekvenčních kontejnerů, které používají jako klíč pro přístup k položkám kladné celé číslo, umožňují asociativní kontejnery použít jako klíč libovolný datový typ. Jak reprezentanta asociativního kontejneru zde použijeme [[http://www.cplusplus.com/reference/map/map/|std::map]].

Kontejner [[http://www.cplusplus.com/reference/map/map/|std::map]] vytváří páry klíč-hodnota, klíč je v tomto případě unikátní((V případě potřeby duplicitních klíčů lze využít kontejner [[http://www.cplusplus.com/reference/map/multimap/|std::multimap]])). Vnitřní implementace je taková, že položka je vlastně proměnnou datového typu [[http://www.cplusplus.com/reference/utility/pair/pair/|std::pair]] a platí, že první položka páru se jmenuje ''first'' a druhá položka se jmenuje ''second''. V příkladu je vytvářen vztah mezi světovými metropolemi a počtem jejich obyvatel. 

<code cpp>
std::map<std::string, int> D;
D["Tokyo"] = 37833000;
D["Dilli"] = 24953000;
D["Sanghaj"] = 22991000;
D["Maxico City"] = 20843000;
D["Sao Paulo"] = 20831000;
</code>

Stejně jako kontejner [[http://www.cplusplus.com/reference/vector/vector/|std::vector]] je i kontejner [[http://www.cplusplus.com/reference/map/map/|std::map]] možné procházet různými způsoby, např. pomocí iterátoru, který lze opěr nahradit klíčovým slovem ''auto''. 

<code cpp>
for (auto i : D) {
    std::cout << std::setw(15) << std::left << i.first << i.second << "\n";
}
</code>

Za povšimnutí stojí, že jednotlivé prvky kontejneru jsou seřazeny podle kritéria, které je uplatnitelné na klíč. Z toho mimochodem vyplývá, že pokud bude klíčem nový datový typ, definovaný jako třída, je třeba pro tento datový typ vytvořit pravidlo pro porovnávání instancí (tj. přetížený operátor ''>''). 

<code>
Dilli          24953000
Maxico City    20843000
Sanghaj        22991000
Sao Paulo      20831000
Tokyo          37833000
</code>

Díky řazení je možné efektivně implementovat vyhledávací funkci [[http://www.cplusplus.com/reference/map/map/find/|find]], jejíž návratovou hodnotou je iterátor nastavený na vyhledaný prvek. V příkladu plná kvalifikace iterátoru, opět lze využít ''auto''.

<code cpp>
std::map<std::string, int>::iterator d = D.find("Sanghaj");
std::cout << "found: " << std::left << d->first << " " << d->second << "\n";
</code> 

==== Vkládání položek ====

Ke vkládání dat do kontejneru [[http://www.cplusplus.com/reference/map/map/|std::map]] slouží kromě přímého přístupu [[http://www.cplusplus.com/reference/map/map/operator[]/|operátorem []]] funkce [[http://www.cplusplus.com/reference/map/map/insert/|insert]]. Protože se položky automaticky řadí podle hodnoty klíče, není při vkládání (na rozdíl od vektoru a jiných sekvenčních kontejnerů) nutné používat iterátor, ovšem pokud je známá přibližná budoucí pozice vkládané položky v seřazené kolekci, dá se iterátorem napovědět. Návratovou hodnotou funkce [[http://www.cplusplus.com/reference/map/map/insert/|insert]] je pár tvořící iterátor a logická hodnota, nabývající hodnoty ''false'' v případě, že vkládaná položka se již v kontejneru vyskytuje. 

<code cpp>
std::pair<std::map<std::string, int>::iterator, bool> ret;
// vytvoření instance std::pair přímým voláním konstruktoru 
ret = D.insert(std::pair<std::string, int>("Sanghaj", 22991000));
if (ret.second == false) {
    std::cout << "polozka " << ret.first->first << " jiz v kolekci existuje s hodnotou " << ret.first->second << "\n";
}

// vytvoření instance std::pair metodou std::make_pair
// dá se čekat, že položka bude první - použit iterátor 
D.insert (D.begin(), std::make_pair("Beijing", 21707000));

// vytvoření páru metodou kontejneru
D.insert (std::map<std::string, int>::value_type ("Jakarta", 31500000));
</code> 

Aktualizaci hodnot párů je možné provést přímo prostřednictvím [[http://www.cplusplus.com/reference/map/map/operator[]/|operátoru []]] nebo s využitím iterátoru (tj. např. vyhledáním páru podle klíče ''first'' a změnou hodnoty ''second''). 
==== Mazání položek ====

K odstranění položek z kontejneru lze využít funkci [[http://www.cplusplus.com/reference/map/map/erase/|erase]] ve třech různých variantách

<code cpp>
// mazání položky podle klíče
D.erase ("Mexico City");

// mazání položky pomocí iterátoru
auto d = D.find ("Mexico City");
D.erase (d);

// mazání položky v rozsahu daném dvěma iterátory (v tomto případě všechny položky)
D.erase (D.begin (), D.end ());
</code>

==== Vlastní datový typ jako klíč ====

Jak už bylo zmíněno v předchozím textu, pokud má být klíčem hodnota uživatelsky definovaného datového typu, je třeba definovat kritérium, podle kterého se instance tohoto typu řadí. To lze zařídit např. dvěma následujícími způsoby.

**1.** Třída popisující nový datový typ obsahuje přetížený operátor ''<'', který definuje kritérium porovnávání. 

<code cpp>
class Key {
    int value;
public:
    bool operator< (const Key & src) const {
        return (this->value < src.value);
    }
};
</code>

<code cpp>
Key k1, k2;
std::map<Key, int> A;

A.insert (std::pair<Key, int>(k1, 100));
A.insert (std::pair<Key, int>(k2, 200));
</code>

**2.** Definice komparátoru. Komparátor je třída, která obsahuje přetížený operátor ''()'', takže je možné komparátor volat jako funkci. Takto definovaný komparátor je třetím argumentem předávaným šabloně třídy.

<code cpp>
struct PorovnejOsobu;

class Osoba {
    std::string jmeno;
public:
    Osoba (std::string j): jmeno(j) {}
    bool operator() (const Osoba &a) {
        return this->jmeno < a.jmeno;
    }
    friend PorovnejOsobu;
};

struct PorovnejOsobu {
    bool operator() (const Osoba &a, const Osoba &b) {
        return a.jmeno < b.jmeno;
    }
};

std::map<Osoba, int, PorovnejOsobu> B;
B.insert(std::pair<Osoba, int>(Osoba("Jan"), 10));
</code>

----

V C++11 je možné využít ještě lambda funkce. Lambda je zápis funkčního objektu, tj. objektu, který bude možné volat jako funkci. V tomto případě není ovšem aplikace úplne přímočará, příklad je spíše návodem na další zkoumání. 

<code cpp>
auto comparator = [](const Osoba& a, const Osoba& b) -> bool
{
    return a.jmeno < b.();
};

std::map<Osoba, int, decltype(comparator)> B(comparator);
</code>