Iterßtory I. Zah°φvacφ kolo

B²t äinô znamenß znßt a ovlßdat prost°edky, kterΘ nabφzφ standardnφ knihovna jazyka C++ STL. D∞sφ vßs pojem iterßtor? Pak jste tu sprßvn∞. P°ipravili jsme pro vßs miniserißl, kter² vßs provede standardnφ knihovnou a seznßmφ vßs s iterßtory. Dozvφte se nejenom, co to je iterßtor, ale seznßmφte se i s prost°edky, kterΘ STL nabφzφ, s tφm proΦ tam jsou a jak fungujφ. Nezapomeneme ani na nejΦast∞jÜφ problΘmy, kterΘ n∞kdy dokß₧φ zaskoΦit i zkuÜenΘho programßtora.

ProΦ iterßtory

P°i programovßnφ pracujeme s daty. Pro v∞tÜφ mno₧stvφ souvisejφcφch dat pou₧φvßme kontejnery, co₧ jsou obecn∞ objekty (nikoli ve smyslu OOP), kterΘ umo₧≥ujφ ulo₧it v∞tÜφ mno₧stvφ dat. Uvnit° kontejneru to ale m∙₧e vypadat r∙zn∞: Data mohou b²t ulo₧ena za sebou v °ad∞ û pak kontejner naz²vßme pole (array znamenß °ada), p°φkladem m∙₧e b²t klasickΘ cΘΦkovskΘ pole nebo STL t°φda vector. Data mohou b²t takΘ pospojovßna do °ady pomocφ ukazatel∙, pak jde o seznam, p°φkladem je STL t°φda list. Nebo pro ·Φely rychlΘho vyhledßvßnφ mohou b²t data uspo°ßdßna do binßrnφho stromu, p°φkladem jsou t°eba STL t°φdy set a map. Zkrßtka uspo°ßdßnφ dat v kontejneru m∙₧e b²t vÜelijakΘ.

Nynφ se zastavφme u algoritm∙. Vezm∞me t°eba hledßnφ maximßlnφho prvku v kontejneru (p°edpoklßdßme, ₧e to pro naÜe data mß smysl). ┌kol, ten znφ jasn∞: projφt vÜechny prvky od prvnφho do poslednφho a najφt ten nejv∞tÜφ. Je jistΘ, ₧e pro tento algoritmus nenφ d∙le₧itΘ, jak jsou data ulo₧ena, jestli ve stromu nebo v poli û to nemß na maximßlnφ prvek vliv. ProblΘm ale je: Co to znamenß prvnφ prvek? Co znamenß poslednφ prvek? Jak prochßzet mezi prvky, neboli jak iterovat? Nap°φklad u pole mßme hned jasno, co je prvnφ prvek a co poslednφ, ale co u stromu? A navφc û projφt pole prvk∙ znamenß takΘ n∞co ·pln∞ jinΘho ne₧ projφt vÜechny v∞tve stromu.

NaÜt∞stφ mßme iterßtory û dßvajφ v²znam pojm∙m jako prvnφ nebo poslednφ prvek a umo₧≥ujφ prochßzet mezi prvky v kontejneru neboli iterovat. Dφky iterßtor∙m se algoritmus pro hledßnφ maximßlnφho prvku, ale i mnoho jin²ch, nemusφ zab²vat vnit°nφ skladbou kontejneru. Iterßtory odkazujφ na prvky (jedna instance iterßtoru na nejv²Üe jeden prvek) a navφc implementujφ logiku prochßzenφ mezi prvky v danΘm kontejneru.

D°φve ne₧ p°istoupφme k bli₧Üφmu popisu, uv∞domme si jednu v∞c: v²raz iterßtor se pou₧φvß jak pro obecn² koncept (vφce o konceptech viz [2]), tak pro datov² typ a stejn∞ tak i pro instanci. Je to podobnΘ jako u ukazatel∙. Kdy₧ mßme nap°. deklaraci

 

int * p;

 

°ekneme ₧e int * je ukazatel, a takΘ ₧e p je ukazatel. Z tohoto d∙vodu v mφst∞, kde bude t°eba odliÜit v²znam pojmu iterßtor, uvedeme v zßvorce, zda se jednß o koncept, typ, nebo instanci.

Obr. 1 Takhle bude vypadat iterovßnφ ve stromu (STL t°φda set). Ka₧dß Üipka odpovφdß jednΘ iteraci.

