====== 4. 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.
std::vector A(10);
std::vector B;
std::vector C {'a', 'b', 'c'};
Velikost jednotlivých vektorů můžeme ověřit např. pomocí členské metody [[http://www.cplusplus.com/reference/vector/vector/size/|size]].
std::cout << A.size << std::endl;
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]].
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;
==== 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í.
A[3] = 100;
std::cout << A.at(3);
std::vector::iterator a = A.begin();
std::cout << *(a+3);
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.
// vektor B je prázdný
try {
B.at(0);
}
catch (std::out_of_range &e) {
std::cout << e.what();
}
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).
// 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);
==== Procházení kontejneru ====
// konstatní iterátor, nelze měnit položky vektoru
for (std::vector::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 pole;
pole C;
for (pole::const_iterator i = C.begin(); i != C.end; ++i)
std::cout << *i << ' ';
// 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 << ' ';
std::copy (C.begin(), C.end(), std::ostream_iterator(std::cout, " "));
// přetížený proudový operátor
std::ostream& operator<< (std::ostream& out, const std::vector& v) {
if (!v.empty()) {
out << "[";
std::copy (v.begin(), v.end(), std::ostream_iterator(out, ", "));
out << "]\n";
}
return out;
}
// lze vytvořit i šablonu, která zajistí nezávislost na datovém typu použitém ve vektoru
template
std::ostream& operator<< (std::ostream& out, const std::vector& v) {
if (!v.empty()) {
out << "[";
std::copy (v.begin(), v.end(), std::ostream_iterator(out, ", "));
out << "]\n";
}
return out;
}
==== Ř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.
std::vector R = {'r', 'j', 'l', 'k', 'a'};
std::sort (R.begin(), R.end());
Pokud bychom potřebovali reverzní řazení, lze využít hned několika možností
// reverzní iterátory
std::sort (R.rbegin(), R.rend());
// generická funkce reverse
std::reverse (R.begin(), R.end());
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).
struct comp {
bool operator()(char a, char b) {
return a > b;
}
};
std::sort (R.begin(), R.end(), comp);
----
===== 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.
std::map D;
D["Tokyo"] = 37833000;
D["Dilli"] = 24953000;
D["Sanghaj"] = 22991000;
D["Maxico City"] = 20843000;
D["Sao Paulo"] = 20831000;
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''.
for (auto i : D) {
std::cout << std::setw(15) << std::left << i.first << i.second << "\n";
}
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 ''>'').
Dilli 24953000
Maxico City 20843000
Sanghaj 22991000
Sao Paulo 20831000
Tokyo 37833000
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''.
std::map::iterator d = D.find("Sanghaj");
std::cout << "found: " << std::left << d->first << " " << d->second << "\n";
==== 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.
std::pair::iterator, bool> ret;
// vytvoření instance std::pair přímým voláním konstruktoru
ret = D.insert(std::pair("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::value_type ("Jakarta", 31500000));
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
// 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 ());
==== 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í.
class Key {
int value;
public:
bool operator< (const Key & src) const {
return (this->value < src.value);
}
};
Key k1, k2;
std::map A;
A.insert (std::pair(k1, 100));
A.insert (std::pair(k2, 200));
**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.
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 B;
B.insert(std::pair(Osoba("Jan"), 10));
----
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í.
auto comparator = [](const Osoba& a, const Osoba& b) -> bool
{
return a.jmeno < b.();
};
std::map B(comparator);