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

<code cpp>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;</code>

Doplňte program tak, aby byly možné následující operace:

<code cpp>std::cout << myNum - "45" << std::endl;
std::cout << myNum * "4" << std::endl;</code>
===== 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<double>''. 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:

<code cpp>
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;
}
</code>
{{ :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:

<code cpp>
std::cout << "v1: " << v1;
std::cout << "v2: " << v2;
std::cout << "v3: " << v3;
std::cout << "v4: " << v4;
</code>

{{: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
<code cpp>
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 { ... }
    ...
};
</code>

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:
<code cpp>
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*;

        ...
    };
    ...
};
</code>

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:

<code cpp>
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;
}
</code>

{{ :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:

<code cpp>
#include "vector.hpp"
#include <iostream>
#include <algorithm>

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
}
</code>

{{ :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:

<code cpp>
#include "vector.hpp"
#include <iostream>
#include <algorithm>

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';
}
</code>

{{ :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í}}