7. rˇ´ıjna 2010, Brno Prˇipravil: David Procha´zka
Sˇablony, kontejnery a itera´tory Programovacı´ jazyk C++
ˇ ablony S
Strana 2 / 21
Sˇablona funkce/metody ˇ ablona je obecny´ popis (trˇ´ıdy, funkce) bez toho, zˇe by byl S specifikova´n konkre´tnı´ typ. Ten je dosazen podle potrˇeby azˇ prˇi pouzˇitı´ sˇablony. Jedna´ se o specifikum jazyka C++. 1 2 3 4 5
template < class T > void prohod ( T &a , T & b ){ T pom = a ; a = b; b = pom ; }
ˇ ablony S
Strana 3 / 21
Pouzˇitı´ sˇablony 1 2 3 4 5
template < class T > void prohod ( T &a , T & b ){ T pom = a ; a = b; b = pom ; }
6 7 8 9 10 11 12 13
int main (){ int a = 10; int b = 11; prohod (a , b ); cout << " A : " << a << endl ; cout << " B : " << b << endl ; ...
ˇ ablony S
Sˇablony trˇ´ıd 1 2 3 4 5 6 7 8 9 10
template < class T > class Sachovnice { private : T deska [8][8]; public : void vypln ( T prvek ){ for ( int i =0; i <8; i ++) for ( int j =0; j <8; j ++) deska [ i ][ j ] = prvek ; } };
Strana 4 / 21
ˇ ablony S
Strana 5 / 21
Pouzˇitı´ sˇablony trˇ´ıdy 1 2
Sachovnice < int >* pokus = new Sachovnice < int >; pokus - > vypln (0);
3 4 5
Sachovnice < float > pokus2 ; pokus2 . vypln (0.1);
6 7
delete pokus ;
ˇ ablony S
Strana 6 / 21
Sˇablony o vı´ce parametrech 1 2 3 4 5 6 7 8 9 10 11 12
template < class T1 , class T2 > class Sachovnice { private : T1 deska [8][8]; T2 pomocnaDeska [8][8]; public : void vypln ( T1 prvek ){ for ( int i =0; i <8; i ++) for ( int j =0; j <8; j ++) deska [ i ][ j ] = prvek ; } ... Sachovnice < int , char > pokus3 ;
ˇ ablony S
Implicitnı´ parametry 1 2
template < class T = int > class Sachovnice {...};
3 4 5
template < class T1 , class T2 = int > class JinaSachovnice {...};
6 7 8
Sachovnice < > pokus ; Sachovnice < int > pokus2 ;
9 10 11
JinaSachovnice < int > pokus ; JinaSachovnice < int , char > pokus2 ;
Strana 7 / 21
STL
Strana 8 / 21
Vector STL: Standard Template Library je knihovna sˇablon, ktera´ je soucˇa´stı´ C++. Obsahuje implementace rˇady beˇzˇny´ch ADT a algoritmu˚. Typicky´m za´stupcem ADT z STL je sˇablona vector. vector je jednorozmeˇrne´ dynamicke´ pole bez specifikovane´ho typu.
STL
Strana 9 / 21
Prˇ´ıklad operacı´ s kontejnerem vector 1 2 3 4 5 6 7 8 9 10 11 12 13 14
# include < vector > # include < iostream > using namespace std ; int main () { vector < int > a (7); // Pole 7 čísel vector < int > b ; // Pole 0 čísel cout << " Počet prvků a je " << a . size () << " " ; cout << " Počet prvků b je " << b . size () << endl ; for ( int i = 0; i < a . size (); i ++){ a [ i ] = i + 1; cout << " a [ " << i << " ] = " << a [ i ] << endl ; } b = a ; // Bez problémů lze použít operátor = ...
STL
Strana 10 / 21
Prˇida´va´nı´ a ubı´ra´nı´ prvku˚ 1 2 3 4 5
vector < int > a ; for ( int i = 0; i < 5; i ++){ a . push_back ( i +1); cout << " Poslední prvek je : " << a . back () << endl ; }
6 7 8 9
for ( int i = 0; i < a . size (); i ++) { cout << a [ i ] << ’\ t ’; }
10 11 12 13
while (! a . empty ()) { a . pop_back (); }
// Opakuj , dokud nemá 0 prvků // Odeberu poslední prvek
14 15
cout << " Velikost " << a . size () << endl ;
STL
Strana 11 / 21
Vı´cerozmeˇrne´ pole 1 2 3 4 5 6
vector < vector < int > > matice (3); // Matice 3 x0 for ( int a = 0; a < 3; a ++) { matice [ a ]. push_back ( a +1); matice [ a ]. push_back ( a +2); matice [ a ]. push_back ( a +3); } // Nyní máme matici 3 x 3 , tupa metoda !
7 8 9 10 11 12 13
for ( int y = 0; y < 3; y ++){ for ( int x = 0; x < 3; x ++){ cout << matice [ x ][ y ] << ’\ t ’; } cout << endl ; }
Itera´tory
Strana 12 / 21
Itera´tory Itera´tor je de facto ukazatel pro kontejner. Vy´znam iteratoru˚ spocˇı´va´ v tom, zˇe unifikujı´ prˇ´ıstup k ru˚zny´m struktura´m. Bez nich by nebylo mozˇne´ vytva´rˇet genericke´ algoritmy. Bezpecˇnejsˇ´ı nezˇ indexy nebo ukazatele. Ke kontejneru˚m jsou prˇeddefinova´ny uzˇitecˇne´ itera´tory na zacˇa´tek (.begin()), za konec (.end()), atp. Itera´toru˚ je cela´ rˇada (vstupnı´, vy´stupnı´, aj.).
Itera´tory
Strana 13 / 21
Pru˚chod polem pomocı´ itera´toru˚ 1
# include < vector >
2 3 4 5 6 7
vector < int > vektor (20); for ( vector < int >:: iterator temp = vektor . begin (); temp != vektor . end (); temp ++){ * temp = 0; }
vectorem lze procha´zet i pomocı´ [] nebo metody at(). Doporucˇena je radeˇji metoda at(), protozˇe v prˇ´ıpadeˇ vstupu na neplatnou pozici vyhodı´ vy´jimku out of range.
Itera´tory
Strana 14 / 21
Vyuzˇitı´ itera´toru˚ pro zmeˇny ve vectoru 1 2 3 4 5 6
// Vložím před první prvek -100 v1 . insert ( v1 . begin () , -100); // Vložím na konec 3 krát 500 v1 . insert ( v1 . end () ,3 ,500); // Vložím celý vektor v1 do v2 v2 . insert ( v2 . begin ()+2 , v1 . begin () , v1 . end ());
7 8 9 10 11 12
// Mažu prvek pod iterátorem v2 . erase ( it ); // Mažu všechny prvky ve v2 v2 . erase ( v2 . begin () , v2 . end ()); v2 . clear ();
Kontejnery
Strana 15 / 21
Dalsˇ´ı kontejnery a jejich funkce Vsˇechny posloupnosti podporujı´ popsane´ varianty insert, erase a clear. Navı´c majı´ dalsˇ´ı metody. jednoduche´
kontejner. adapte´ry asociativnı´ kontejnery
vector list deque queue stack priority que set map multiset multimap
front, back, push/pop back, at/[] vector bez at/[]+ push/pop front vector + push front, pop front push,pop,front,back,size,empty push, top, pop, size, empty queue
Kontejnery
Strana 16 / 21
Komenta´rˇe k tabulce list i deque umozˇnˇujı´ narozdı´l od vectoru vkla´dat na zacˇa´tek/mazat ze zacˇa´tku prvek v konstantnı´m cˇase. Proto jsou u nich tyto metody implementova´ny. U vectoru by tato operace meˇla linera´rnı´ slozˇitost (posun vsˇech prvku˚ dozadu). vector i deque nabı´zı´ prˇ´ımy´ prˇ´ıstup s linea´rnı´ slozˇitostı´. vector je ale jednoduzˇsˇ´ı a proto rychlejsˇ´ı. list je naopak zameˇrˇen na rychle´ vkla´da´nı´ a maza´nı´ prvku˚ kdekoliv v konstantnı´m cˇase. priority queue je stejna´ jako queue jen prvek s nejveˇtsˇ´ı hodnotou se dostane automaticky do cˇela fronty.
Asociativnı´ kontejnery
Strana 17 / 21
Asociativnı´ kontejnery Jedna´ se o setrˇ´ıdeˇne´ kontejnery, ale necha´peme je obvykle jako klasicka´ pole hodnot. Strukturou lze vsˇak klasicky sekvencˇeneˇ projı´t. set je mnozˇina. map je hash, kde prvek je (mı´sto pozice) identifikova´n klı´cˇem. Ke klı´cˇi se vztahuje prˇ´ıslusˇna´ hodnota. „Multi“ varianty kontejneru˚ umozˇnˇujı´ duplicitnı´ prvky/klı´cˇe.
Asociativnı´ kontejnery
Strana 18 / 21
Asoc. kontejner set 1 2 3 4
# include <set > # include < iterator > ... multiset < int > mnozina ;
5 6 7 8
mnozina . insert (4); mnozina . insert (3); mnozina . insert (5);
9 10 11 12 13
multiset < int >:: iterator pos ; for ( pos = mnozina . begin (); pos != mnozina . end (); ++ pos ){ cout << * pos << ’ ’; }
Asociativnı´ kontejnery
Strana 19 / 21
Asoc. kontejner map (hash) 1 2 3
# include <map > ... map < string , string > slova ;
4 5 6 7 8 9 10 11 12 13
// ulozeni hodnoty slova [ " jmeno " ] = " david " ; slova [ " prijmeni " ] = " prochazka " ; // vypis hodnoty cout << " Jmeno : " << slova [ " jmeno " ] << endl ; // vypis velikost cout << " Velikost : " << slova . size () << endl ; // vlozeni celeho paru hodnot slova . insert ( pair < string , string >( " jmeno " ," hodnota " ));
Asociativnı´ kontejnery
Strana 20 / 21
Pru˚chod mapem 1 2 3 4 5 6 7
// projdu v cyklu for a vypisuji klic ( first ) // a hodnotu ( second ) for ( map < string , string >:: iterator iter = freq . begin (); iter != freq . end (); ++ iter ) { cout << iter - > first << " " << iter - > second << endl ; }
Dalsˇ´ı na´stroje STL
Strana 21 / 21
Dalsˇ´ı na´stroje STL Funktory (equal to
(a, b), greater, less, ...), kopı´rova´nı´, na´hrady, genera´tory, vyhleda´va´nı´ (find(v.begin(), v.end(), 4)), trˇ´ıdeˇnı´ (sort(v.begin(), v.end()), ...