Obr. 2 Iterovßnφ v klasickΘm poli nebo vektoru (STL t°φda vector). Ka₧dß Üipka odpovφdß jednΘ iteraci.

Algoritmy a iterßtory

Zatφm jsme nehovo°ili o tom, jak takov² iterßtor vypadß, ale jak vyplyne z nßsledujφcφho textu, pro pou₧φvßnφ STL kontejner∙ a algoritm∙ to nenφ nezbytn∞ nutnΘ. Zatφm nßm bude staΦit v∞d∞t, ₧e iterßtor je takovß äΦernß sk°φ≥kaô (black box), oznaΦme ji pφsmenem i, se kterou m∙₧eme, a₧ na n∞kolik v²jimek, provßd∞t tyto operace:

Obr. 3 Iterßtor jako Φernß sk°φ≥ka.

 

Nynφ si zde jeÜt∞ p°ipomeneme definici funkce hledajφcφ maximßlnφ prvek

 

template <class ITERATOR>á // (1)

ITERATOR max_element(ITERATOR prvni, ITERATOR posledni) // (2)

{

áá if ( prvni == posledni ) return posledni;á // (3)

áá ITERATOR max_prvek = prvni;á // (4)

áá while ( ++prvni != posledni )á // (5)

áá {

ááááá if ( *max_prvek < *prvni ) max_prvek = first;á // (6)

áá }

áá return max_prvek;á // (7)

}

 

Na vysv∞tlenou:

(1)   Ka₧d² kontejner m∙₧e mφt sv∙j vlastnφ iterßtor (typ), ale algoritmus hledßnφ maximßlnφho prvku z∙stane stejn². Proto je typ iterßtoru Üablonov²m parametrem.

(2)   Algoritmu zadßme dva iterßtory (instance): iterßtor na prvnφ prvek a iterßtor za poslednφ prvek rozsahu, kterΘho se t²kß hledßnφ maxima. TakovΘto zadßnφ rozsahu umo₧≥uje hledat maximßlnφ prvek t°eba jen v urΦitΘ Φßsti kontejneru. Algoritmus vracφ iterßtor na maximßlnφ prvek û nejen₧e zφskßme hodnotu maxima (dereferencovßnφm vrßcenΘho iterßtoru), ale navφc vφme, kde maximßlnφ prvek v kontejneru le₧φ.

(3)   Kdy₧ jsou si vstupnφ argumenty rovny, rozsah je prßzdn², tak₧e v duchu STL vrßtφme iterßtor na konec rozsahu (de facto na prvnφ prvek za)

(4)   Inicializujeme iterovßnφ, zaΦφnßme od prvnφho prvku v danΘm rozsahu.

(5)   Podmφnka pro ukonΦenφ iterace, vΦetn∞ p°echodu na dalÜφ prvek (++prvni).

(6)   Testujeme, jestli prvek urΦen² iterßtorem max_prvek je menÜφ, ne₧ prvek urΦen² iterßtorem prvni. Jak jste si jist∞ vÜimli, iterßtor prvni je pou₧it k projitφ zadanΘho rozsahu a tudφ₧ v t∞le smyΦky v₧dy znamenß zaΦßtek dosud nezpracovanΘho rozsahu (tΘto vlastnosti se °φkß invariant smyΦky, nebo¥ z∙stßvß v platnosti po celou dobu iterovßnφ).

(7)   Po skonΦenφ iterovßnφ odkazuje iterßtor max_prvek na (prvnφ) maximßlnφ prvek v danΘm rozsahu.

To byl p°φklad typickΘho generickΘho algoritmu. VÜimn∞te si nßsledujφcφch vlastnostφ: Parametrem je jist² rozsah prvk∙ urΦen² (ohraniΦen²) dv∞ma iterßtory. RadÜi ne₧ maximßlnφ prvek vracφ algoritmus iterßtor na maximßlnφ prvek. Algoritmus v∙bec nevφ na jakΘm kontejneru pracuje; pracuje s prvky kontejneru (pomocφ iterßtor∙), nikoli s kontejnerem samotn²m (proto nap°φklad nem∙₧e m∞nit poΦet prvk∙ kontejneru û pozd∞ji uvidφme, jak je d∙le₧itΘ o tΘto vlastnosti v∞d∞t).

Kontejnery a iterßtory

