Iterátory II. Bez konceptů ani ránu...

První díl máme za sebou, tématem dne jsou koncepty. Probereme si koncepty iterátorů použité ve standardní knihovně STL jazyka C++.

Motivace

Různé kontejnery poskytují iterátory různé kvality. Např. klasické pole nebo třída vector umožňují snadno, v konstantním čase, získat iterátor na libovolný prvek – stačí znát jeho index. U seznamu (třída list) je situace složitější. Když chceme k-tý prvek, musíme jít na začátek seznamu a provést k iterací, abychom se k němu dostali.

To samé platí pro algoritmy: různé algoritmy vyžadují iterátory různé kvality. Vezměme si třeba jednoduchý výpočet aritmetického průměru a směrodatné odchylky.

 

template <typename ITERATOR>

double prumer(ITERATOR prvni, ITERATOR posledni)

{

   double avg = 0.0;

 

   std::size_t pocet = 0;

   while ( prvni != posledni )

   {

      avg += *prvni++;

      ++pocet;

   }

 

   if ( pocet > 0 )

   {

      avg /= static_cast<double>(pocet);

   }

 

   return avg;

}

 

Jak je vidět, stačí nám jeden průchod přes zadaný rozsah. To znamená, že vstupní data mohou pocházet jak z pole, vektoru, seznamu, tak i třeba ze vstupního datového proudu (např. vstup z příkazové řádky). Nyní jak vypadá směrodatná odchylka

 

template <typename ITERATOR>

double odchylka(ITERATOR prvni, ITERATOR posledni)

{

   double avg = 0.0;

   double var = 0.0;

   ITERATOR i(prvni);  // uložit prvni

 

   // první průchod

   std::size_t pocet = 0;

   while ( prvni != posledni )

   {

      avg += *prvni++;

      ++pocet;

   }

 

   if ( pocet > 0 )

   {

      avg /= static_cast<double>(pocet);

      double sum = 0.0;

 

      // druhý průchod

      while ( i != posledni )

      {

         double tmp = *i++ - avg;

         sum += tmp;

         var += tmp * tmp;

      }

 

      // korekce :

      var = (var - sum * sum /

             static_cast<double>(pocet)) / (pocet - 1);

   }

 

   return sqrt(var);

}

 

Tento algoritmus je už dvouprůchodový: v prvním průchodu přes zadaný rozsah se spočte aritmetický průměr a ten je pak použit v druhém průchodu k výpočtu standardní odchylky. To znamená, že tento algoritmus vyžaduje víc od „svého“ iterátoru (konkrétně možnost více průchodů přes zadaný rozsah). Takže už nejde použít vstup přímo z příkazové řádky, protože tento je pouze jednoprůchodový (jako data na pásce, která se posunuje jen jedním směrem – dovnitř).

Dalším zajímavým momentem je třídění. Třídit lze i s  víceprůchodovými ukazateli, ale nemusí to být efektivní. Těžko si lze představit algoritmus quicksort, který by pro každý přístup k jakémukoliv prvku musel jít na začátek rozsahu a odpočítat potřebný počet iterací k danému prvku (přístup ke k-tému prvku by vyžadoval k iterací, zde by bylo na místě spíše pojmenování slowsort). Řeší to dodatečné požadavky na iterátor: pokud iterátor umožňuje náhodný přístup (přístup ke k-tému prvku v konstantním čase), může být třídění implementováno velmi efektivně. Zde se střetávají dvě pravidla:

• Algoritmus by měl pracovat s co nejobecnějším druhem iterátorů.
• Algoritmus by měl být co nejefektivnější.

Pokud použijeme obecnější víceprůchodový iterátor, nebude třídění efektivní. A naopak, při použití iterátorů s náhodným přístupem bude třídění efektivní, ale nedokážu setřídit všechno, protože ne všechny kontejnery poskytují iterátory s náhodným přístupem. Vítězí efektivita – třídící algoritmy vyžadují iterátory s náhodným přístupem. A když to nejde jinak, je vždy možno doprogramovat třídění pro obecnější iterátory bez náhodného přístupu. Proto také třída list které se to týká, má vlastní optimalizovanou metodu pro setřídění dat.

Co z toho všeho plyne? Iterátory je možné kategorizovat podle toho, jak přistupují k prvkům, jestli jsou jednoprůchodové nebo víceprůchodové, nebo např. jestli je možné iterovat jen jedním směrem nebo i zpátky.

