Iterátory III. Značky, rysy, adaptéry...

Minule jsme si představili koncepty (metatypy) iterátorů. Dnes se budeme bavit převážně o modelech těchto konceptů, tedy z pohledu C++ o typech a jejich vlastnostech.

Značkování iterátorů

Iterátorem může být klasický ukazatel a stejně tak i třída, která implementuje požadované rozhranní (s požadovanou sémantikou). Prostředky C++ však neumožňují pracovat přímo s koncepty; název konceptu lze použít jako jméno šablonového parametru a tím to končí (Ještě lze s pomocí jistých triků testovat, zda daný typ je modelem konceptu, ale pouze na syntaktické úrovni).

Pokud tedy chceme vědět, zda daný iterátor (typ) je vstupní, dopředný či s náhodným přístupem musíme si je označkovat. Každému iterátoru přiřadíme právě jednu značku, která bude označovat ten nejlepší koncept, jehož je iterátor modelem. Značky nebudou nic jiného, než prázdné C++ třídy. Jednomu konceptu odpovídá jeden datový typ.

V STL jsou tyto značky definovány v hlavičkovém souboru <iterator>. Objektová hierarchie těchto značek odpovídá přibližně hierarchii příslušných konceptů, viz Obr. 1. Vlastní definice těchto značek vypadají takto (jeden příklad za všechny)

 

class forward_iterator_tag

   : public input_iterator_tag

{};

 

 

 

Obr. 1 Objektová hierarchie značek iterátorů.

 

K čemu je značkování dobré? Stačí si uvědomit, že některé algoritmy fungují efektivněji, když mají k dispozici mocnější iterátory. Například minule zmiňované třídění by fungovalo i s dopřednými iterátory, ale teprve když použijeme iterátory s náhodným přístupem dostaneme efektivní algoritmus. Když tohle spojíme s přetěžováním funkcí, můžeme dát třídící funkci na výběr mezi obecnějším iterátorem a málo efektivním algoritmem nebo specializovaným iterátorem a efektivním algoritmem.

Nejlépe bude uvést si konkrétní příklad. Tentokrát půjde o obrácení pořadí prvků v posloupnosti (první bude poslední atd.). Zde je možné použít obousměrné iterátory, ale iterátory s náhodným přístupem dávají efektivnější algoritmus. Nejprve napíšeme funkci pro obousměrné iterátory a pak pro iterátory s náhodným přístupem:

 

template <typename BidirectionalIterator>

void obrat_poradi(BidirectionalIterator prvni,

      BidirectionalIterator posledni,

      bidirectional_iterator_tag)

{

   while (true)

   {

      if ( (prvni == posledni) || (prvni == --posledni) )

         return;

      else

         std::iter_swap(prvni++, posledni);

   }

}

 

template <typename RandomAccessIterator>

void obrat_poradi(RandomAccessIterator prvni,

      RandomAccessIterator posledni,

      random_access_iterator_tag)

{

   while (prvni < posledni) std::iter_swap(prvni++, --posledni);

 

}

 

Poslední třetí parametr představuje značku iterátoru. Je nepojmenovaný, protože jeho instance se v těle funkce vůbec nepoužije. Slouží pouze překladači při hledání vhodné přetížené funkce. Na doplněnou: STL funkce iter_swap, ležící v prostoru jmen std, provede prohození hodnot, na něž odkazují její dva parametry – iterátory.

Pořád tomu ještě něco chybí – dispečer, tedy řídící funkce, která se postará o zavolání jedné z předchozích funkcí podle toho, jaké iterátory dostane na vstupu. A co chybí dispečerovi? Možnost zeptat se libovolného iterátoru na jeho značku. Potřebujeme tedy třídu rysů (template traits class), která bude implementovat mapování libovolného typu iterátoru na příslušnou značku. STL pro tento účel poskytuje šablonovou třídu rysů iterator_traits.

Třída rysů iterátorů

Šablonová třída rysů iterátorů, iterator_traits, je definována v hlavičkovém souboru <iterator>. Poskytuje informace nejenom o značce iterátoru, ale i o typu prvku, typu rozdílu iterátorů, typu ukazatele na prvek a typu reference na prvek. A to všechno pro libovolný iterátor, který je jejím šablonovým argumentem. Definice této třídy rysů je následující (jednotlivé definice typů jsou uvedeny v pořadí, v jakém byly výše vyjmenovány)

 