Nynφ nabφdneme pohled z druhΘ strany. Kontejner musφ generickΘmu algoritmu poskytnout jistou podporu, aby algoritmus mohl pracovat s jeho prvky. Jde jednak o typovΘ informace (jakΘho typu je iterßtor, konstantnφ iterßtor, prvek kontejneru, atd.) a jednak o poskytnutφ iterßtor∙ na prvnφ a (za) poslednφ prvek v kontejneru. Proto ka₧d² STL kontejner musφ implementovat normou p°edepsanΘ rozhrannφ. Nßm te∩ bude staΦit v∞d∞t, ₧e ka₧d² STL kontejner mß vno°enΘ definice typ∙:

 

iteratorááááááááááááááááááá typ iterßtoru na danΘm kontejneru

const_iteratorááááááá typ iterßtoru na danΘm kontejneru s konstantnφmi prvky

value_typeááááááááááááááá typ prvku danΘho kontejneru

 

a metody

 

iterator begin()áááááááááááááááááááááááááááááá vrßtφ iterßtor na prvnφ prvek

iterator end()áááááááááááááááááááááááááááááááááá vrßtφ iterßtor na prvnφ prvek za poslednφm (norma zaruΦuje, ₧e to mß smysl)

const_iterator begin() constáááááá vrßtφ iterßtor na prvnφ prvek konstantnφho kontejneru

const_iterator end() constáááááááááá vrßtφ iterßtor na prvnφ prvek za poslednφm u konstantnφho kontejneru (norma zaruΦuje, ₧e to mß smysl)

 

Na p°φkladu se vÜe hned objasnφ. Mßme kontejner cel²ch Φφsel a hledßme maximßlnφ prvek.

Nejd°φve pro vektor

 

vector<int> cisla;á // a n∞jakß inicializace prvk∙

// kde je maximßlnφ prvek?

vector<int>::iterator max_prvek =

ááááá max_element(cisla.begin(), cisla.end());

// kolik to je?

vector<int>::value_type max_hodnota = *max_prvek;

 

A te∩ pro seznam

 

list<int> cisla;á // a n∞jakß inicializace prvk∙

// kde je maximßlnφ prvek?

list<int>::iterator max_prvek =

ááááá max_element(cisla.begin(), cisla.end());

// kolik to je?

list<int>::value_type max_hodnota = *max_prvek;

 

VÜimn∞te si, ₧e dφky standardizovanΘmu rozhrannφ obou kontejner∙, se uvedenΘ v²pisy tΘm∞° neliÜφ. KONTEJNER::iterator je u obou tφm sprßvn²m typem iterßtoru pro dan² KONTEJNER, begin() v₧dy znamenß zaΦßtek a end() v₧dy konec rozsahu. To proto jsem tvrdil, ₧e nenφ t°eba v∞d∞t, jak jsou jednotlivΘ iterßtory implementovßny, jakΘho jsou vlastn∞ typu. Dφky vno°en²m definicφm typ∙ (deklarace typedef) se m∙₧eme ka₧dΘho STL kontejneru äzeptatô, jakΘho typu je jeho iterßtor û to je onen v²raz KONTEJNER::iterator. Metody begin() a end() vracφ iterßtory tohoto typu, tak₧e p°ekladaΦ si dokß₧e vydedukovat sprßvn² Üablonov² argument generickΘ funkce max_element a vygenerovat jejφ p°φsluÜnou instanci. Jak vidno, spoustu v∞cφ za nßs ud∞lß p°ekladaΦ.

Analogicky to funguje dokonce i pro klasickß pole:

 

int cisla[N] = { /*...*/ };

// kde je maximßlnφ prvek?

int * max_prvek = max_element(cisla, cisla + N);

// kolik to je?

int max_hodnota = *max_prvek;

 

Zde ale nemßme vno°enΘ definice typ∙ ani metody begin() a end(). Uv∞domte si ale, ₧e ukazatele jsou takΘ iterßtory û podporujφ vÜechny operace zmφn∞nΘ v p°edeÜlΘ sekci, lze jimi zadat hranice klasickΘho pole a implementujφ p°echod mezi prvky v klasickΘm poli.

JeÜt∞ pro ·plnost: v p°φpad∞ STL kontejner∙ implementovan²ch pomocφ binßrnφho stromu (nap°. t°φdy set) lze ve v∞tÜin∞ p°φpad∙ nahradit pou₧itφ algoritmu max_element n∞Φφm efektivn∞jÜφm. Tyto kontejnery jsou toti₧ set°φd∞nΘ.

D∙le₧itΘ pojmy

Abychom si i nadßle rozum∞li, provedeme up°esn∞nφ n∞kolika d∙le₧it²ch pojm∙, na kterΘ p°i pou₧φvßnφ iterßtor∙ zcela jist∞ narazφte.

