===== Další funkcionalita vectoru ===== {{:courses:a7b36pjc:cviceni:cviceni_7_init.zip|Výchozí kód}} Náš první úkol bude zjednodušit implementaci některých speciálních členských funkcí, jmenovitě kopírujícího přiřazení, přesunujícího konstruktoru a přesunujícího přiřazení. Velmi nám pomůže, když budeme mít k dispozici metodu, která dvěma objektům typu ''vector'' vymění veškerý obsah. * Implementujte ve třídě ''vector'' metodu ''swap'', která vymění obsah dvou vektorů. * Deklarace této metody je ''void swap(vector& rhs)'' a po jejím skončení by měl být obsah obou vektorů prohozen bez toho, aby se přesouvaly jednotlivé prvky. * Ke zjednodušenní prohazování hodnot v proměnných můžete použít knihovní funkci ''std::swap'' z hlavičky ''''. * Zjednodušte kopírující přiřazení, přesunující konstruktor a přesunující přiřazení pomocí metody ''swap''. Náš ''vector'' už je jen malý kousek od plnohodnotného ''std::vector''. Jedna nápadná chybějící funkcionalita je možnost použít operátor indexace pole pro přístup k jednotlivým prvkům ''vector''u. Chtěli bychom, aby následující kód fungoval: void multiply_all(vector& v, double factor) { for (size_t i = 0; i < v.size(); i++) { v[i] *= factor; } } double accumulate(const vector& v) { double sum = 0; for (size_t i = 0; i < v.size(); i++) { sum += v[i]; } return sum; } vector cat(vector v) { auto original_size = v.size(); v.resize(v.size() * 2); for (size_t i = 0; i < original_size; ++i) { v[original_size + i] = v[i]; } return v; } * Implementujte ve třídě ''vector'' operátor indexace pole ''[]''. * Operátor indexace se vždy deklaruje uvnitř třídy a jeho deklarace bude ''double& operator[](size_t)'', respektive ''double operator[](size_t) const''. Jeho definice pak bude prakticky stejná jako definice metody ''at''. Následující vychytávku ''std::vector'' neumí, ale bude se nám hodit. Protože je otravné psát ''print_vector'' vždy, když chceme vypsat obsah ''vector''u na výstup, vytvořme si vlastní přetížení operace ''%%<<%%''. * Implementujte pro třídu ''vector'' operátor zápisu do proudu ''%%<<%%''. * Operátor zápisu do proudu se vždy deklaruje mimo třídu a jeho deklarace je ''std::ostream& operator%%<<%%(std::ostream&, const vector&)''. Pokud jsme všechno udělali správně, následující kód bude fungovat: std::cout << "v1: " << v1; std::cout << "v2: " << v2; std::cout << "v3: " << v3; std::cout << "v4: " << v4; {{:courses:a7b36pjc:cviceni:cviceni_7_swap.zip|Řešení}} ===== Iterátory ===== Iterátory jsou důležitou součástí C%%++%%, protože umožňují spolupráci kolekcí (jako je ''vector'') s algoritmy ze standardní knihovny. Až přidáme iterátory do naší třídy, bude možné například seřadit její prvky vzestupně pomocí volání ''std::sort''. Není iterátor jako iterátor; iterátory kategorizujeme podle toho, jak jsou mocné. * **Dopředné iterátory** umožňují procházet kolekci jedním směrem. * **Obousměrné iterátory** umožňují procházet kolekci oběma směry. * **Iterátory s náhodným přístupem** umožňují provádět při procházení libovolně dlouhé skoky. Každá kolekce poskytuje iterátory z jedné z těchto kategorií. ==== Dopředný iterátor ==== Pojďme zavést dopředný (//forward//) iterátor pro třídu ''vector''. Začínáme dopředným iterátorem, protože je nejjednodušší. Umožňuje nám procházet prvky jedním směrem, typicky zepředu dozadu. Až budeme hotovi, následující kód bude fungovat: void multiply_all(vector& v, double factor) { for (vector::iterator it = v.begin(); it != v.end(); it++) { *it *= factor; } } double accumulate(const vector& v) { double sum = 0; for (vector::const_iterator it = v.begin(); it != v.end(); it++) { sum += *it; } return sum; } Aby předchozí kód pracoval, jak má, musí být splňeny tyto podmínky: * Existuje typ ''vector::iterator'', což je iterátor ''vector''u, který může měnit procházené prvky. * Existuje typ ''vector::const_iterator'', což je iterátor ''vector''u, který nesmí měnit procházené prvky. * Existují metody ''begin'' a ''end'', které: * Pro nekonstantní ''vector'' vracejí ''iterator''. * Pro konstatní ''vector'' vracejí ''const_iterator''. * Metoda ''begin'' vrací iterátor, který ukazuje **na první** prvek. * Medota ''end'' vrací iterátor, který ukazuje **za poslední** prvek. Pro samotné dopředné iterátory (''iterator'' i ''const_iterator'') musí platit následující pravidla. Za předpokladu, že ''it'' je iterátor: * ''++it'' způsobí, že ''it'' ukazuje na další prvek. Hodnota výrazu je iterátor po inkrementaci. * ''it++'' způsobí, že ''it'' ukazuje na další prvek. Hodnota výrazu je iterátor před inkrementací. * ''*it'' poskytne prvek, na který ''it'' ukazuje. * ''it == it2'' a ''it != it2'' rozhodne o rovnosti dvou iterátorů na základě toho, zda ukazují na stejný prvek. * ''it%%->%%foo()'' zavolá metodu ''foo'' prvku, na který ''it'' ukazuje. Nápodobně ''it%%->%%bar'' poskytne členský objekt ''bar'' prvku, na který ''it'' ukazuje. (Nebudeme potřebovat, protože náš typ prvku -- ''double'' -- nemá ani členská data, ani metody.) Finta: ukazatel splňuje všechny požadavky dopředného iterátoru. (Dokonce splňuje i všechny požadavky iterátoru s náhodným přístupem.) Proto stačí jen implementovat metody ''begin'' a ''end'' a jako iterátory jmenovat ukazatele: class vector { public: ... using iterator = double*; using const_iterator = const double*; ... }; Na cvičení ale budeme alespoň ''iterator'' implementovat pracně, abychom si vyzkoušeli přetěžování operátorů. Pokud vytváříme iterátor jako vlastní třídu, musíme nějakým způsobem deklarovat jeho kategorii. To se dělá tak, že v něm zavedeme alias typu ''iterator_category''. Není to ale jediná věc, kterou by o sobě měl iterátor deklarovat, celkem je potřeba zavést 5 aliasů typů: * ''iterator_category'' -- například ''std::forward_iterator_tag'', deklaruje kategorii iterátoru * ''difference_type'' -- obvykle ''std::ptrdiff_t'', označuje typ, ve kterém se dá napočítat vzdálenost mezi iterátory daného typu (nejen ''it2'' - ''it''). * ''value_type'' -- například ''double'', označuje hodnotu typu, na který iterátor ukazuje * ''reference'' -- například ''double&'', označuje referenci na typ, na který iterátor ukazuje (obvyklý výsledek ''*it'') * ''pointer'' -- například ''double*'', označuje ukazatel na typ, na který iterátor ukazuje class vector { public: ... class iterator { public: using difference_type = std::ptrdiff_t; using iterator_category = std::forward_iterator_tag; using value_type = double; using reference = double&; using pointer = double*; ... }; ... }; {{:courses:a7b36pjc:cviceni:cviceni_7_iter1.zip|Řešení}} ==== Obousměrný iterátor ==== Obousměrný iterátor nám dovoluje při procházení couvat. Toho můžeme využít třeba k tomu, abychom prošli ''vector'' pozpátku. Chtěli bychom, aby fungoval tento kód: #include "vector.hpp" #include #include vector reverse(const vector& v) { if (v.size() == 0) return vector(); vector result; auto i = v.end(); do { i--; result.push_back(*i); } while (i != v.begin()); return result; } int main() { vector v; v.push_back(415); v.push_back(154); v.push_back(336); v.push_back(276); std::cout << v; // 415 154 336 276 std::reverse(v.begin(), v.end()); std::cout << v; // 276 336 154 415 v = reverse(v); std::cout << v; // 415 154 336 276 } Zde používáme standardní algoritmus ''std::reverse'' (z hlavičky ''''), který obrátí pole. Potom pole podruhé obrátíme vlastní funkcí ''reverse''. Pro obousměrný iterátor platí následující dodatečné podmínky: * ''%%--%%it'' způsobí, že ''it'' ukazuje na předchozí prvek. Hodnota výrazu je iterátor po dekrementaci. * ''it%%--%%'' způsobí, že ''it'' ukazuje na předchozí prvek. Hodnota výrazu je iterátor před dekrementací. Třída obousměrného iterátoru oznamuje svou kategorii pomocí ''std::bidirectional_iterator_tag''. {{:courses:a7b36pjc:cviceni:cviceni_7_iter2.zip|Řešení}} ==== Iterátor s náhodným přístupem ==== Nejvyšší kategorií iterátoru, kterou si dnes ukážeme, je iterátor s náhodným přístupem. Ten umožňuje nejen procházet prvky, ale také provádět libovolně dlouhé skoky vpřed i vzad. Pouze kolekce s takovýmto iterátorem lze setřídit pomocí ''std::sort''. Následující kód by měl fungovat: #include "vector.hpp" #include #include vector::iterator binary_find(vector::iterator first, vector::iterator last, double val) { auto l = first; auto r = last; while (true) { if (l >= r) return last; // return last if val not found size_t sz = r - l; auto mid = l + sz / 2; if (*mid < val) { l = mid + 1; } else if (*mid > val) { r = mid; } else { return mid; } } } int main() { vector v; v.push_back(823); v.push_back(133); v.push_back(408); v.push_back(802); v.push_back(653); v.push_back(451); v.push_back(239); v.push_back(883); v.push_back(314); v.push_back(616); v.push_back(709); v.push_back(114); std::sort(v.begin(), v.end()); std::cout << v; auto it = binary_find(v.begin(), v.end(), 451); size_t pos = it - v.begin(); std::cout << "v[" << pos << "] = " << *it << '\n'; it = std::lower_bound(v.begin(), v.end(), 451); pos = it - v.begin(); std::cout << "v[" << pos << "] = " << *it << '\n'; } K binárnímu vyhledávání lze použít i funkci standardní knihovny ''std::lower_bound'', která funguje podobně((Pokud hledaný prvek neexistuje, ''std::lower_bound'' vrátí iterátor na první větší)) jako naše ''binary_search''. ''std::binary_search'' pak pouze vrátí ''true'' pokud byla hledaná hodnota nalezena. Existuje i ''std::upper_bound'', která se chová trochu jinak a vrací iterátor na prvek, který je bezprostředně větší než hledaný prvek. Za předpokladu, že ''it'' je iterátor a ''sz'' je velikost (typu ''size_t''), dodatečné podmínky pro iterátor s náhodným přístupem jsou: * ''it + sz'' je iterátor posunutý o ''sz'' kroků dopředu. * ''it - sz'' je iterátor posunutý o ''sz'' korků dozadu. * ''it += sz'' posune ''it'' o ''sz'' kroků dopředu. Hodnota výrazu je ''it'' po posunutí. * ''it -= sz'' posune ''it'' o ''sz'' kroků dozadu. Hodnota výrazu je ''it'' po posunutí. * ''it < it2'' rozhodne, zda ''it'' ukazuje na prvek před prvkem, na který ukazuje ''it2''. Podobně pro ''>'', ''%%<=%%'', ''>=''. * ''it[sz]'' poskytne prvek o ''sz'' kroků napřed od ''it''. To samé, jako ''*(it + sz)''. * ''it2 - it'' poskytne počet kroků od ''it'' do ''it2''. Třída iterátoru s náhodným přístupem oznamuje svou kategorii pomocí ''std::random_access_iterator_tag''. {{:courses:a7b36pjc:cviceni:cviceni_7_iter3.zip|Řešení}}