template <typename Iterator>

struct iterator_traits

{

   typedef typename

      Iterator::iterator_category iterator_category;

   typedef typename

      Iterator::value_type value_type;

   typedef typename

      Iterator::difference_type difference_type;

   typedef typename

      Iterator::pointer pointer;

   typedef typename

      Iterator::reference reference;

};

 

Struktura každé z oněch definicí typu je následující: Klíčové slovo typedef uvádí vnořenou definici typu, následuje klíčové slovo typename, které překladači napoví, že následující výraz Iterator::iterator_category je označením vnořeného typu v typu Iterator. Jako poslední se objeví jméno definovaného typu, tj. iterator_category.

Tato definice předpokládá, že iterátor (typ) je třída a má vnořené definice typů. My však z minula víme, že klasický ukazatel je rovněž iterátor. Co s tím? Ukazatel přece nemůže mít vnořené definice typů. Naštěstí jsou tu pokročilé vlastnosti C++, konkrétně částečná specializace šablony třídy. Nic nám tedy nebrání napsat specializaci pro klasické ukazatele

 

template <typename T>

struct iterator_traits<T *>

{

   typedef

      random_access_iterator_tag iterator_category;

   typedef ptrdiff_t  difference_type;

   typedef T  value_type;

   typedef T *  pointer;

   typedef T & reference;

};

 

template <typename T>

struct iterator_traits<const T *>

{ /* analogicky... */ };

 

Zde jasně říkáme, že ukazatel je iterátor s náhodným přístupem. Rozdíl dvou ukazatelů je v C++ typu ptrdiff_t. Rozhodnutí, zda použít nespecializovanou či specializovanou šablonu, je věcí překladače; o to se vůbec nemusíme starat. Nyní už můžeme doplnit dvě dříve definované funkce o jejich dispečera

 

template <typename BidirectionalIterator>

void obrat_poradi(BidirectionalIterator prvni,

      BidirectionalIterator posledni)

{

   obrat_poradi(prvni, posledni,

      iterator_traits<BidirectionalIterator>::iterator_category());

}

 

Nenechte se zmást, že se všechny funkce jmenují stejně – o rozlišení se postará překladač a přetěžování funkcí. Jak známo, tam kde funguje koncept, funguje i jeho zjemnění. Takže tuto funkci můžeme volat také pro iterátory s náhodným přístupem, neboť tento koncept zjemňuje koncept obousměrného iterátoru (který je zde explicitně vyžadován). Rozlišení, o jaký koncept iterátoru se jedná, je uskutečněno uvnitř funkce, při použití třídy rysů. Vyžaduje to však menší vysvětlení. Výraz

 

iterator_traits<BidirectionalIterator>::iterator_category

 

představuje typ značky iterátoru. Například

 

iterator_traits<int *>::iterator_category

 

znamená, jak jistě uhodnete, typ random_access_iterator_tag. Ty prázdné závorky za označením typu z toho udělají (nepojmenovanou) instanci. Jinými slovy: jde o volání implicitního konstruktoru.

Zdatnější programátoři, kteří ovládají šablonové metaprogramování (viz článek [6]), by to zvládli i bez té nepojmenované instance. Nepoužilo by se přetěžování funkcí, ale meta konstrukce, viz ukázka v [10].

Ještě jeden zajímavý příklad. Vzpomeňme na výše zmíněnou funkci iter_swap. Jejím úkolem je prohodit dva prvky, na které odkazují její dva parametry, iterátory. K prohození prvků potřebujeme vytvořit pomocnou instanci prvku, ale k tomu potřebuje znát typ prvku. Není nic jednoduššího, než se zeptat iterátoru na jeho příslušný typ prvku pomocí třídy iterator_traits.

 

template <typename ForwardIterator1,

          typename ForwardIterator2>

inline void iter_swap(ForwardIterator1 a,

          ForwardIterator2 b)

