{{page>courses:b6b36pjc:styles#common&noheader&nofooter}}
{{page>courses:b6b36pjc:styles#cviceni&noheader&nofooter}}
======= Cvičení 7: Přetěžování operátorů a iterátory =======
{{ :courses:b6b36pcc:cviceni:pruvodce.png?90|Průvodce studiem}}
Kromě funkcí lze v C%%++%% přetížit i operátory. Uvidíme, jak lze snadno přetížit operátor sčítání. Přetížit lze ale i jiné speriální operátory, například operátor indexace pole nebo operátor zápisu do proudu ''<<''.
Iterátory slouží k snadnému procházení datových struktur. U pole automaticky předpokládáme procházení pole podle indexů jeho prvků. U složitějších struktur (stromy, grafy apod.) může být obtížnější určit pořadí, v jakém prvky dané struktury procházet. Právě to určují iterátory, které můžeme nad danými strukturami definovat.
===== Přetížení operátoru sčítání =====
Součet umožňuje sečíst dvě celá (typu ''int'') nebo desetinná (typu ''float'', ''double'') čísla. Následující příklad ukazuje, jak lze přetížit operátor součtu ''+'' tak, aby bylo možné přičíst číslo zadané v řetězci.
class Number {
public:
int num;
Number(int n) : num(n) {}
Number operator + (std::string b) {
std::stringstream ss;
int bb;
ss << b;
ss >> bb;
return Number(num + bb);
}
};
std::ostream& operator<<(std::ostream& os, const Number& dt) {
os << dt.num;
return os;
}
Number myNum(12);
std::cout << myNum + "45" << std::endl;
Doplňte program tak, aby byly možné následující operace:
std::cout << myNum - "45" << std::endl;
std::cout << myNum * "4" << std::endl;
===== Indexace vektoru =====
{{:courses:b6b36pcc:cviceni:cviceni_7_init.zip|Výchozí kód}}
Po minulém cvičení již našemu ''vector''u nechybí mnoho aby byl plnohodnotná
náhrada za ''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;
}
{{ :courses:b6b36pcc:cviceni:ukoly.png?90|Úkoly k procvičení}}
* 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:b6b36pcc:cviceni:cviceni_7_ops.zip|Řešení}}
===== Iterátory =====
Iterátory jsou důležitou součástí C%%++%%, protože slouží jako abstrakce
průchodu kolekcemi a tudíž umožňují mít knihovnu algoritmů oddělenou od
jednotlivých kolekcí. To znamená, že po přidání iterátorů do naší třídy
půjde seřadit obsažené prvky zavoláním ''std::sort(vec.begin(), vec.end())''((
A taky, že na náš vektor půjde použít for-each loop: ''for (double d: vec) ...'')).
Na iterátory se můžeme dívat jako zobecněné ukazatele (ostatně, ukazatele
se dají předat algoritmům místo iterátorů), a dělíme je do 4((Existuje
ještě jedna kategorie, ''ContiguousIterator'', která dává více záruk,
nežli ''RandomAccessIterator'', ale z důvodů zpětné kompatibility tato
kategorie není součástí typového systému.)) kategorií, dle toho co všechno
se s nimi dá dělat:
* ''RandomAccessIterator'' neboli **Iterátory s náhodným přístupem**
* ''BidirectionalIterator'' neboli **Obousměrné iterátory**
* ''ForwardIterator'' neboli **Dopředné iterátory**
* ''InputIterator'' / ''OutputIterator'' neboli **Vstupní** (nebo) **výstupní iterátory**
Input/Output iterátory se na tomto cvičení nebudeme zabývat, používají se
pro čtení, respektive zápis na vstupu pomocí algoritmů.
Jak název napovídá,
* **Iterátory s náhodným přístupem** umožňují provádět při procházení libovolně dlouhé skoky,
* **Obousměrné iterátory** umožňují procházet kolekci oběma směry,
* **Dopředné iterátory** umožňují procházet kolekci jedním směrem.
a každá kolekce poskytuje iterátory z jedné z těchto kategorií.
**Do jaké kategorie spadají ukazatele?**
==== Iterátor pro náš vector ====
Nejjednodušší a nejpragmatičtější způsob jak přidat iterátory do naší
implementace třídy ''vector'' je tento
class vector {
...
using iterator = double*;
using const_iterator = double const*;
iterator begin() { return m_data; }
iterator end() { return m_data.get() + m_size; }
const_iterator begin() const { ... }
const_iterator end() const { ... }
const_iterator cbegin() const { ... }
const_iterator cend() const { ... }
...
};
Jak již bylo řečeno, ukazatele jsou v podstatě iterátory, takže je můžeme
použít rovnou. Následně je potřeba přidat sadu metod, které vrací iterátor
na začátek/konec pole obsaženého ve vektoru.
Teď se ale podíváme jak postupovat v případě, že nemůžeme vytváření
iterátoru podobným způsobem obejít, postavíme si tedy postupně vlastní
iterátor jako vnořenou třídu uvnitř ''vector''.
===== Definování vlastního iterátoru =====
Každý iterátor o sobě musí deklarovat 5 vlastností:
* ''iterator_category'' -- například ''std::forward_iterator_tag'', deklaruje kategorii iterátoru
* ''difference_type'' -- obvykle ''std::ptrdiff_t'', deklaruje typ, ve kterém se dá napočítat vzdálenost mezi iterátory daného typu (nejen ''it2 - it'').
* ''value_type'' -- například ''double'', deklaruje hodnotu typu, na který iterátor ukazuje
* ''reference'' -- například ''double&'', deklaruje referenci na typ, na který iterátor ukazuje (obvyklý výsledek ''*it'')
* ''pointer'' -- například ''double*'', deklaruje ukazatel na typ, na který iterátor ukazuje
Tyto vlastnosti se dají deklarovat 2 způsoby
- Specializací [[https://en.cppreference.com/w/cpp/iterator/iterator_traits|''std::iterator_traits'']] pro náš iterátor
- Zavedením type aliasů s těmito jmény uvnitř našeho iterátoru
My budeme používat druhou možnost:
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*;
...
};
...
};
Dále je potřeba přidat metody ''begin'' a ''end'' pro které platí:
* Pro nekonstantní ''vector'' vracejí ''iterator''.
* Pro konstatní ''vector'' vracejí ''const_iterator''.
* Metoda ''begin'' vrací iterátor, který ukazuje **na první** prvek.
* Metoda ''end'' vrací iterátor, který ukazuje **za poslední** prvek.
//Ideálně bychom měli přidat ještě ''cbegin'', ''cend'', ''rbegin'',
''rend'', ''crbegin'' a ''crend'', ale to pro toto cvičení přeskočíme.//
==== Dopředný iterátor ====
Začneme implementací dopředného iterátoru, protože má nejméně požadavků
na to co musí iterátor umět, a tudíž i nejméně metod k implementaci. Až
s jeho implementací skončíme, budeme chtít aby tento kód fungoval pro
náš vektor:
void multiply_all(vector& v, double factor) {
for (auto& elem : v) {
elem *= factor;
}
}
double accumulate(const vector& v) {
double sum = 0;
for (auto const& elem : v) {
sum += elem;
}
return sum;
}
{{ :courses:b6b36pcc:cviceni:ukoly.png?90|Úkoly k procvičení}}
Co se implementace týče, dopředné iterátory (''iterator'' i
''const_iterator'') musí splňovat 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.)).
{{:courses:b6b36pcc: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 k projití našeho vektoru pozpátku, což slouží například k otočení
pořadí všech prvků ve vektoru. Až s implementací skončíme, chceme aby
tento kód fungoval:
#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
}
{{ :courses:b6b36pcc:cviceni:ukoly.png?90|Úkoly k procvičení}}
Co se implementace týče, třída obousměrného iterátoru oznamuje svou
kategorii pomocí ''std::bidirectional_iterator_tag'' a obousměrné iterátory
musí splňovat následující podmínky navíc:
* ''%%--%%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í.
{{:courses:b6b36pcc:cviceni:cviceni_7_iter2.zip|Řešení}}
==== Iterátor s náhodným přístupem ====
Iterátor s náhodným přístupem je nejsilnější (je na ně nejvíce nároků)
kategorie iterátorů, která v typovém systému. Narozdíl od obousměrného
iterátoru, umožňuje iterátor s náhodným přístupem provádět libovolně
dlouhé skoky vpřed i vzad v konstatním čase. To je užitečné například
pro řazení (''std::sort'') nebo binární vyhledávání (''std::binary_search'',
''std::lower_bound'' a ''std::upper_bound'').
Po jeho implementování by následující kód 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';
}
{{ :courses:b6b36pcc:cviceni:ukoly.png?90|Úkoly k procvičení}}
Co se implementace týče, třída iterátoru s náhodným přístupem používá
''std::random_access_iterator_tag'' jako svoji kategorii a 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''.
{{:courses:b6b36pcc:cviceni:cviceni_7_iter3.zip|Řešení}}