1 Standard Template LibraryProgramowanie uogólnione, parametryczne ( generic programming) Składniki biblioteki STL kontenery iteratory algorytmy adaptatory funktory Nicolai M. Josuttis, C++ Biblioteka standardowa, Helion 2003 kontener iterator Algorytm iterator kontener iterator kontener

2 WZORCE Wzorce funkcji template T minimum (T Pierwsza, T Druga) { return Pierwsza < Druga ? Pierwsza : Druga; } template bool greater (T Pierwsza, int Druga) return Pierwsza > Druga; // int a = 5; double x = ; cout << minimum(a, -17) << endl; // wersja int cout << minimum(x, a); // błąd cout << minimum(x, (double)a) << endl; // wersja double cout << greater(a, 5) << endl; // wersja int, int cout << greater(x, a) << endl; // wersja double, int cout << greater(a, x) << endl; // wersja int, int

3 Wzorce klas template class Para { T Lewy; T Prawy;int Numer; public: Para(int Nr) : Numer(Nr) {} Para(T, T, int); ~Para(); int Wiekszy (T wzorzec); }; template Para :: Para(T lewy, T prawy, int nr): Lewy(lewy), Prawy(prawy), Numer(nr) { cout << "Razem!" << endl; } template Para ::~Para () { cout << "Rozwod!" << endl; } template int Para :: Wiekszy (T wzorzec) { if (Lewy > wzorzec) return Numer; else return -1; }

4 Para ParaCalk(1, 2, 5); cout << ParaCalk.Wiekszy(7) << endl; cout << ParaCalk.Wiekszy(-4) << endl; float x = 4.0, *px = &x; //Para ParaRzecz(x, px, 5); // błąd Para* WskPd = new Para(3.0, 7.0, 9); cout << WskPd->Wiekszy(5.0) << endl; delete WskPd; Razem! -1 5 Rozwod!

5 Kontenery Wektor Kolejka o dwu końcach Lista sekwencyjneZbiór lub wielozbiór Mapa lub multimapa sekwencyjne asocjacyjne

6 Wektory 1 2 3 4 5 6 7 #include "stdafx.h" #include #include using namespace std; vector coll; // kontener wektorowy dla liczb całkowitych // dołącz elementy o wartościach od 1 do 7 for (int i=1; i<=7; ++i) coll.push_back(i); // coll[i] = i : błąd // wyświetl wszystkie elementy rozdzielone spacjami for (int i=0; i < coll.size(); ++i) cout << coll[i] << ' ';

7 Kolejki o dwu końcach (deque)#include deque coll; // kontener deque dla elementów typu float // wstaw elementy o wartościach od 1.1 do 7.7 na początek kontenera for (int i=1; i<=7; ++i) { coll.push_front(i * 1.1f); // wstaw na początek } // wstaw elementy o wartościach od -1.1 do -7.7 na koniec kontenera coll.push_back(i * -1.1f); // wstaw na koniec // wyświetl wszystkie elementy rozdzielone spacjami for (int i=0; i < coll.size(); ++i) cout << coll[i] << ' ';

8 a b c d e f g h i j k l m n o p q r s t u v w x y zListy #include list coll; // kontener list dla elementów znakowych // dolacz elementy od 'a' do 'z' for (char c='a'; c<='z'; ++c) { coll.push_back(c); // push_front(c) } /* wypisz wszystkie elementy : - gdy lista nie jest pusta - wypisz i usuń pierwszy element */ while (! coll.empty( )) cout << coll.front() << ' '; // coll.back() coll.pop_front(); // pop_back() a b c d e f g h i j k l m n o p q r s t u v w x y z

9 Adaptatory kontenerów sekwencyjnychStos #include stack st;   // wpisz trzy elementy na stos st.push(1); st.push(2); st.push(3);   // ze stosu zdejmij i wypisz dwa elementy cout << st.top( ) << ' '; st.pop( ); cout << '\t';   // zmodyfikuj szczytowy element st.top( ) = 77;   // wpisz dwa nowe elementy st.push( 4 ); st.push( 5 );   // zdejmij jeden element nie przetwarzając go st.pop();   // zdejmij i wypisz pozostałe elementy while (!st.empty( )) { cout << st.top( ) << ' '; st.pop( ); }