Rovnost iterßtor∙

Pokud je pro iterßtor (typ) definovßna rovnost operßtorem ==, pak dva iterßtory (instance) i a j jsou si rovny, pφÜeme i == j, pokud odkazujφ na stejn² prvek. Nerovnost iterßtor∙ i != j znamenß totΘ₧ co !(i == j). Tedy bu∩ oba odkazujφ na r∙znΘ prvky, nebo je alespo≥ jeden z nich singulßrnφ (viz dßle).

Konstantnφ a nekonstantnφ iterßtory

Pokud v souvislosti s iterßtory mluvφme o konstantnosti a nekonstantnosti, mßme v₧dy na mysli konstantnost a nekonstantnost odkazovan²ch prvk∙. Konstantnφ instance iterßtoru toti₧ postrßdß smysl û neÜel by aplikovat operßtor ++ pro p°echod na dalÜφ prvek.

Konstantnφ iterßtor je tedy iterßtor, kter² umo₧≥uje prochßzet mezi prvky, ale neumo₧≥uje m∞nit jejich hodnoty. Nekonstantnφ iterßtor, krßtce je iterßtor, umo₧≥uje prochßzet mezi prvky i m∞nit jejich hodnoty.

Typ prvku

STL kontejner obsahuje prvky jednoho typu, iterßtor na tyto prvky odkazuje. Typem prvku u iterßtoru rozumφme typ hodnoty, kterou dostaneme, kdy₧ na iterßtor aplikujeme operßtor dereferencovßnφ *. Nap°φklad:

 

vector<int> cisla;

vector<int>::iterator i = cisla.begin();

 

Typem prvku iterßtoru i je typ v²razu *i, tj. v naÜem p°φpad∞ int.

 

const vector<int> ccisla;á // konstantnφ kontejner

vector<int>::const_iterator j = ccisla.begin();

 

Zde je typem prvku iterßtoru j typ const int. Vno°en² typ const_iterator nßm poskytne typ iterßtoru pro konstantnφ instanci t°φdy vector, a verze metod begin() a end() pro konstantnφ instance nßm vrßtφ iterßtor sprßvnΘho typu.

Anglicky se typ prvku oznaΦuje value type. S tφmto pojmem se pozd∞ji setkßme u ÜablonovΘ t°φdy rys∙ iterator_traits.

Dosa₧itelnost

╪ekneme, ₧e iterßtor j je dosa₧iteln² z iterßtoru i, jestli₧e existuje koneΦnß sekvence aplikacφ operßtoru ++ na iterßtor i, kterß zajistφ rovnost i == j. Jin²mi slovy: z i po koneΦnΘm poΦtu iteracφ p°ejdeme a₧ do j.

Pokud je iterßtor j dosa₧iteln² z iterßtoru i, pak oba nutn∞ le₧φ ve stejnΘm kontejneru. Nenφ mo₧nΘ, ₧e bychom se inkrementacφ iterßtoru i dostali ävenô z kontejneru a po n∞jakΘm Φase bloud∞nφ v pam∞ti ävpadliô do n∞jakΘho jinΘho kontejneru.

Jestli₧e jsou i a j r∙znΘ a j je dosa₧itelnΘ z i, pak podle naÜφ definice i nenφ dosa₧itelnΘ z j. Pot°ebovali bychom zp∞tn² chod, operßtor --. Jak uvidφme dßle, n∞kterΘ druhy iterßtor∙ toto zvlßdnou. Mohli bychom tak pro n∞ definovat reverzibilnφ dosa₧itelnost.

Anglick² termφn pro dosa₧itelnost je reachability.

Typ rozdφlu

Pokud je pro dva iterßtory definovßna rovnost pomocφ operßtoru == (m∞ly by zßrove≥ b²t ve stejnΘm kontejneru), je definovßna i nerovnost operßtorem !=. V p°φpad∞, ₧e se dva nesingulßrnφ (viz dßle) iterßtory i a j nerovnajφ, m∙₧e nßs zajφmat, jak jsou od sebe daleko. Vzdßlenost se m∞°φ poΦtem krok∙ (iteracφ), kterΘ je nutno uΦinit, abychom se od i dostali k j. Pokud i == j, pak vzdßlenost je nulovß. Pro i != j musφme rozliÜit dva p°φpady: Za prvΘ, pokud je j dosa₧itelnΘ z i, tak vzdßlenost od i do j je rovna poΦtu aplikacφ operßtoru ++ nutn²ch na dosa₧enφ j z i. Za druhΘ zb²vß u₧ jen mo₧nost, kdy i je dosa₧itelnΘ z j, pak vzdßlenost od i do j je rovna zßporn∞ vzatΘmu poΦtu aplikacφ operßtoru ++ nutn²ch na dosa₧enφ i z j. Typ rozdφlu tedy musφ b²t celΘ Φφslo se znamΘnkem.