{

   iterator_traits<ForwardIterator1>::value_type tmp(*a);

   *a = *b;

   *b = tmp;   

}

Specifika výstupního iterátoru

Z minula víme, že pro výstupní iterátory nemá smysl definovat typ prvku (value_type) ani typ rozdílu (difference_type). V STL se to vyjádří tak, že se použije typ void. Takže třída iterator_traits bude mít pro jakýkoliv výstupní iterátor obsah ekvivalentní s

 

{

   typedef output_iterator_tag iterator_category;

   typedef void difference_type;

   typedef void value_type;

   typedef void pointer;

   typedef void reference;

};

Píšeme iterátor kompatibilní s STL

Když budeme psát vlastní iterátor, bude to zcela jistě třída. Pro kompatibilitu s STL budeme muset zajistit dostupnost rysů našeho iterátoru. Zde existuje několik možností, jak toho dosáhnout.

Řekněme, že jsme vytvořili jistý kontejner, třeba jednosměrný seznam, a zároveň tvoříme i iterátor na tomto kontejneru. Je jistě jasné, že jednosměrný seznam nemůže nabídnout více než dopředný iterátor. Zde je kostra definice našeho iterátoru

 

template <typename T> class cJednosmerka

{

   // ...

};

 

Předpokládejme, že všechny vlastnosti, které vyžaduje koncept dopředného iterátoru, jsou již správně implementovány. Nyní si ukážeme, jak z něj udělat iterátor kompatibilní s STL, tj. uvedeme do života rysy tohoto iterátoru.

Specializace třídy rysů

Jednou z možností je použití částečné specializace šablony třídy rysů iterator_traits, tak jako v případě ukazatelů. Jenže zatímco pro ukazatel to byla jediná možnost, zde je to spíše exces, vyžadující navíc ty nejpokročilejší vlastnosti (které bohužel některé překladače ještě neznají) i znalosti C++.

 

template <typename T>

struct iterator_traits<cJednosmerka<T> >

{

   typedef forward_iterator_tag iterator_category;

   typedef ptrdiff_t  difference_type;

   typedef T  value_type;

   typedef T *  pointer;

   typedef T & reference;

};

Ruční vepsání definic typů

Další možností je „ruční práce“. Prostě do naší třídy vepíšeme potřebné definice typů. Jednoduché a snad i přehledné.

 

template <typename T> class cJednosmerka

{

   // ...

public:

   typedef forward_iterator_tag iterator_category;

   typedef ptrdiff_t  difference_type;

   typedef T  value_type;

   typedef T *  pointer;

   typedef T & reference;

};

Bázová třída iterator

Pokud si vzpomenete na článek [5], na to jak jsme z neadaptabilních funktorů dělali adaptabilní, víte, že jsme měli v STL k dispozici dvě bázové třídy, které sice samy o sobě nebyly funktory, ale poskytovaly potřebné definice typů. Stejná situace je i u iterátorů. Máme k dispozici bázovou třídu iterator, která sice sama o sobě není iterátorem, ale poskytuje potřebné vnořené definice typů. Najdeme ji v hlavičkovém souboru <iterator>. Název je možná zavádějící, ale s tím se musíme smířit. Definice vypadá takto

 

template <typename Category,

          typename T,

          typename Distance = ptrdiff_t,

          typename Pointer = T*,

          typename Reference = T&>

struct iterator

{

   typedef Category iterator_category;

   typedef T value_type;

   typedef Distance difference_type;

   typedef Pointer pointer;

   typedef Reference reference;

};

 

S použitím této třídy můžeme aktivovat rysy našeho iterátoru tím, že ho odvodíme jako potomka

 

template <typename T> class cJednosmerka

   : public iterator<forward_iterator_tag, T>

{

   // ...

};

 

Všimněte si, že jsme zadali pouze první dva šablonové argumenty. Ostatní mají své implicitní hodnoty, které ve většině případů není nutno měnit. Toto je preferovaný způsob.

Specifika výstupního iterátoru

Jak již víme, výstupní iterátor je poněkud zvláštní – většina jemu asociovaných typů je void. Proto mohou mít všechny výstupní iterátory jednoho předka

 

class cJakykolivVystupniIterator

   : public iterator<output_iterator_tag,

                     void, void, void, void>

