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

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 vectoru, který může měnit procházené prvky.
• Existuje typ vector::const_iterator, což je iterátor vectoru, 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*;
 
        ...
    };
    ...
};

Řešení

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

Zde používáme standardní algoritmus std::reverse (z hlavičky <algorithm>), 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.

Řešení

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

K binárnímu vyhledávání lze použít i funkci standardní knihovny std::lower_bound, která funguje podobně¹⁾ 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.

Řešení