Na Obr. 1 vidíme hierarchii konceptů iterátorů v STL. Šipky naznačují zjemnění konceptu. Analogicky jako při dědění v duchu OOP: Tam, kde se očekává nějaký koncept, funguje i jeho zjemnění.

 

Obr. 1 Hierarchie konceptů

Primitivní koncepty

Nejdříve si pro úplnost vysvětlíme význam čtyř primitivních konceptů, které jsou na Obr. 1 barevně odlišeny od konceptů iterátorů.

Default Constructible	Typy umožňující implicitní inicializaci, tj. jakýkoliv vestavěný typ nebo třída s veřejně přístupným implicitním konstruktorem. Tato inicializace nemusí objektu přiřadit žádnou konkrétní hodnotu. V případě iterátorů jde o vytvoření singulární hodnoty (neinicializovaný iterátor).
Assignable	Typy, jejichž instance se chovají jako (číselné) hodnoty. Instance je možné kopírovat (kopírovací konstruktor) a přiřazovat (operátor =). Patří sem samozřejmě také všechny vestavěné typy.
Equality Comparable	Typy, jejichž instance lze porovnávat operátory == a !=. Sémantika by měla odpovídat relacím rovnosti a nerovnosti známým ze základního kurzu matematiky.
Less Than Comparable	Typy, pro něž jsou definovány relační operátory <, >, <=, >=, od kterých se očekává stejná sémantika, jako u odpovídajících relací, které znáte ze základní výuky matematiky.

Triviální iterátor

Zjednodušeně řečeno, triviální iterátor je takový iterátor, který odkazuje na nějaký prvek, ale neumožňuje přechod na jiný prvek. Tento koncept je víceméně teoretická záležitost, neboť generické algoritmy pracují vždy s nějakým rozsahem prvků a používají iterátory pro pohyb mezi prvky.

Modelem může být například ukazatel na objekt, který není součástí pole. Z pohledu C++ však nedokážeme rozlišit, jestli ukazatel ukazuje na prvek v poli, nebo na osamocený prvek mimo pole

 

int * prvek = new int (0);  // osamocený prvek

int * pole = new int [20];  // pole

 

int neco = prvek[0];  // tohle projde i když nejde o pole

int takyneco = *pole;  // tohle je běžná konstrukce

 

Triviální iterátor podporuje všechny operace „zděděné“ od konceptů, které zjemňuje, a navíc ještě podporuje dereferencování operátorem *, změnu prvku a přístup ke složkám prvku (pokud je prvek instance nějaké třídy) pomocí operátoru ->, viz tabulka 1. U triviálního iterátoru má smysl mluvit o typu prvku.

 

operace	zápis	poznámky
dereferencování	*i	i je dereferencovatelná hodnota.
změna prvku	*i = b	i je dereferencovatelná hodnota a nekonstantní iterátor; b je hodnota (instance) stejného typu jako typ prvku iterátoru i.
přístup ke složkám prvku	i->slozka	Pokud je odkazovaný prvek třída je možné přistupovat k jeho složkám pomocí přetíženého operátoru ->. Ekvivalentní zápis je (*i).slozka. i je dereferencovatelná hodnota

 

Tab. 1 Triviální iterátor – co přidává k zjemňovaným primitivním konceptům. Všechny tyto operace mají konstantní časovou složitost.

Vstupní iterátor

Nejjednodušším „běžným“ iterátorem, je tzv. vstupní iterátor. Jedná se o zjemnění konceptu triviálního iterátoru. Zjemnění se týká následujících vlastností:

• Není zaručena možnost změny prvku.
• Je přidána možnost procházení mezi prvky pomocí operátoru ++ pouze jedním směrem s tím, že po přechodu z i do ++i není zaručeno, že i bude mít ještě smysl (tj. že i bude dereferencovatelná hodnota). To znamená, že koncept vstupního iterátoru negarantuje možnost opakovaného průchodu.

Nejjednodušším modelem je samozřejmě klasický ukazatel do pole prvků. Ukážeme si dále, že klasické ukazatele podporují mnohem více, než jen koncept vstupního iterátoru.

