std::lower_bound
vrátí iterátor na první větší
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.
vector
metodu swap
, která vymění obsah dvou vektorů.
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.
std::swap
z hlavičky <utility>
.
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 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 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é.
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:
vector::iterator
, což je iterátor vector
u, který může měnit procházené prvky.
vector::const_iterator
, což je iterátor vector
u, který nesmí měnit procházené prvky.
begin
a end
, které:
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.
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*; ... }; ... };
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
.
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ě1) 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
.
std::lower_bound
vrátí iterátor na první větší