for (double d: vec) …
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.
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;
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:
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; }
vector
operátor indexace pole []
.
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 <<
.
vector
operátor zápisu do proudu <<
.
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;
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())
1).
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 42) 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á,
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
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í:
vector
vracejí iterator
.
vector
vracejí const_iterator
.
begin
vrací iterátor, který ukazuje na první prvek.
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
ukazuje3).
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í.
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
.
for (double d: vec) …
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.double
– nemá ani členská data, ani metody.