Cvičení 7: Přetěžování operátorů a iterátory

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

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

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

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í

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

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í

¹⁾

A taky, že na náš vektor půjde použít for-each loop: for (double d: vec) …

²⁾

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.

³⁾

Nebudeme potřebovat, protože náš typ prvku – double – nemá ani členská data, ani metody.

Table of Contents

Cvičení 7: Přetěžování operátorů a iterátory

Přetížení operátoru sčítání

Indexace vektoru

Iterátory

Iterátor pro náš vector

Definování vlastního iterátoru

Dopředný iterátor

Obousměrný iterátor

Iterátor s náhodným přístupem