Jiným modelem, který není vůbec založen na použití ukazatele, je iterátor na vstupním datovém proudu istream_iterator (o něm si povíme více příště). Tento iterátor je, narozdíl od ukazatele, nanejvýš vstupní a není modelem žádného dalšího zjemnění, např. dopředného iterátoru.

Ke vstupnímu iterátoru patří typ prvku a typ rozdílu (vzdálenost mezi iterátory nebo počet prvků v rozsahu).

 

operace	zápis	poznámky
přechod na další prvek	++i	i je dereferencovatelná hodnota; výsledkem může být iterátor na první (neexistující) prvek za koncem kontejneru.
přechod na další prvek	i++	i je dereferencovatelná hodnota, ekvivalentní s ++i
přístup k prvku a přechod na další prvek	*i++	i je dereferencovatelná hodnota. Ekvivalentní s { TYP a = *i; ++i; return a; }.

 

Tab. 2 Operace, které zavádí vstupní iterátor. Všechny tyto operace mají konstantní časovou složitost.

 

Když se vrátíme k úvodní funkci pro výpočet aritmetického průměru, je jistě jasné, že výstupní iterátor je tím nejobecnějším iterátorem, pro který lze danou funkci napsat (aniž by utrpěla efektivita algoritmu). Jedinou možností, jak v C++ tuto skutečnost vyjádřit, je pojmenování šablonového parametru, například takto

 

template <typename VSTUPNI_ITERATOR>

double prumer(VSTUPNI_ITERATOR prvni, VSTUPNI_ITERATOR posledni);

 

nebo ve stylu STL takto

 

template <typename InputIterator>

double prumer(InputIterator prvni, InputIterator posledni);

Výstupní iterátor

Zdálo by se, že výstupní iterátor je opakem vstupního iterátoru, ale situace je poněkud složitější. Jak název napovídá, výstupní iterátor je určen pro ukládání sekvencí hodnot „někam“. Nemusí však podporovat přístup k těmto hodnotám, tj. ani přístup k jejich složkám pomocí operátoru ->, a ani relaci rovnosti (iterátorů). Proto tento koncept nezná typ prvku ani typ rozdílu. Umí však přechod na další prvek.

Zkuste si to představit například jako magnetický pásek (kontejner) a zapisovací hlavu (iterátor). Můžeme zapsat data a posunout pásek na další volnou pozici, ale nemůžeme ty data z pásku číst ani se vrátit zpátky (převinout pásku zpět). Přesně tato představa odpovídá jednomu konkrétnímu modelu, iterátoru na výstupním proudu – třídě ostream_iterator.

Klasický ukazatel je rovněž modelem výstupního iterátoru (i když toho umí mnohem víc).

 

operace	zápis	poznámky
dereference a uložení prvku	*i = a	i je dereferencovatelná hodnota, a je hodnota nějakého (vhodného) typu. Mezi dvěma těmito operacemi musí proběhnout přechod na další prvek.
přechod na místo k uložení dalšího prvku	++i	i je dereferencovatelná hodnota. Předtím muselo proběhnout přiřazení do *i.
přechod na místo k uložení dalšího prvku	i++	i je dereferencovatelná hodnota. Předtím muselo proběhnout přiřazení do *i.
uložení prvku a přechod na místo k uložení dalšího prvku	*i++ = a	i je dereferencovatelná hodnota, a je hodnota nějakého (vhodného) typu. Ekvivalentní s { *i = a; ++i; }.

 

Tab. 3 Operace, které zavádí výstupní iterátor. Všechny mají konstantní časovou složitost.

 

Ještě několik důležitých poznámek k přiřazení *i = a. Za prvé, konstantní časová složitost je vztažena k operaci s iterátorem, vlastní uložení prvku může mít jinou časovou složitost. Za druhé, operátor přiřazení lze ve výstupním iterátoru přetížit tak, aby vracel proxy, neboli zástupnou třídu, která rovněž musí mít přetížený operátor přiřazení. Ptáte se, k čemu je to dobré? Vypadá to jako zbytečná komplikace, ale je v tom skryt velmi silný aparát. Když totiž v proxy přetížíme operátor přiřazení pro různé typy nebo dokonce vytvoříme členskou šablonu operátoru přiřazení parametrizovanou typem výstupní hodnoty, můžeme pomocí výstupního iterátoru s proxy ukládat hodnoty více typů. To proto nemá smysl uvažovat (pevný) typ prvku pro výstupní iterátory. O výstupních iterátorech a proxy toho ještě hodně uslyšíte.

