Výchozí kód

Po minulém cvičení již našemu vectoru 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 vectoru. 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 vectoru 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;

Řešení

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())¹⁾.

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²⁾ 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,
• a 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?

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.

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

1. Specializací ''std::iterator_traits'' pro náš iterátor
2. 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.

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;
}

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³⁾.

Řešení

TODO: Více kódu a vysvětlení jaké algoritmy můžeme přidat?

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

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

Řešení

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

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.

Řešení