{

   // ...

};

 

Toto zajistí, že třída rysů iterator_traits bude obsahovat ty správné údaje (viz výše).

Pomocné funkce

Pro základní práci s iterátory poskytuje STL dvě funkce: advance pro posun iterátoru o daný počet kroků (vpřed nebo i vzad podle konceptu iterátoru), distance pro zjištění vzdálenosti mezi dvěma iterátory (jeden musí být dosažitelný z druhého).

 

template <typename InputIterator, typename Distance>

void advance(InputIterator& i, Distance n);

 

template<typename InputIterator>

typename iterator_traits<InputIterator>::difference_type

distance(InputIterator first, InputIterator last);

 

Tyto funkce jsou implementovány podobně jako naše „dispečerská“ funkce výše. To znamená, že dané funkce vždy poskytují co nejefektivnější algoritmus pro dané typy parametrů. Například pro iterátory s náhodným přístupem obě metody pracují v konstantním čase, zatímco pro ostatní iterátory pracují v lineárním čase (úměrném počtu kroků). Takže například

 

cJednosmerka i;  // + nějaká inicializace

cJednosmerka i2;  // + nějaká inicializace

advance(i, 10);

int vzdalenost = distance(i, i2);

 

znamená, že se pro iterátor i desetkrát zavolá operátor ++ a pak se ještě provede jistý počet iterací s kopií iterátoru i, dokud se nedosáhne i2 (jinak totiž vzdálenost určit nejde). Kdežto

 

int j[20];  // + inicializace

int * j2 = j + 20;

advance(j, 10);

int do_konce = distance(j, j2);

 

je ekvivalentní operacím

 

j += 10;

int do_konce = j2 – j;

 

To jen díky tomu, že ukazatel je iterátor s náhodným přístupem.

Poučení: Nepodceňujte tyto funkce. Při každém přesunu iterátoru o větší počet kroků než 1 použijte funkci advance. Pro zjištění vzdálenosti mezi dvěma (dosažitelnými) iterátory vždy použijte funkci distance.

Zpětný iterátor (adaptér)

Většina STL algoritmů pracuje s jistým rozsahem prvků stylem „od začátku do konce“, tj. používají většinou operátor ++ k přechodu mezi prvky. Někdy však může být žádoucí obrátit sled na „od konce k začátku“. Abychom nemuseli přepisovat kód algoritmů, nabízí STL adaptér iterátoru, který obrátí sled procházení: Jeho operátor ++ bude vlastně odpovídat operátoru --adaptovaného iterátoru a obráceně. Zde je deklarace (hlavičkový soubor <iterator>)

 

template <typename Iterator>

class reverse_iterator

: public iterator

         <

            typename iterator_traits<Iterator>::iterator_category,

            typename iterator_traits<Iterator>::value_type,

            typename iterator_traits<Iterator>::difference_type,

            typename iterator_traits<Iterator>::pointer,

            typename iterator_traits<Iterator>::reference

         >

{

   // ...

   typedef Iterator iterator_type;

   explicit reverse_iterator(Iterator x);

   Iterator base() const;

   // ...

};

 

Je jasné, že tento adaptér nelze použít na jednosměrný iterátor. Takže šablonovým argumentem může být obousměrný iterátor nebo iterátor s náhodným přístupem. Pokud nahlédnete do hlavičkového souboru s definicí tohoto adaptéru, zjistíte, že má všechny metody odpovídající konceptu iterátoru s náhodným přístupem; tedy například

 

reference operator[](difference_type n) const;

 

pro přístup k libovolnému prvku v konstantním čase. Ale co když adaptujeme pouze obousměrný iterátor? Ten přece takovou operaci nezná! Je to v pořádku? Ano je. Díky pokročilým vlastnostem C++, konkrétně implicitnímu vytváření instancí šablon: Pokud metodu použiji, vygeneruje se automaticky potřebná instance, ale pokud takovou metodu nepoužiji, pak jako by nebyla (nevytvoří se instance). To znamená, že bude všechno v pořádku, dokud se nepokusím použít něco, co pro obousměrné iterátory nefunguje. Takže pokud adaptujeme obousměrné iterátory, je adaptér modelem obousměrného iterátoru. A pokud adaptujeme iterátor s náhodným přístupem je výsledný adaptér modelem iterátoru s náhodným přístupem.