Neméně důležitou vlastností je vztah přiřazení a přechodu na další prvek. Nelze dvakrát zapsat na jedno místo. Mezi dvěma zápisy musí proběhnout přechod na další prvek. Po přechodu na další prvek může následovat zápis (přiřazení) ale nikoli další přechod.

 

// Koncept: Vystupni iterator

*i = 1; ++i; *i = 2;     // OK

*i++ = 1; *i++ = 2;     // OK

*i = 1; *i = 2;     // !! Nelze

*i++ = 1; ++i; *i=2;     // !! Nelze

 

Takhle nějak se chová třída ostream_iterator. Klasické ukazatele vám sice umožní provést všechny čtyři řádky, ale to je tím, že ukazatel je rovněž modelem mnohem pokročilejšího konceptu, než je výstupní iterátor.

Dopředný iterátor

Konečně jsme dospěli k prvnímu „normálnímu“ iterátoru. Dopředný iterátor umožňuje číst i zapisovat prvky, procházet mezi prvky (pouze v jednom směru) a navíc je zaručena možnost opakovaného průchodu (to vstupní ani výstupní iterátor negarantují). Je tedy možné uložit si kopii iterátoru, např. na začátek rozsahu, a projít daný rozsah ještě jednou.

Koncept dopředného iterátoru je zjemněním konceptů vstupního a výstupního iterátoru. Nezavádí však další nové operace; pouze odstraňuje některá omezení. Například při přechodu z i do ++i má iterátor i zaručenu platnost. Je tedy možné se do tohoto místa vrátit a znovu jím projít. To je základní předpoklad pro víceprůchodové algoritmy. Navíc pokud i == j, pak ++i == ++j (To v případě vstupních a výstupních iterátorů neplatilo).

Modelem je zcela jistě klasický ukazatel. Dalším modelem může být třeba iterátor na seznamu (list<T>::iterator), vektoru a jiných STL kontejnerech.

Pokud se vrátíme na začátek k funkci odchylka, zjistíme, že dopředný iterátor je přesně to, co potřebujeme. Vyjádříme tuto skutečnost pojmenováním šablonového parametru

 

template <typename DOPREDNY_ITERATOR>

double odchylka(DOPREDNY_ITERATOR prvni, DOPREDNY_ITERATOR posledni);

 

nebo ve stylu STL

 

template <typename ForwardIterator>

double odchylka(ForwardIterator prvni, ForwardIterator posledni);

Obousměrný iterátor

Nastal čas přidat zpětný chod, tj. umožnit iterátoru přejít jak na následující, tak na předcházející prvek. Koncept obousměrného iterátoru zjemňuje koncept dopředného iterátoru. Přidává jen přetížený operátor -- pro zpětný chod. Přitom operace ++ a -- musí být symetrické, tj. obě dvě následující sekvence

 

++i; --i;

--i; ++i;

 

představují nulovou operace, tj. „jako by se nic nestalo“.

Modelem je opět klasický ukazatel, iterátor na seznamu (standardní třída list je implementována jako obousměrný seznam), nebo iterátor na vektoru.

 

operace	zápis	poznámky
přechod na předchozí prvek	--i	i je dereferencovatelná hodnota.
přechod na předchozí prvek	i--	i je dereferencovatelná hodnota, ekvivalentní s { TYP tmp = i; --i; return tmp }, kde TYP je typ iterátoru.

 

Tab. 4 Operace pro zpětný chod u obousměrného iterátoru (opět konstantní složitost).

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

Dostáváme se k nejpokročilejšímu konceptu iterátoru. Iterátor s náhodným přístupem umí vše co obousměrný iterátor a navíc garantuje přístup v konstantním čase k jakémukoliv prvku v daném rozsahu. Tím pádem umožňuje v konstantním čase posuny vpřed a vzad o libovolný počet kroků. Obousměrný iterátor na to potřebuje lineární čas (lineárně úměrný počtu kroků). To je také jeden z hlavních důvodů zavedení tohoto konceptu. Díky přístupu k libovolnému prvku v konstantním čase můžeme velmi efektivně implementovat třídící algoritmy.

