Fejlett programozási nyelvek C++ Iterátorok 10. előadás Antal Margit 2009
slide 1
Témakörök I. Bevezetés II. Iterátor definíció III. Iterátorok jellemzői IV. Iterátorkategóriák V. Iterátor adapterek
slide 2
I. Bevezetés ◆ Tárolók (konténerek) – Sorozatok: vector
, deque, list – Asszociatív tárolók: set, map, multiset, multimap ◆ Függvényobjektumok – tárolók rendezettsége ◆ Iterátorok– tárolók bejárása
slide 3
Homogén és ,,heterogén'' tárolók vector<Szemely> Szemely
Szemely
Szemely
... Szemely
vector<Szemely*> Alkalmazott
... Szemely
Alkamazott
Alkalmazott
slide 4
II. Iterátor - definíció ◆ Olyan objektumok, amelyek tetszőleges belső ábrázolású tároló bejárását biztosítják ◆ Iterátor osztály = pozíció + műveletek ◆ Általánosítják a mutató (pointer) fogalmát – Intelligens mutató ◆ Biztosítják az algoritmusok alkalmazhatóságát különféle tárolóban meghatározható tartományokra slide 5
III. Iterátorok jellemzése ◆ kétféle iterátor van – érvényes: it != container.end() – érvénytelen: • vector<string>::iterator it; – (nincs kezdőértéke) • vector<string> v; //... for(it=v.begin(); it!=v.end(); ++it); – it==v.end(); • törlés vagy beszúrás következtében érvénytelenné vált slide 6
IV.
Iterátorkategóriák
Bemeneti iterátor
Kimeneti iterátor Előre iterátor
Kétirányú iterátor Közvetlen elérésű iterátor
slide 7
Iterátorkategóriák ◆ Bemeneti iterátor – Input Iterator – előre olvas (csak!): object = *it;it++; ◆ Kimeneti iterátor – Output Iterator – előre ír (csak!): *it = object;it++; ◆ Előre iterátor – Forward Iterator – előre olvas és ír ◆ Kétirányú iterátor – Bidirectional Iterator – előre/hátra olvas és ír: it++; it--; ◆ Közvetlen elérésű iterátor – Random Access Iterator: it+n; it-n;
slide 8
Alapvető iterátor műveletek ◆ elem elérése: *it ◆ tag elérése: it->member ◆ előre léptetés: ++it ◆ vissza léptetés: --it
slide 9
1. Bemeneti iterátorok ◆ Szekvenciális feldolgozást tesznek lehetővé ◆ Single Pass Iterator – minden elemhez csak egyszer férhetünk hozzá ◆ Algoritmusok: – find – for_each slide 10
A find algoritmus template InIt find( InIt first, InIt last, T what { for( ; first != last; ++first ) if( *first == what ) return first; return first; }
slide 11
A forEach algoritmus template Func for_each( InIt first, InIt last, Func f) { for( ;first != last; ++first) f( *first ); return f; }
slide 12
A forEach használata class Duplaz{ double osszeg; public: Duplaz() : osszeg ( 0 ){} void operator()( double& d ){ d += d; osszeg += d;} double getOsszeg(){ return osszeg;} };
double x[]={1, 2, 3}; Duplaz fo; fo = for_each( x, x+3, fo); cout<<"Osszeg: "<
slide 13
2. Kimeneti iterátorok ◆ szekvenciális feldolgozás ◆ csak írás művelet ◆ Single Pass Iterator – minden pozíció csak egyszer írható
◆ Algoritmusok: – copy
slide 14
A copy algoritmus template OutIt copy( InIt first1, InIt last1, OutIt first2) { while( first1 != last1 ){ *first2 = *first1; first1++; first2++; } return first2; }
slide 15
3. Előre iterátorok A bemeneti és a kimeneti iterátorok tulajdonságait egyesíti Multi Pass Iterator Ír és olvas, akár többször is ugyanazt a pozíciót Algoritmusok: • replace slide 16
A replace algoritmus template < class FwdIt, class T > void replace ( FwdIt first, FwdIt last, const T& oldv, const T& newv ) { for (; first != last; ++first) if (*first == oldv) *first=newv; }
slide 17
4. Kétirányú iterátorok Olyan előre bejáró, amely lehetővé teszi a visszafele lépkedést is (it++, it--) A standard könyvtár minden tárolója legalább ilyen erősségű bejáróval rendelkezik Algoritmusok • reverse_copy
slide 18
A reverse_copy algoritmus template OutIt reverse_copy ( BiIt first, BiIt last, OutIt result) { while ( first!=last ){ --last; *result = *last; result++; } return result; }
slide 19
5. Közvetlen elérésű iterátorok Olyan kétirányú iterátor, amely
it+n, it-n it1 < it2
Algoritmusok:
sort, next_permutation, ...
slide 20
V. Iterátor adapterek Lehetővé teszik, hogy az iterátorok fordított, beszúró, illetve adatfolyam módban dolgozzanak. Vissza iterátorok – Reverse Iterator Beszúró iterátorok – Insert Iterator Adatfolyam iterátorok – Stream Iterator
slide 21
Viszza iterátorok ◆ Megfordítják a ++ és a -- operátorok jelentését. Segítségükkel az algoritmusok fordított sorrendben dolgozzák fel az elemeket. ◆ Minden tárolónak van, elérése: – container.rbegin() – container.rend()
slide 22
Beszúró iterátorok ◆ Átalakítják az értékadó műveletet beszúró műveleté ◆ overwrite insert ◆ Miért szükségesek? – Az algoritmusok alapértelmezetten felülírásos üzemmódban működnek slide 23
Beszúró iterátorok (2) template OutIt copy( InIt first1, InIt last1, OutIt first2) { while( first1 != last1){ *first2 = *first1;//EZT !!! first1++; first2++; } return first2; } slide 24
Beszúró iterátor típusok *pos = ertek; Név
Osztály
Függvény
Hátra beszúró
back_insert_iterator push_back( ertek)
back_inserter(container)
Előre beszúró
front_insert_iterator push_front(ertek)
front_inserter(container)
Beszúró
insert_iterator
inserter(container,poz)
insert(poz, ertek)
Létrehozás
slide 25
Beszúró iterátor – példa //Helytelen int x[] = {1, 2, 3}; vector v; copy( x, x+3, v.begin()); //Helyes int x[] = {1, 2, 3}; vector v; copy( x, x+3, back_inserter(v)); slide 26
Adatfolyam (stream) iterátorok ◆ Cél: az algoritmusok a bemenetüket, illetve a kimenetüket adatfolyamhoz köthessék
cin
copy
vector
vector
copy
cout
slide 27
Adatfolyam iterátorok Működési elv: – írás → adatfolyamba írás – olvasás → adatfolyamból olvas
slide 28
Adatfolyam iterátorok – példák Kimeneti: vector v; copy(v.begin(), v.end(), ostream_iterator(cout, ",")); Bemeneti: copy(istream_iterator(cin), istream_iterator(), back_inserter(v)); slide 29
Iterátor - tulajdonságok template< class T> struct iterator_traits{ typedef typename T::value_type value_type; typedef typename T::difference_type difference_type; typedef typename T::iterator_category iterator_category; typedef typename T::pointer pointer; typedef typename T::reference reference; };
slide 30
A CArray osztály template class CArray{ T * data; int size; public: ... typedef T* typedef T typedef T& typedef ptrdiff_t typedef T * };
iterator; value_type; reference; difference_type; pointer;
slide 31