Anglicky se typ rozdφlu oznaΦuje difference type a setkßme se s nφm u ÜablonovΘ t°φdy rys∙ iterator_traits.

Prvek za koncem kontejneru

UrΦit∞ vφte, ₧e kdy₧ deklarujeme klasickΘ pole N prvk∙, mßme k dispozici i adresu prvku N+1 (jeliko₧ indexovßnφ zaΦφnß v₧dy nulou, mß tento index N). Pro osv∞₧enφ pam∞ti

 

const int N = 20;

int pole[N] = { /*...*/ };

 

for ( int * i = pole; i < &pole[N]; ++i ) { /*...*/ }

// nebo

for ( int * i = pole; i < pole + N; ++i ) { /*...*/ }

 

Zv²razn∞nΘ Φßsti jsou adresy neexistujφcφho prvku za koncem pole. Norma jazyka C++ (ale i C) zajiÜ¥uje, ₧e tato adresa mß v₧dy smysl.

Analogie uvedenΘho pravidla platφ i pro vÜechny iterßtory. Implementace knihovny STL musφ zajistit, aby iterßtor na prvnφ äneexistujφcφ prvekô za koncem kontejneru m∞l smysl. S takov²mi iterßtory se setkßvßme Φast∞ji, ne₧ by se zdßlo. Nap°φklad iterßtor, kter² vrßtφ metoda end() je iterßtorem na neexistujφcφ prvek za poslednφm prvkem v p°φsluÜnΘm kontejneru.

Anglicky tyto prvky naz²vßme past-the-end values, nebo takΘ one past-the-end.

 

 

Obr. 4 Neexistujφcφ prvek za koncem kontejneru.

 

DereferencovatelnΘ hodnoty iterßtor∙

Iterßtor (typ) sice implementuje operßtor dereferencovßnφ *, ale ne vÜechny jejich instance jdou dereferencovat. Nap°φklad u₧ zmi≥ovanΘ iterßtory na prvky za koncem kontejneru nejdou dereferencovat. To znamenß, ₧e nejde napsat (s vyu₧itφm p°edchozφho p°φkladu)

 

int pole[N] = { /* ... */ };

int a = pole[N];á // !!! NELZE

pole[N] = 0;áá // !!! NELZE

 

Adresa tohoto prvku sice existuje, ale prvek samotn² nikoliv. Stejn∞ tak nelze dereferencovat iterßtor zφskan² metodou end()

 

vector<int> cisla;á // a n∞jakß inicializace prvk∙

int a = *cisla.end();á // !!! NELZE

*cisla.end() = 0;áá // !!! NELZE

 

Tak₧e dereferencovatelnΘ hodnoty iterßtor∙ jsou takovΘ instance iterßtor∙, kde pou₧itφ operßtoru * k zφskßnφ odkazovanΘho prvku mß smysl.

Singulßrnφ hodnoty iterßtor∙

Stejn∞ jako neinicializovanΘ ukazatele (ukazatele ukazujφcφ nikam), m∙₧eme mφt i neinicializovanΘ iterßtory. TakovΘ iterßtory neodkazujφ na ₧ßdn² prvek v ₧ßdnΘm kontejneru. JedinΘ, co lze s takov²m iterßtorem d∞lat, je p°i°adit mu n∞jakou nesingulßrnφ hodnotu, tj. nechat ho odkazovat na n∞jak² prvek v n∞jakΘm kontejneru.

Je jist∞ z°ejmΘ, ₧e dereferencovatelnΘ hodnoty iterßtor∙ a iterßtory odkazujφcφ na prvnφ prvek za koncem kontejneru jsou nesingulßrnφ.

Rozsah