10 liczba elementow w kolejce: 2Kolejka #include #include queue q; // do kolejki wstaw trzy elementy q.push("Tu "); q.push("sa "); q.push("wiecej niz "); // z kolejki odczytaj i wypisz dwa elementy cout << q.front(); q.pop(); // wstaw dwa nowe elementy q.push("cztery "); q.push("slowa!"); // opusc jeden element // odczytaj i wypisz pierwszy i ostatni element cout << q.front() << endl; cout << q.back() << endl; // wypisz liczbe elementow w kolejce cout << "liczba elementow w kolejce: " << q.size(); Tu sa cztery slowa! liczba elementow w kolejce: 2

11 Kolejka priorytetowa TaskQueue 66.6 44.4 33.3 22.2 11.1#include priority_queue q; // do kolejki priorytetowej wstaw trzy elementy q.push(66.6); q.push(22.2); q.push(44.4); // odczytaj i wypisz dwa elementy cout << q.top() << ' '; q.pop(); cout << q.top() << endl; // wstaw kolejne trzy elementy q.push(11.1); q.push(55.5); q.push(33.3); // pomin jeden element // zdejmij i wypisz pozostale elementy while (!q.empty( )) { cout << q.top() << ' '; q.pop(); } TaskQueue

12 class Zadanie { int Priorytet; char* Opis; public: Zadanie(int, char* ); friend bool operator < (Zadanie, Zadanie); // less friend ostream& operator << (ostream&, Zadanie&); }; Zadanie::Zadanie(int pr = 0, char* op = NULL) : Priorytet(pr), Opis(op) {} bool operator < (Zadanie z1, Zadanie z2) { return z1.Priorytet < z2.Priorytet; } ostream& operator << (ostream& wy, Zadanie& zz) { wy << zz.Opis << " o priorytecie : " << zz.Priorytet << endl; return wy; }

13 Zad-2 o priorytecie : 12 Zad-5 o priorytecie : 8  priority_queue ListaZadan;   ListaZadan.push(Zadanie(5, "Zad-1")); ListaZadan.push(Zadanie(12, "Zad-2")); ListaZadan.push(Zadanie(3, "Zad-3")); ListaZadan.push(Zadanie(7, "Zad-4"));   cout << ListaZadan.top(); ListaZadan.pop();   ListaZadan.push(Zadanie(8, "Zad-5")); ListaZadan.push(Zadanie(4, "Zad-6")); Zad-2 o priorytecie : 12 Zad-5 o priorytecie : 8

14 Iteratory Iterator – obiekt, który służy do nawigowania w kontenerzeOperatory dla interatorów: * -> == != = Funkcje kontenerów związane z iteratorami begin( ) end( )

15 Typy iteratorów kontener::iterator nazwa // zapis i odczyt kontener::const_iterator nazwa // tylko odczyt dwukierunkowy ( ++ , -- ) : list, set, multiset, map, multimap dostępu swobodnego (arytmetyka iteratorów i dwukierunkowy) : vector, deque

16 a b c d e f g h i j k l m n o p q r s t u v w x y zlist coll; // kontener typu lista dla elementów znakowych // dolacz elementy od 'a' do 'z' for (char c='a'; c<='z'; ++c) coll.push_back(c); // wypisz wszystkie elementy - iteruj po wszystkich elementach list::const_iterator pos; for (pos = coll.begin(); pos != coll.end(); ++pos) // tylko ++ -- cout << *pos << ' '; a b c d e f g h i j k l m n o p q r s t u v w x y z vector vw; for (char c='a'; c<='z'; ++c) vw.push_back(c); vector iterator lok; for (lok = coll.begin(); lok != coll.end(); lok += 2) // co drugi { *lok = toupper(*lok); cout << *lok << ' '; } ONP1 A C E G I K M O Q S U W Y

17 Kontenery asocjacyjneZbiory i wielozbiory typedef set IntSet; // sort using less ( < ) IntSet coll; // kontener set dla wartości typu int // wstaw 7 elementów - wartość 1 wstawiana jest dwukrotnie coll.insert(3); coll.insert(1); coll.insert(5); coll.insert(4); coll.insert(1); coll.insert(6); coll.insert(2); coll.insert(7); // wypisz wszystkie elementy - iteruj po wszystkich elementach IntSet::const_iterator pos; for (pos = coll.begin(); pos != coll.end(); ++pos) cout << *pos << ' ';

18 typedef multiset > IntMultSet;// sort using greater ( > ) IntMultSet cont; cont.insert(3); cont.insert(1); cont.insert(5); cont.insert(4); cont.insert(1); cont.insert(6); cont.insert(2); cont.insert(7); // wypisz wszystkie elementy - iteruj po wszystkich elementach IntMultSet::const_iterator lok; for (lok = cont.begin(); lok != cont.end(); ++lok) cout << *lok << ' ';

19 jest to multimapa złożona z oznakowanych łancuchówMapy i multimapy typedef multimap IntStringMMap;  IntStringMMap coll; // kontener na pary wartości typu int-string   // wstaw kilka elementów w przypadkowej kolejności // - wartość o kluczu 1 wstawiana jest dwukrotnie coll.insert(make_pair(5,"oznakowanych")); coll.insert(make_pair(1,"jest")); coll.insert(make_pair(2,"multimapa")); coll.insert(make_pair(1,"to")); coll.insert(make_pair(4,"z")); coll.insert(make_pair(6,"łancuchów")); coll.insert(make_pair(3,"złożona")); /* wypisz wszystkie wartości elementów - iteruj po wszystkich elementach - druga składowa elementu to wartość */ IntStringMMap::iterator pos; for (pos = coll.begin(); pos != coll.end(); ++pos) cout << pos->second << ' '; jest to multimapa złożona z oznakowanych łancuchów

20 klucz: "dowolna liczba" wartosc: 4983.22/* typ kontenera: * - mapa: elementy o postaci par klucz-wartość * - string: klucze posiadają typ string * - float: wartości posiadają typ float */ typedef map StringFloatMap; StringFloatMap coll; // wstaw do kolekcji kilka elementów – tablica asocjacyjna // (tylko mapy) coll["VAT"] = 0.22; coll["Pi"] = ; coll["dowolna liczba"] = ; coll["Zero"] = 0; /* wypisz wszystkie elementy - iteruj po wszystkich elementach - pierwsza składowa elementu to klucz - druga składowa elementu to wartość */ StringFloatMap::iterator pos; for (pos = coll.begin(); pos != coll.end(); ++pos) cout << "klucz: \"" << pos->first << "\" " << "wartosc: " << pos->second << endl; MapFun2,1 klucz: "Pi" wartosc: klucz: "VAT" wartosc: 0.22 klucz: "Zero" wartosc: 0 klucz: "dowolna liczba" wartosc:

21 Algorytmy funkcje globalne operujące na iteratorach Zakresy[ początek , koniec ) początek - pozycja pierwszego elementu zakresu koniec - pozycja następna za ostatnim elementem zakresu #include

22 max: 34 max: 35 list coll; list::iterator pos;for (int i=20; i<=40; ++i) coll.push_back(i); //elementy do 20 do 40 // ustal pozycje wartości 25 oraz 35 list::iterator pos25, pos35; pos25 = find (coll.begin(), coll.end(), 25); // zakres, wartość pos35 = find (coll.begin(), coll.end(), 35); // zakres, wartość // wypisz największą wartość z odpowiedniego zakresu cout << "max: " << *max_element (pos25, pos35) << endl; // przetwarzaj elementy włącznie z ostatnią pozycją cout << "max: " << *max_element (pos25, ++pos35) << endl; max: 34 max: 35

23 min: 1 max: 6 vector::iterator pos;vector coll; vector::iterator pos; // wstaw elementy od 1 do 6 w przypadkowej kolejności coll.push_back(2); coll.push_back(5); coll.push_back(4); coll.push_back(1); coll.push_back(6); coll.push_back(3); // znajdź i wypisz element o najmniejszej i największej wartości pos = min_element (coll.begin(), coll.end()); cout << "min: " << *pos << endl; pos = max_element (coll.begin(), coll.end()); cout << "max: " << *pos << endl; // zamień miejscami elementy z pozycji 3 i 5 swap( coll[3], coll[5] ); // od 0 // zamień miejscami element maksymalny i element ostatni swap( *pos, *(coll.end( )-1)); min: 1 max: 6

24 1 2 6 5 4 3 // posortuj wszystkie elementysort (coll.begin(), coll.end());   // znajdź pierwszy element o wartości 3 pos = find (coll.begin(), coll.end(), 3); // zakres wartość   // odwróć kolejność elementów, począwszy od // znalezionego elementu o wartości 3 do końca reverse (pos, coll.end());   // wypisz wszystkie elementy for (pos=coll.begin(); pos!=coll.end(); ++pos) { cout << *pos << ' '; }

25 Obsługa wielu zakresów pierwszy zakres : początek i koniec dalsze zakresy : tylko początek list coll1; vector coll2; for (int i=1; i<=9; ++i) coll1.push_back(i); // wstaw elementy od 1 do 9 // zmień rozmiar kolekcji 2 tak, // aby miała wystarczająco miejsca dla algorytmu nadpisującego coll2.resize (coll1.size());   // utwórz trzecią kolekcję z wystarczająca ilością miejsca // - rozmiar początkowy przekazywany jest jako parametr deque coll3(coll1.size());

26 1 2 3 4 5 6 7 8 9 copy (coll1.begin(), coll1.end(), // źródło// przekopiuj elementy z pierwszej kolekcji do drugiej copy (coll1.begin(), coll1.end(), // źródło coll2.begin()); // przeznaczenie   // przekopiuj elementy z drugiej kolekcji do trzeciej copy (coll2.begin(), coll2.end(), // źródło coll3.begin()); // przeznaczenie deque::const_iterator lok; for (lok = coll3.begin(); lok != coll3.end(); ++ lok) cout << *lok << ' ';

27 Adaptatory iteratorówIteratory wstawiające wstawiacze końcowe wstawiacze początkowe wstawiacze ogólne Wstawiacz Opis back_inserter ( kontener ) Dołącza w tej samej kolejności funkcja push_back() front_inserter ( kontener ) Dołącza w odwrotnej kolejności funkcja push_front() inserter ( kontener, pozycja ) Wstawia na podanej pozycji funkcja insert() (dla kontenerów asocjacyjnych pozycja : początek poszukiwań)

28 9 8 7 6 5 4 3 2 1 list coll1;// wstaw elementy od 1 do 9 do pierwszej kolekcji for (int i=1; i<=9; ++i) coll1.push_back(i); // przekopiuj elementy z coll1 do coll2 dołączając je na końcu vector coll2; copy (coll1.begin(), coll1.end(), // źródło back_inserter(coll2)); // przeznaczenie // przekopiuj elementy z coll1 do coll3 wstawiając je na początku // - odwraca kolejność elementow deque coll3; front_inserter(coll3)); // przeznaczenie deque::const_iterator lok; for (lok = coll3.begin(); lok != coll3.end(); ++ lok) cout << *lok << ' ' ;

29 1 2 3 4 5 6 7 8 9 // - jedyny wstawiacz działający// przekopiuj elementy z kolekcji coll1 do coll4 // - jedyny wstawiacz działający // w przypadku kolekcji asocjacyjnych set coll4; copy (coll1.begin(), coll1.end(), // źródło inserter(coll4,coll4.begin())); // przeznaczenie set::const_iterator pos; for (pos = coll4.begin(); pos != coll4.end(); ++ pos) cout << *pos << ' ' ;

30 Iteratory strumieniowelist coll; cout << "Wpisz ciag liczb całkowitych i zakończ go .Enter \n"; copy(istream_iterator(cin),// początek źródła istream_iterator(), // koniec źródła .Enter, ctrl-Z Enter front_inserter(coll)); // przeznaczenie // wypisz wszystkie elementy kolekcji copy (coll.begin(), coll.end(), // źródło ostream_iterator(cout," ")); // przeznaczenie Wpisz ciag liczb całkowitych i zakończ go .Enter

31 6 5 4 3 2 1 1 2 3 4 5 6 6 5 4 2 1 1 2 4 5 6 5 6 list coll;for (int i=1; i<=6; ++i) { coll.push_front(i); coll.push_back(i); } // wypisz wszystkie elementy kolekcji copy (coll.begin(), coll.end(), ostream_iterator(cout," ")); // usuń wszystkie elementy o wartości 3 remove (coll.begin(), coll.end(), 3); // wypisz wynikowe elementy kolekcji

32 liczba usunietych elementow: 2 6 5 3 2 1 1 2 3 5 6coll.erase (coll.begin(), coll.end()); // usunięcie elementów for (int i=1; i<=6; ++i) { coll.push_front(i); coll.push_back(i); } // usuń wszystkie elementy o wartości 4 - zachowaj nową pozycję końca list::iterator end = remove (coll.begin(), coll.end(), 4); // wypisz wynikowe elementy kolekcji copy (coll.begin(), end, ostream_iterator(cout," ")); // wypisz liczbę elementów wynikowych cout << "liczba usuniętych elementów: " << distance(end, coll.end()) << endl; // usuń unieważnione elementy coll.erase (end, coll.end()); // wypisz wszystkie elementy zmodyfikowanej kolekcji copy (coll.begin(), coll.end(), liczba usunietych elementow: 2

33 Iteratory odwrotne 9 8 7 6 5 4 3 2 1 WordHis, Trójkivector coll; // wstawia elementy od 1 do 9 for (int i=1; i<=9; ++i) coll.push_back(i); // wypisz wszystkie elementy w odwrotnej kolejności copy (coll.rbegin(), coll.rend(), // źródło ostream_iterator(cout," ")); // przeznaczenie WordHis, Trójki

34 Funkcje Funkcje ogólne template inline void PRINT_ELEMENTS (const T& coll, const char* opis = "") { typename T::const_iterator pos; cout << opis; for (pos=coll.begin(); pos!=coll.end(); ++pos) cout << *pos << ' '; } cout << endl; // deque coll2; PRINT_ELEMENTS(coll2,"Wartości początkowe : ");

35 Funkcje jako argumenty algorytmówset coll1; vector coll2;   // wstaw do kolekcji coll1 elementy od 1 do 9 for (int i=1; i<=9; ++i) { coll1.insert(i); } PRINT_ELEMENTS(coll1,"Wartości początkowe: "); // przekształć każdy element z coll1 i umieść go w coll2 // - podnieś do kwadratu przenoszone wartości transform (coll1.begin(),coll1.end(), // źródło back_inserter(coll2), // przeznaczenie square); // zdefiniowana operacja   PRINT_ELEMENTS(coll2,"Podniesione do kwadratu : "); Wartosci poczatkowe : Podniesione do kwadratu :

36 Predykaty bool isPrime (int number){ if (number < 0) number = -number; // ignoruj znak ujemności if (number == 0 || number == 1) { return false; } // liczby 0 i 1 nie są pierwszymi // znajdź dzielnik, przez który liczba dzieli się bez reszty int divisor; for (divisor = number/2; number % divisor != 0; --divisor) { } return divisor == 1; // gdy jest dzielnik większy od 1, liczba nie jest liczbą pierwszą }

37 29 to pierwsza znaleziona liczba pierwszalist coll; // wstaw elementy od 24 do 30 for (int i=24; i<=30; ++i) { coll.push_back(i); } list::iterator pos; pos = find_if (coll.begin(), coll.end(), // zakres isPrime); // predykat if (pos != coll.end()) { cout << *pos << " to pierwsza znaleziona liczba pierwsza" << endl; } else { cout << "Nie znaleziono żadnej liczby pierwszej" << endl; } 29 to pierwsza znaleziona liczba pierwsza

38 mogą posiadać stan wewnętrzny (inicjowanie) posiadają typ Obiekty funkcyjne mogą posiadać stan wewnętrzny (inicjowanie) posiadają typ działają szybciej niż zwykłe funkcje // prosty obiekt funkcyjny, który wypisuje przekazany argument class PrintInt { public: void operator( ) (int elem) const cout << elem << ' '; } };

39 1 2 3 4 5 6 7 8 9 vector coll; // wstaw elementy od 1 do 9for (int i=1; i<=9; ++i) { coll.push_back(i); }   // wypisz wszystkie elementy for_each (coll.begin(), coll.end(), // zakres PrintInt()); // operacja // konstruktor -> tempPrintIt ; // for_each -> tempPrintIt( *tempPos )

40 // którą został zainicjalizowany class AddValue { private: // obiekt funkcyjny dodający wartość, // którą został zainicjalizowany class AddValue { private: int theValue; // wartość do dodania public: AddValue(int v) : theValue(v) { } // konstruktor ustala wartość do dodania void operator() (int& elem) { elem += theValue; } // wywołanie funkcji dodaje wartość };

41 po dodaniu pierwszego elementu: 22 23 24 25 26 27 28 29 30list coll; for (int i=1; i<=9; ++i)   // wstaw elementy od 1 do 9 { coll.push_back(i); } PRINT_ELEMENTS(coll,"wartości początkowe: ");   // do każdego elementu dodaj wartość 10 for_each (coll.begin(), coll.end(), // zakres AddValue(10)); // operacja PRINT_ELEMENTS(coll,"po dodaniu liczby 10: "); // do każdego elementu dodaj wartość pierwszego elementu AddValue(*coll.begin())); // operacja PRINT_ELEMENTS(coll,"po dodaniu pierwszego elementu: "); wartosci poczatkowe: po dodaniu liczby 10: po dodaniu pierwszego elementu: