Minule jste dostali na rozmyšlenou, jak co nejjednodušeji s pomocí prostředků STL napsat funkci, která otestuje, zda dané slovo je či není palindrom (tj. od začátku i od konce se čte stejně). Zde je elegantní řešení
bool
je_palindrom(const string & slovo)
{
return equal(slovo.begin(), slovo.end(), slovo.rbegin());
}
Začneme trochu netradičně, popisem funkce copy. Tato funkce vypadá následovně
template<typename InputIterator,
typename
OutputIterator>
OutputIterator copy(InputIterator prvni, InputIterator
posledni,
OutputIterator
kam)
{
while ( prvni != posledni ) *kam++ = *prvni++;
return kam;
}
Tato funkce kopíruje data z rozsahu [prvni, posledni), do rozsahu [kam, kam + (posledni - prvni)). Zkusme si teď jeden příklad – chceme provést spojení dvou vektorů tím, že jeden nakopírujeme za druhý
vector<int>
v; // + vložení nějakých prvků
vector<int>
w; // + vložení nějakých prvků
// spojení: k w prikopirujeme v
copy(v.begin(), v.end(), w.end()); // !!! CHYBA
Pokud jste už někdy něco takového zkusili, určitě vám to nefungovalo správně. Proč? Protože funkce copy nepracuje s kontejnery (v našem případě jde o třídu vector), ale s iterátory na těchto kontejnerech. Nemá tudíž kredit k přidávání prvků do kontejneru – a o to jsme se tu pokusili.
Jinými slovy, funkce copy funguje v takzvaném přepisovacím (overwrite) režimu, to znamená, že přepisuje již existující prvky novými hodnotami. Za koncem kontejneru, počínaje iterátorem end(), již žádné prvky nejsou, a proto příkaz označený třemi vykřičníky může způsobit i havárii programu...
Existuje však způsob, jak přinutit funkci copy k práci v takzvaném vkládacím (insert) režimu. Musíme však použít speciální výstupní iterátory – vkládací iterátory.
Jak taková věc funguje? Předem si musíme uvědomit, že jde o výstupní iterátory (viz [3]), takže množina podporovaných operací je značně omezena. Za druhé, jde nám o to, převést příkaz
*kam++ = neco;
na volání metody kontejneru pro vložení prvku. Může jít o metodu insert, push_back, nebo push_front podle toho, jestli chceme vkládat prvky kamkoli, na konci, nebo na začátku kontejneru. Popíšeme si zde konstrukci výstupního iterátoru, který používá metodu insert. Je jasné, že takový iterátor musí uchovávat odkaz na kontejner a iterátor, který určuje, kam se budou vkládat prvky. S použitím standardu C++, sekce 24.4.2.5 :
template <typename Container> // (1)
class insert_iterator
: public iterator<output_iterator_tag,
void, void, void, void> // (2)
{
protected:
Container *
container; // (3)
typename Container::iterator
iter; // (4)
public:
typedef Container
container_type; // (5)
insert_iterator(Container
& x,
typename
Container::iterator i); // (6)
insert_iterator<Container>
&
operator
=(typename Container::const_reference value);
// (7)
insert_iterator<Container>
& operator *(); // (8)
// ...
};
(1) Metoda insert je povinnou součástí většiny kontejnerů, proto je rozumné parametrizovat vkládací iterátor typem kontejneru. O rozdílech mezi vkládáním do různých typů kontejnerů pohovoříme za chvíli.
(2) Jde o výstupní iterátor. Rysy iterátoru aktivujeme odvozením iterátoru od třídy iterator. Více viz [4].
(3) Odkaz na kontejner.
(4) Iterátor, který určuje, kam se bude vkládat. Typ iterátoru získáme tak, že se zeptáme kontejneru na jeho typ iterátoru tj. Container::iterator. Klíčové slovo typename je zde nutné – napoví překladači, že jde o typ.
(5) Abychom se mohli vkládacího iterátoru zeptat na typ kontejneru, do kterého vkládá, je k dispozici tato vnořená definice typu.
(6) Konstruktor: zadáme instanci kontejneru a nesingulární iterátor (instanci) na tomto kontejneru. Slouží k inicializaci atributů (3) a (4).
Nyní to nejdůležitější: Jak implementovat operátory (7) a (8)? Jak víte z článku [3], operátor dereferencování výstupního iterátoru může vrátit proxy, tj. zástupnou třídu, jejíž přetížený operátor = se postará o uložení prvku. A o to tu jde. Tento operátor vrátí proxy, akorát že pro jednoduchost touto proxy bude třída insert_iterator osobně (to je ale detail implementace, nikoli standardem nařízené chování...). Takže tělo operátoru (8) bude obsahovat jediný příkaz
return *this;
Teď je jasné, že operátor (7) se musí postarat o vložení prvku do kontejneru a aktualizaci atributu iter, neboť vložením prvku může tento iterátor ztratit platnost (např. kvůli re-alokaci). Jeho tělo bude vypadat takto
iter = container->insert(iter, value); // (a)
++iter; // (b)
return *this;
(a) Uložíme hodnotu value do kontejneru na pozici, určenou iterátorem iter pomocí metody insert. Přitom může dojít k re-alokaci, čímž by původní iterátor iter ztratil platnost. Naštěstí metoda insert chytře vrací iterátor na výslednou pozici, kam je uložena hodnota.
(b) Metoda insert ukládá nové prvky do kontejneru před prvek určený jako místo vkládání. Abychom zajistili toto chování i pro vkládací iterátory, musíme postrčit iter o jeden prvek dopředu, tak aby odkazoval na původní prvek, před který se mají vkládat nové.
Zbývají ještě oba operátory ++. Jelikož už operátory (7) a (8) vykryly všechnu potřebnou činnost, budou operátory ++ hrát mrtvého brouka: žádný přechod na další prvek, jen
return *this;
Zbývá ještě oddiskutovat použití metody insert u různých kontejnerů. Stejně jako koncepty iterátorů máme i koncepty kontejnerů, viz článek [5]. Požadavky vkládacího iterátoru na typ kontejneru splňují dva koncepty (a samozřejmě všechny ostatní, které je zjemňují): posloupnost (Sequence) a setříděný asociativní kontejner (Sorted Associative Container), každý však po svém. Zatímco u posloupností se nově vkládané hodnoty vždy dostanou na (před) místo, které je určeno iterátorem iter, u setříděných asociativních kontejnerů to neplatí. Je to celkem pochopitelné: Vkládaná hodnota musí padnout tam, kam patří podle třídícího kritéria. Parametr iter tam slouží pouze jako pomůcka (kam asi by to mohlo padnout), ale na výsledném umístění hodnoty nemá vliv.
Nyní zpět k funkci copy. S použitím vkládacího iterátoru bychom mohli napsat (a tentokrát už to bude v pořádku)
// spojení: k w prikopirujeme v
copy(v.begin(), v.end(),
insert_iterator<vector<int>
>(w, w.end()));
Ale pořád je to moc složité. Naštěstí, stejně jako u funktorů, standard definuje příslušnou vytvořující funkci, která s využitím pokročilých vlastností C++ vytvoří potřebnou instanci vkládacího iterátoru jen na základě typů argumentů.
template <typename Container, typename Iterator>
inline insert_iterator<Container>
inserter(Container& x, Iterator i)
{
return insert_iterator<Container>(x,
typename Container::iterator(i));
}
Vytvořující funkce inserter se postará o vytvoření instance vkládacího iterátoru. Rovněž se pokusí o konverzi iterátoru i na požadovaný typ, kterým je Container::iterator. Pomocí vytvořující funkce zjednodušíme náš kód na
// spojení: k w prikopirujeme v
copy(v.begin(), v.end(), inserter(w, w.end()));
Použili jsme obecný vkládací iterátor ačkoli nevkládáme prvky doprostřed, ale na konec posloupnosti. Proto bychom mohli použít vkládací iterátor založený na metodě push_back. Princip je stejný jako u třídy insert_iterator, ale s těmito rozdíly:
Jelikož třída vektor je modelem konceptu Back Insertion Sequence a podporuje operaci push_back, můžeme psát (rovnou s využitím vytvořující funkce)
// spojení: k w prikopirujeme v
copy(v.begin(), v.end(), back_inserter(w));
// OK
Obdobně jako na konec, můžeme vkládat prvky na začátek posloupnosti metodou push_front. Oproti vkládání na konec jsou tu tyto rozdíly
Jeden důležitý rozdíl nakonec: Zatímco v případě vkládání na konec nebyl rozdíl mezi použitím obecného vkládacího iterátoru (insert_iterator) a iterátoru back_insert_iterator, u vkládání na začátek posloupnosti to neplatí. Než začnete číst další řádky, zkuste se zamyslet proč tomu tak je.
(Nejen) pro ty netrpělivé, zde je vysvětlení: Iterátor front_insert_iterator ukládá prvky, tak jak přijdou, vždy na začátek, takže jejich výsledné pořadí v posloupnosti je obrácené. Při použití vkládacího iterátoru insert_iterator si tento pamatuje iterátor na původní první prvek v posloupnosti po celou dobu vkládání. To znamená, že pořadí vložených prvků v posloupnosti bude odpovídat pořadí, v jakém byly vloženy.
Většina STL generických algoritmů pracuje v přepisovacím (overwrite) režimu. To proto, že při použití iterátorů, které jim nabídnou kontejnery, tyto algoritmy nemají kredit k modifikaci kontejneru (tj. počtu prvků v kontejneru apod.) ale pouze k modifikaci prvků, na které odkazují iterátory. STL však nabízí prostředek, který umožní algoritmům pracovat ve vkládacím (insert) režimu – vkládací iterátory. Pomocí nich je možné do kontejnerů přidávat nové prvky.
Na závěr povídání o vkládacích iterátorech se sluší říct, že je i jejich vytvořující funkce zpřístupníme vložením standardního hlavičkového souboru <iterator>. Pro používání vkládacích iterátorů si stačí pamatovat jen ty tři vytvořující funkce.
A ještě jedna rada: Naše použití funkce copy k připojení jednoho vektoru za druhý bylo zvoleno kvůli vhodné demonstraci funkce vkládacích iterátorů. Jinak (a lépe) lze tuto akci uskutečnit pomocí metody insert
w.insert(v.begin(), v.end());
Jsou ale situace, kde funkce copy a vkládací iterátory představují elegantní řešení. Jeden takový příklad poznáme záhy, až se trochu seznámíme s iterátory na vstupně/výstupních datových proudech.
Datové proudy jazyka C++ (iostreams) představují další zajímavou možnost aplikace iterátorů. Jedním z důvodů zavedení konceptů vstupního a výstupního iterátoru je právě možnost dát STL generickým algoritmům šanci pracovat přímo s datovými proudy.
Základní myšlenkou iterátoru na vstupním proudu je převedení operace přístupu k prvku s přechodem na další prvek *i++ na operaci čtení z datového proudu operátorem >>. Je jasné, že takový iterátor bude modelem (nejvýše) vstupního iterátoru. To plyne z toho, že již přečtený prvek nemůže být znovu čten (byl již z datového proudu extrahován), a tudíž tento iterátor neumožňuje vícenásobný průchod.
template <typename T, // (1)
typename
charT = char, // (2)
typename
traits = char_traits<charT>, //
(3)
typename
Distance = ptrdiff_t> // (4)
class istream_iterator
// (5)
: public iterator<input_iterator_tag,
T, // (6)
Distance,
const T*, const T&>
{
// ... uvedeny
jen specifické složky
public:
typedef charT
char_type; // (7)
typedef traits
traits_type; // (8)
typedef basic_istream<charT,traits>
istream_type; // (9)
istream_iterator();
// (10)
istream_iterator(istream_type&
s); // (11)
};
(1) Typ vstupních dat, aneb jak má iterátor interpretovat vstupní data. Pokud chceme z proudu číst celá čísla, bude T například int.
(2) Typ znaku datového proudu. Obvykle char; pro znaky Unicode by to byl wchar_t.
(3) Třída rysů popisující základní typy a operace pro práci se znaky a s posloupností znaků. Obvykle vystačíme s uvedeným implicitním argumentem.
(4) Typ rozdílu iterátorů.
(5) Jméno třídy
(6) Odvozením od třídy iterator aktivujeme rysy iterátoru (třída iterator_traits).
(7) Definice typu, která umožňuje zeptat se iterátoru na typ znaku datového proudu.
(8) To samé pro typ třídy rysů znaku datového proudu.
(9) To samé pro typ datového proudu.
(10) Implicitní konstruktor. Vytvoří iterátor, který se bude tvářit jako konec datového proudu (end-of-stream). To má význam při zadávání rozsahu čtení.
(11) Konstruktor, kterým se iterátor „připojí“ k datovému proudu.
Jak tento iterátor funguje? Zkusme si jednoduchý vstup z příkazové řádky. Nejdříve vytvoříme instanci iterátoru na vstupním datovém proudu cin a pak přečteme dvě celá čísla.
istream_iterator<int> i(cin);
int prvni
= *i++;
int druhé
= *i++;
Jednotlivé metody iterátoru si práci rozdělily takto: konstruktor vytvoří instanci iterátoru, připojí ji ke standardnímu vstupnímu proudu cin a načte pomocí operátoru >> první prvek do interního atributu. Operátor dereferencování * vrátí prvek uložený v interním atributu. Operátor ++ provede přechod na další prvek, tj. načte pomocí operátoru >> další prvek do interního atributu. Prvky jsou v datovém proudu odděleny takzvanými bílými znaky (jeden nebo více mezer, tabulátorů, znaků konce řádku apod.).
A nyní již dříve slíbené elegantní použití vkládacích iterátorů. Načteme do vektoru data z datového proudu (jde to i ze souboru, ale my se zde omezíme na standardní vstupní proud).
vector<int> v;
copy(istream_iterator<int>(cin),
istream_iterator<int>(),
back_inserter(v));
Všimněte si zadání vstupního rozsahu. Předem nevíme kolik tam bude prvků. Využijeme ale jedné vlastnosti těchto iterátorů: pokud se čtení nezdaří z jakéhokoliv důvodu (např. konec souboru), pak se iterátor začne tvářit jako iterátor na konec datového proudu, což znamená ukončení iterování. Další vlastností je nemožnost zadat rozsah jinak než od začátku do konce datového proudu.
Iterátor na výstupním datovém proudu je založen na myšlence převedení operace zápisu prvku *i = a na zápis do datového proudu pomocí operátoru <<. Stejně jako v předchozím případě, tento iterátor není víceprůchodový, tedy je modelem pouze konceptu výstupního iterátoru.
template <typename T,
typename
charT = char,
typename
traits = char_traits<charT> >
class ostream_iterator
// (1)
: public iterator<output_iterator_tag,
// (2)
void,
void, void, void>
{
public:
// ... uvedeny
jen specifické složky
ostream_iterator(ostream_type&
s); // (3)
ostream_iterator(ostream_type&
s, const charT * delimiter); // (4)
ostream_iterator<T,charT,traits>&
operator=(const T& value); //
(5)
};
(1) Jméno třídy.
(2) Odvozením od třídy iterator aktivujeme rysy iterátoru (třída iterator_traits). O zvláštnostech rysů výstupních iterátorů jsme hovořili minule.
(3) Konstruktor, kterým se iterátor „připojí“ k datovému proudu. Zapisované prvky nebudou nijak odděleny.
(4) Konstruktor, kterým se iterátor „připojí“ k datovému proudu. Zároveň se nastaví oddělovač (řetězec), který se vypíše po každém zapsaném prvku.
(5) Operátor zápisu prvku. Tentokrát, na rozdíl od vstupního iterátoru, má tento na starosti výstup prvku a případně i o výstup oddělovacího řetězce, pokud byl tento zadán v konstruktoru (4).
Ostatní operátory (++, *) nedělají nic jiného než pouze vrací *this. A jak to funguje? Pokud jste sledovali zdrojové kódy na Chip CD, jistě víte, jak vypsat na obrazovku (nebo i do souboru) pole prvků bez napsání smyčky
int pole[5] = { 1, 1, 2, 3, 5 };
copy(pole,
pole + 5, ostream_iterator<int>(cout, “ “));
Vypisujeme prvky pole do standardního výstupního proudu cout. Prvky budou odděleny mezerou.
Pokud potřebujeme neformátovaný vstup a výstup znak po znaku, můžeme použít iterátory na vyrovnávací paměti datových proudů. I zde musíme rozlišit vstup a výstup. V následujících výpisech tříd uvádíme jen ty složky, které vyžadují vysvětlení.
template<typename charT,
typename
traits = char_traits<charT> >
class istreambuf_iterator
: public iterator<input_iterator_tag,
charT,
typename
traits::off_type,
charT
*, charT &>
{
// ... uvedeny
jen specifické složky
public:
istreambuf_iterator()
// (1)
istreambuf_iterator(istream_type
& s) throw(); // (2)
istreambuf_iterator(streambuf_type
* s) throw(); // (3)
bool equal(istreambuf_iterator
& j); // (5)
};
(1) Konstruktor, který vytvoří iterátor na konec datového proudu.
(2) Konstruktor, který se připojí k vyrovnávací paměti datového proudu. V případě, že datový proud je prázdný vytvoří iterátor na konec proudu.
(3) To samé jako (2), ale s tím, že zadáme přímo vyrovnávací paměť.
(4) Rovnost dvou iterátorů typu istreambuf_iterator: rovnají se když jsou buď oba iterátorem na konec proudu, nebo ani jeden není iterátorem na konec proudu.
Narozdíl od formátovaného vstupu, zde konstruktor nenačte žádný znak. O načítání znaků se stará operátor přístupu k prvku *. Ukážeme si jeden užitečný příklad jak nejlépe načíst obsah (textového) souboru do řetězce
ifstream
in(“data.txt”);
string
data((istreambuf_iterator<char>(in)),
istreambuf_iterator<char>());
Je to mnohem rychlejší než použití formátovaného vstupu. Proč je první parametr v závorkách se dozvíte příště.
Neformátovaný výstup znak po znaku zajistí následující výstupní iterátor
template <typename charT,
typename
traits = char_traits<charT> >
class ostreambuf_iterator
: public iterator<output_iterator_tag,
void,
void, void, void>
{
// ... uvedeny
jen specifické složky
public:
ostreambuf_iterator(ostream_type
& s); // (1)
ostreambuf_iterator(streambuf_type
* s); // (1)
ostreambuf_iterator
& operator =(charT c); // (2)
bool failed()
const; // (3)
};
(1) Konstruktory, které připojí iterátor k výstupní vyrovnávací paměti.
(2) Zde se odehrává zápis znaku do proudu, ale jen v případě, že failed() vrátí false.
(3) Vrací true, pokud se při nějakém předchozím zápisu (operátor =) dosáhlo konce proudu; jinak vrací false.
Ostatní operátory pouze vrací *this. Navážeme na předchozí jednoduchý příklad: Když už jsme načetli textový soubor, tak si ho teď znovu uložíme
ofstream out(“mojedata.txt”);
copy(data.begin(), data.end(),
ostreambuf_iterator<char>(out));
Deklaraci všech těchto iterátorů na vstupně/výstupních proudech nalezneme v hlavičkovém souboru <iterator>. Poslední dva jmenované jsou neprávem podceňovány a přehlíženy. Pokud jde o neformátovaný vstup nebo výstup, jsou ale tou pravou volbou.
V příštím závěrečném dílu dokončíme přehlídku STL a všimneme si nejčastějších chyb a „podrazů“, které s sebou používání iterátorů přináší.
Jaroslav Franěk
Infotipy
[1] Dokumentace STL od SGI: www.sgi.com\technology\stl
[2] J. Franěk, Iterátory I, Chip 01/03
[3] J. Franěk, Iterátory II, Chip 01/03
[4] J. Franěk, Iterátory III, Chip 01/03
[5] J. Franěk, Nebojte se STL, Chip 12/01
[6] D. Musser et al., STL
Tutorial and Reference Guide, 2001
[7] N. Josuttis, The
C++ Standard Library, 1999