V tabulce 5 je uvedeno, že iterátor s náhodným přístupem podporuje operaci <. Pokud se ale nad tím trochu zamyslíte, zjistíte, že jsou podporovány všechny relace: ==, !=, <, >, <=, >=. Rovnost a nerovnost najdeme v konceptu Equality Comparable, který je iterátorem s náhodným přístupem zjemňován. Operace < je zavedena v iterátoru s náhodným přístupem. Ostatní operace je možné pomocí nich realizovat

 

(i > j) právě tehdy, když (!(i < j) && (i != j))  neboli také (j < i)

(i <= j) právě tehdy, když ((i < j) || (i == j))

(i >= j) právě tehdy, když !(i < j)

 

Modelem iterátoru s náhodným přístupem je klasický ukazatel a stejně tak i iterátory na STL kontejnerech, třídách vector a deque. Iterátor na STL kontejneru list sem už nepatří. Pokud jde o klasický ukazatel, asi vám již došlo, podle čeho byl vytvořen koncept iterátoru s náhodným přístupem. Pojem „rychlá iterátorová aritmetika“ v tabulce 5 je parafrází rychlé adresové aritmetiky klasických ukazatelů.

Pro zajímavost: Klasické ukazatele umí o trošičku víc než požaduje koncept iterátoru s náhodným přístupem. Jazyk C i C++ totiž umožňují napsat:

 

int pole[20];

15[pole] = 3;  // !

 

Řádek označený vykřičníkem znamená totéž co pole[15] = 3; Jde tedy jen o jinou, alternativní syntaxi pro přístup k prvkům. Osobně jsem se s tím setkal pouze v učebnicích jazyků C a C++ a manuálech překladačů, nikdy v reálném kódu.

 

operace	zápis	poznámky
pohyb vpřed	i += n	Jestliže n > 0 je efekt stejný jako při n‑násobném použití ++i; jestliže n < 0,  je efekt stejný jako při n‑násobném použití --i; pro n == 0 jde o nulovou operaci. i je nesingulární, stejně jako n pozic daným směrem (podle znaménka n).
„rychlá iterátorová aritmetika“	i + n, n + i	Oba dva zápisy znamenají totéž: { TYP tmp = i; return tmp += n; }, kde TYP je typ iterátoru.
pohyb vzad	i -= n	Totéž co i += (-n)
„rychlá iterátorová aritmetika“	i – n	Totéž co i + (-n)
čtení libovolného prvku	i[n]	i + n musí být dereferencovatelná hodnota, ekvivalentní s *(i + n).
zápis do libovolného prvku	i[n] = a	i + n musí být dereferencovatelná hodnota, ekvivalentní s *(i + n) = a.
rozdíl iterátorů	j – i	j musí být dosažitelné z i. Výsledkem je hodnota n (typu rozdílu) taková, že j == i + n.
porovnání	i < j	j je dosažitelné z i, nebo j je dosažitelné z i, nebo obojí. Relace < je ostré slabé uspořádání.

 

Tab. 5 Operace iterátoru s náhodným přístupem, všechny s konstantní časovou složitostí. Další, zde neuvedené operace jsou shodné s těmi od obousměrnému iterátoru.

 

objekt	koncept iterátoru
klasické pole	Náhodný přístup
vector	Náhodný přístup
deque	Náhodný přístup
string	Náhodný přístup
list	Náhodný přístup
set, multiset	Obousměrný iterátor
map, multimap	Obousměrný iterátor
vstupní datový proud (istream)	Vstupní iterátor
výstupní datový proud (ostream)	Výstupní iterátor

 

Tab. 6 Jaké iterátory nabízí (nejenom) STL kontejnery.

Co nás ještě čeká

V dalších pokračováních nás čekají modely iterátorů (tj. iterátory jako typy jazyka C++), podpora knihovny STL pro vytváření vlastních iterátorů a zjišťování vlastností iterátorů. Všimneme si také specialit v podobě adaptérů, proxy a iterátorů na vstupně/výstupních datových proudech.

Jaroslav Franěk

Infotipy
[1] Dokumentace STL od SGI: www.sgi.com\technology\stl
[2] J. Franěk, Nebojte se STL, Chip 12/01
[3] J. Franěk, Iterátory I, Chip 01/03
[4] D. Musser et al., STL Tutorial and Reference Guide, 2001
[5] N. Josuttis, The C++ Standard Library, 1999
[6] E. Gamma et al., Design Patterns, 1995
[7] zdrojový kód v rubrice Chip Plus na Chip CD