1 Standard Template Library
2 Książki o STL i bibliotece standardowej C++Nicolai M. Josuttis: C++ Standard Library: A tutorial and Reference, 1st, Pearson 1999, przykłady: (Polska wersja: Nicolai M. Josuttis: C++ Biblioteka standardowa Podręcznik Programisty, Helion 2003, przykłady: ftp://ftp.helion.pl/przyklady/cpbspp.zip) Nicolai M. Josuttis: C++ Standard Library: A tutorial and Reference, 2nd, Addison Wesley Longman 2012, (uwzględnia standard C++11) Grębosz J.: Pasja C++, RM, W-wa Inne (wspomniane na pierwszym wykładzie o C++, w tym ANSI/ISO C++ standard)
3 Biblioteka standardowa języka C++Biblioteka zawiera klasy strumieniowe klasy łańcuchowe STL Standard Template Library (największa i najintensywniej rozwijana część biblioteki) Dawniej używano nagłówków (obsolete): „*.h”, „*.hpp”, „*.hxx” Znacząco rozszerzona w standardzie C++11 (głównie część STL) Rozszerzenia języka i bibliotek C++11 nie są jeszcze w pełni wspierane przez kompilatory; wykład o C++11 na przedmiocie MiNWO poświęcony będzie nowemu standardowi C++
4 STL Główne składniki STL to biblioteka wzorców!Kontenery (listy, wektory, etc.) Iteratory (interfejs pomiędzy algorytmami a kontenerami) Algorytmy (proste, nie bardziej skomplikowane od wyszukiwania i sortowanie) Inne (obiekty funkcyjne, adaptory, ...) STL to biblioteka wzorców! Dane odseparowane od metod (a co z ideą OOP?) Zaprojektowane dla programowania wysokopoziomowego Zaprojektowane dla programowania wydajnego
5 BTW: rząd złożoności algorytmuO-notacja Wyszukiwanie w posortowanej tablicy: O(log2(n)) Wyszukiwanie w nieuporządkowanej tablicy: O(n) quicksort: O(n · log2(n)) Sortowanie bąbelkowe: O(n2)
6 Kontenery Sekwencyjne Asocjacyjne vector (tablica dynamiczna)dequeue (tablica dynamiczna dwukierunkowa) list (lista dwukierunkowa) (tablica i string nie są kontenerami STL, ale można je przetwarzać za pomocą algorytmów STL) Asocjacyjne set (drzewo binarne) multiset map, multimap
7 Kontenery vector Zaimplementowany jako tablica dynamicznaszybkie push_back() szybki operator[] wolne insert()
8 Kontenery deque Zaimplementowany jako tablica dynamicznaszybkie push_back() (vector może być szybszy) szybkie push_front() (nieobsługiwany przez vector) szybki operator[] wolny insert()
9 Kontenery list Zaimplementowana jako lista dwukierunkowaszybkie push_back() szybkie push_front() szybkie insert() Nie ma operatora operator[]
10 Iteratory Iteratory zachowują się jak zwyczajne wskaźniki ...* -> ++ -- == != = (vector, deq: -, <, >, +(int) ) Ale działają dla wszystkich kontenerów! container.begin() // zwróć iterator do pierwszego elementu. container.end() // ... do ostatniego przykład: list2.cpp
11 Kontenery set Zaimplementowany jako drzewo binarneSowrtowanie przy wstawianiu (porównywanie domyślnym operatorem<() ) Odpowiednik zbiorów matematycznych metoda find() szybkie insert() nie ma: push_back() nie ma: push_front() nie ma: operatora []
12 Kontenery multiset Dozwolone powtórzenia tej samej wartościUporządkowanie wewnątrz grupy elementów o tych samych wartościach jest niezdefiniowane
13 Kontenery multimap multiset dla par: klucz, wartość – użyj make_pair()
14 Kontenery map Tylko dla kontenera map: operator[key]()set dla par: klucz, wartość – użyj make_pair() Tylko dla kontenera map: operator[key]() Indeksowanie wartością (tablica asocjacyjna)
15 Algorytmy STL Operują na kontenerach za pomocą iteratorówSposób uniwersalny, ale nie tak szybki jak metody kontenerów Dla niektórych kombinacji algorytm/kontener wolne Możliwe jednoczesne działanie na kontenerach różnych typów Tylko podstawowe, proste algorytmy Parametryzowalne przez romaite iteratory Parametryzowalne przez obiekty funkcyjne i adaptory Nie intuicyjne (eufemizm)
16 Algorytmy STL Przykład: algo1.cppmin_element // operator<() max_element // operator<() sort // operator<() find // operator==() reverse // operator=() min_element (coll.begin(), coll.end()) Zakres to [ coll.begin(), coll.end() ) (przykład: find1.cpp) Właściwa definicja zakresu to zadanie programisty Koniec zakresu powinien być osiągany przez ++’owanie początku Co gdy nie mamy pewności co jest końcem a co początkiem?
17 Algorytmy STL copy (coll1.begin(), coll1.end(), coll2.begin());Koniec zakresu podany tylko dla pierwszego zakresu Rozmiar zakresu docelowego musi być wystarczający Algorytm przeprowadza wyłącznie proste nadpisywanie … bez sprawdzania rozmiaru zakresu docelowego (iteratory to interfejs do elementów kontenera, nie do kontenera) Właściwy rozmiar kolekcji to odpowiedzialność/zadanie programisty (przykład: copy2.cpp) Dla niektórych kontenerów (sekwencyjne) ustawienie rozmiaru początkowego jest proste
18 Iteratory STL Wielkość zakresu musi być wystarczająca, albo ...copy (coll1.begin(), coll1.end(), inserter(coll2, coll2.begin()) ); ... albo użyj iteratorów wstawiających (inserter) ;) (copy3.cpp) inserter dla wszystkich kontenerów, które mają metodę insert() Wstawia przed podaną lokalizacją Dla kontenerów asocjacyjnych lokalizacja jest tylko wskazówką back_inserter dla kontenerów, które mają metodę push_back() front_inserter dla kontenerów, które mają metodę push_front()
19 Iteratory STL Iteratory strumienioweZachowują się jak zwyczajne iteratory Mają interfejs zwykłych iteratorów Operują na strumieniach i/o (ioiter1.cpp) istream_iterator
20 Iteratory STL Iteratory odwrotne (reverse iterator)Mają interfejs zwykłych iteratorów Zachowują się odwrotnie (rter1.cpp) container.rbegin() wskazuje na ostatni element (nie pozycję po ostatnim) container.rend() wskazuje na pozycję przed pierwszym! ++ to --, -- to ++, itd.
21 Algorytmy STL Usuwanie elementów z kontenera Algorytm remove(...)Tak naprawdę nie usuwa zawartości kontenera (remove1.cpp) Nie ma dostępu do kontenera, a tylko do elementów Nie działa dla kontenerów asocjacyjnych Zwraca nowy koniec zakresu (element następny po ostatnim) Użyj metody kontener.erase(...) by się pozbyć elementów (remove2.cpp) Wiele wersji Działa dla kontenerów asocjacyjnych (remove3.cpp)
22 Rozszerzanie STL Programista może (a nawet powinien) rozszerzać funkcjonalność STL Tworzyć nowe wzorce, lub klasy/funkcje przykład: print.hpp Słowo kluczowe typename oznacza że argument jest typem W przeciwieństwie do „mutable” to jest użyteczne
23 Funkcja jako argument algorytmuFunkcje jednoargumentowe przykłady: foreach1.cpp, transform1.cpp Predykaty Jeden argument i wynik bool (przykład: prime1.cpp) Dwa argumenty i wynik bool (przykład: sort1.cpp)
24 Obiekt funkcyjny jako argument algorytmuObiekty funkcyjne Zachowują się jak funkcje, ale wykorzystują operator()() foreach2.cpp Są obiektami Lepiej optymalizowane przez kompilator Mogą posiadać zmienne klasowe, „wewnętrzny stan” przekazany jako argument konstruktora (add1.cpp) Można mieć wiele obiektów funkcyjnych tej samej klasy
25 Obiekt funkcyjny jako argument algorytmuPredefiniowane szablony obiektów funkcyjnych less<>, greater <> set
26 Adaptory funkcji Definiują przypadki szczególne użycia funkcjiModyfikują funkcję, gdy wymagany jest inny interfeja (i.e. lista argumentów) bind2nd(less
27 Elementy kontenerów Interfejs zawsze wymaganyKonstruktor kopiujący Operator przypisania Destruktor Interfejs wymagany czasami Konstruktor domyślny operator == operator <
28 STL, błędy i wyjątki Zaprojektowana dla maksymalizacji prędkościW przypadku błędnego użycia (np. *end()=something) zachowanie jest niezdefiniowane, miejmy nadzieją że błąd ujawni się wcześnie Ostrożnie z iteratorami i zakresami Tylko minimalne sprawdzenia są realizowane (wyjątek bad_alloc) Jest wersja debug biblioteki Użyj jej!!! Niektóre metody niektórych kontenerów są „transaction-safe” A niektóre nie są! Sprawdź w dokumentacji!