Ještě je zde ale menší problém s určením rozsahu pro tento zpětný iterátor. Dejme tomu, že chceme projít celý kontejner. Začínáme na posledním prvku, který do rozsahu patří, a tím pádem by druhý konec rozsahu měl být omezen prvním neexistujícím prvkem před prvním prvkem kontejneru. Nic takového však norma nedovoluje (za kontejnerem ano, ale před ne). Proto je použita finta. Rozsah začíná na prvním prvku za posledním a končí na prvním prvku, ale zpětný iterátor odkazuje „o jeden prvek“, viz červená šipka na Obr. 2. Přesněji by se to nechalo zapsat takto

 

&*(reverse_iterator(i)) == &*(i - 1)

 

Každý kontejner podporující obousměrné iterátory poskytuje vnořené definice typů reverse_iterator a const_reverse_iterator, a také metody rbegin() a rend(), které vracejí iterátory těchto typů, viz Obr. 2.

 

 

Obr. 2 Zpětné iterátory rend(), rbegin() a j. Plná šipka označuje element, který získáme použitím operátoru dereferencování, iterátory rend() a end() nelze dereferencovat.

 

Adaptér reverse_iterator obsahuje několik novinek oproti iterátorům. Tyto jsou vypsány v deklaraci v úvodu této sekce. Vnořený typ iterator_type umožňuje zeptat se na typ adaptovaného iterátoru. Explicitní jednoparametrický konstruktor z iterátoru udělá zpětný iterátor, viz j = reverse_iterator(i) na Obr.2. Metoda base() vrací iterátor původního, adaptovaného typu, který odpovídá aktuální pozici zpětného iterátoru. Toho lze využít při práci s kontejnery například v následující situaci: S kontejnerem pracujeme pomocí zpětných iterátorů, hledáme třeba výskyt jistého prvku od konce kontejneru, a pak se rozhodneme tento prvek z kontejneru odstranit. Metoda kontejneru erase však nevezme zpětný iterátor jako parametr, proto pomocí metody base() zpětného iterátoru provedeme konverzi a pak už erase bude fungovat.

Příklady užití zpětných iterátorů najdete v [10]. Zde jen krátká ukázka toho jak vypsat pozpátku obsah pole na obrazovku v textovém režimu (každý prvek na vlastní řádek)

 

int pole[5] = { 1, 2, 3, 4, 5 };

copy(reverse_iterator<int *>(pole + 5), // rbegin

     reverse_iterator<int *>(pole),     // rend

     ostream_iterator(cout, “\n“));

 

Mimochodem, víte jak co nejjednodušeji s použitím STL napsat funkci, která zjistí, zda dané slovo (řetězec) je palindrom? Připomeňme, že palindrom je takové slovo, které se i pozpátku čte stejně, např. oko, krk, level, atd. Deklarace bude vypadat takto

 

bool je_palindrom(const string & slovo);

 

Zkuste na to přijít (Pro jednoduchost předpokládejte, že slovo je skutečně jedno slovo a neobsahuje mezery.). Řešení se dozvíte v příštím díle.

Dokončení příště

Dnes se ještě nedostalo na vkládací iterátory a iterátory na vstupně/výstupních proudech. Budeme se jim věnovat příště.

Jaroslav Franěk

Infotipy
[1] Dokumentace STL od SGI: www.sgi.com\technology\stl
[2] J. Franěk, Iteratory I, Chip 01/03
[3] J. Franěk, Iteratory II, Chip 01/03
[4] J. Franěk, Nebojte se STL, Chip 12/01
[5] J. Franěk, Jak se na funktor volá II, Chip 02/02
[6] J. Franěk, Dřinu nechte překladači!, Chip 01/01
[7] D. Musser et al., STL Tutorial and Reference Guide, 2001
[8] N. Josuttis, The C++ Standard Library, 1999
[9] S. Meyers, Effective STL, 2001
[10] zdrojový kód v rubrice Chip Plus na Chip CD