Dostßvßme se ke snad nejd∙le₧it∞jÜφmu pojmu, tφm je rozsah. Pokud mßme dva nesingulßrnφ iterßtory i a j na stejnΘm kontejneru a j je dosa₧itelnΘ z i (budeme uva₧ovat pouze platnΘ rozsahy), pak m∙₧eme definovat rozsah takto: Je to mno₧ina vÜech iterßtor∙ i poΦφnaje, kterΘ dostaneme z i aplikovßnφm operßtoru ++ tak dlouho dokud nedosßhneme j, p°iΦem₧ j do rozsahu nezahrneme. Lidov∞ °eΦeno: vÜechno mezi i a j, vΦetn∞ i a mimo j. Rozsah iterßtor∙ m∙₧eme oznaΦit stejn∞ jako interval Φφsel v matematice

 

[i, j)

 

Tento zßpis znamenß, ₧e i do danΘho rozsahu pat°φ (V Φesk²ch krajφch se pou₧φvß spφÜe lomenß zßvorka, ale v∞tÜina poΦφtaΦovΘ literatury je v angliΦtin∞, proto si dovolφm napsat to takto.) a j tam nepat°φ.

ProΦ tam j nepat°φ? Je k tomu n∞jak² rozumn² d∙vod? Ano je, nap°φklad celkem snadno m∙₧eme oznaΦit prßzdn² rozsah takto

 

[i, i)

 

Kdy₧ si mφsto iterßtor∙ p°edstavφme celß Φφsla, kolik prvk∙ mß mno₧ina [m,n)? P°esn∞ m-n. Kdybychom se na totΘ₧ zeptali u mno₧iny [m,n], vyÜlo by nßm m-n+1 a to u₧ nenφ tak hezkΘ.

Cel² rozsah libovolnΘho STL kontejneru, pojmenovanΘho nap°. cisla, lze vyjßd°it takto

 

[cisla.begin(), cisla.end() )

 

U₧ vφme, ₧e metoda end() vracφ iterßtor na prvnφ prvek za poslednφm, kter² do zpracovßvanΘho rozsahu nepat°φ.

 

 

Obr. 5 Rozsah [i,j). Barevn∞ podlo₧eny jsou odpovφdajφcφ prvky.

OhlΘdnutφ do minulosti i souΦasnosti

Iterßtory nejsou v²sadou STL. Je to obecn² programovacφ vzor (design pattern, viz [6]), kter² se pou₧φval jeÜt∞ p°ed tφm, ne₧ p°iÜla STL. Pam∞tnφci mo₧nß zaznamenali p°φtomnost iterßtor∙ v knihovn∞ datov²ch typ∙ BIDS (Borland International Data Structures), kterß se distribuovala s oblφben²m p°ekladaΦem Borland C++ 3.1.

Modernφ programovacφ jazyky jako Java a C# takΘ umo₧≥ujφ prßci s iterßtory.

Iterßtor a dalÜφ programovacφ vzory

V souvislosti s iterßtory se (v STL) pou₧φvajφ jeÜt∞ dalÜφ programovacφ vzory: adaptΘr a proxy, podrobn∞ popsanΘ v [6]. O adaptΘrech jsme si u₧ povφdali v souvislosti s funktory [3]. AdaptΘr p°izp∙sobφ rozhrannφ adaptovanΘho objektu jin²m pot°ebßm. Nap°φklad adaptΘr reverse_iterator, jak jmΘno napovφdß, zm∞nφ sm∞r prochßzenφ prvk∙ od konce k zaΦßtku.

Proxy je tzv. zßstupn² objekt. P°edstavte si, ₧e mßte hodn∞ velk² kontejner, kter² se nevejde cel² do operaΦnφ pam∞ti. Je tedy z v∞tÜφ Φßsti ulo₧en na pevnΘm disku. I na takovΘm kontejneru lze po₧φt iterßtory û budou vÜak vracet proxy a nikoli odkazovanΘ objekty. Proxy se postarß, v p°φpad∞ p°φstupu k danΘmu prvku, o naΦtenφ prvku z disku do pam∞ti.

DalÜφm p°φkladem proxy jsou tzv. vklßdacφ iterßtory. To jsou iterßtory, kterΘ umo₧≥ujφ vklßdat do kontejneru novΘ prvky. V ·vodu tohoto Φlßnku jsem zd∙raznil, ₧e iterßtory nemohou m∞nit poΦet prvk∙ v kontejneru û to je pravda, ale v kombinaci s proxy to jde. Jak? û To se dozvφte v jednom z nßsledujφcφch dφl∙.

P°φÜt∞

Po ·vodnφm seznßmenφ se zßkladnφmi pojmy nahlΘdneme p°φÜt∞ do STL a p°edstavφme si koncepty iterßtor∙, kterΘ tato knihovna pou₧φvß.

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, Jak se na funktor volß I., Chip 01/02
[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