1 Szablony C++ Leszek Mierzejewski

2 Szablony Szablon to funkcja bądź klasa zaimplementowana dla nieokreślonego z góry typu. Typ ten jest określany (w sposób jawny bądź niejawny) w miejscu zastosowania szablonu. Ponieważ szablony są elementami języka, są objęte pełną kontrolą typów i zasięgu widoczności. Szablony pozwalają na parametryzacje działania programu, optymalizację kodu i parametryzacje informacji. We współczesnych programach szablony są wykorzystywane bardzo szeroko.

3 Szablon funkcji Szablony funkcji definiują rodzinę funkcji dla różnych parametrów szablonu. Konstrukcja składniowa template < lista-parametrów-oddzielonych-przecinkami > Słowo kluczowe typename wprowadza do listy parametrów tzw. parametr typu. Z przyczyn historycznych w określeniu parametru typu dopuszcza się stosowanie w miejsc typename słowa kluczowego class. Definiowanie i korzystanie z szablonu funkcji template inline T const& max (T const& a, T const& b) { // jeżeli a < b zwróć b; w przeciwnym przypadku zwróć a return a < b ? b : a; } int main() { ::max(7, 68); ::max(7.0, 42.0); // wywołanie szablonu max (dedukcja typu argumentów) ::max<>(7, 42); // wywołanie szablonu max (dedukcja typu argumentów) ::max(7, 42); // wywołanie szablonu max (bez dedukcji typu)

4 Przekazując w wywołaniu argumenty szablonu, konkretyzujemy szablon funkcji dla wskazanych typów argumentów. Proces zastępowania parametrów szablonu konkretnymi typami nazywamy konkretyzacją (ang. instantiation) szablonu. Efekt konkretyzacji – nowa jednostka (klasa, funkcja lub metoda klasy) – zwany jest ogólnie specjalizacją. Szablony są kompilowane dwukrotnie: Pierwszy raz kod szablonu jest analizowany pod kątem poprawności składniowej. Drugi raz podczas konkretyzacji: kod szablonu jest weryfikowany pod kątem poprawności wszystkich wywołań. Możliwe jest przeciążanie szablonów funkcji. Możliwe jest jawne kwalifikowanie parametrów szablonu. Przeciążając szablony funkcji, należy ograniczać zmiany do jawnego określania parametrów szablonu. Zawsze warto sprawdzić, czy w miejscu wywołania znane są wszystkie wersje przeciążonego szablonu funkcji.

5 Szablony klas Szablon klasy to klasa implementowana równocześnie dla wielu nieokreślonych z góry typów. template class Stack { private: std::vector elems; // elementy public: void push(T const&); // wstawia element na szczyt stosu void pop(); // zdejmuje element ze szczytu stosu T top() const; // zwraca szczytowy element stosu bool empty() const { // czy stos jest pusty? return elems.empty(); } }; Aby skorzystać z szablonu klasy, należy w liście argumentów szablonu określić typ konkretyzacji. Szablon klasy jest dla tego typu konkretyzowany i kompilowany. Stack intStack; // stos elementów typu int Stack stringStack;// stos elementów typu std::string Konkretyzacji podlegają w szablonach klas wyłącznie te metody, które zostały wywołane.

6 Szablony klas można specjalizować dla wybranych typów.template<> class Stack { private: std::deque elems; // elementy public: void push(std::string const&); // wstaw element std::string top() const; ... }; Szablony klas można częściowo specjalizować dla wybranych typów. // specjalizacja częściowa (oba parametry szablonu mają ten sam typ) template class MyClass { } // specjalizacja częściowa (drugi parametr szablonu to int) template class MyClass { // specjalizacja częściowa (oba parametry są typu wskaźnikowego) template class MyClass {

7 Możliwe jest definiowanie wartości domyślnych parametrów szablonów klas. Mogą się one odwoływać do poprzednich parametrów szablonu. template > class Stack { private: CONT elems; // elementy public: void push(T const&); // wstaw element na szczyt stosu void pop(); // usuń element ze szczytu stosu T top() const; // zwróć szczytowy element stosu bool empty() const { // czy stos jest pusty? return elems.empty(); } }; template void Stack::push (T const& elem) { elems.push_back(elem); // dołącz kopię przekazanego elementu // stos elementów typu int: Stack intStack; // stos elementów typu double przechowywany w kontenerze std::deque Stack > dblStack;

8 Inne aspekty szablonówAby odwołać się do nazwy typu uzależnionego od parametru szablonu, należy kwalifikować tę nazwę słowem kluczowym typename. template class MyClass { typename T::SubType * ptr; ... } Klasy zagnieżdżone i metody składowe również mogą być definiowane jako szablony. Przydaje się to między innymi do implementacji operacji ogólnych, wykorzystujących wewnętrzną konwersję typów. Nie eliminuje to naturalnie procesu kontroli typów. template Stack& Stack::operator= (Stack const& op2) { Stack tmp(op2); // utwórz kopię przypisywanego stosu elems.clear(); // usuń istniejące elementy stosu while (!tmp.empty()) { // kopiuj elementy do nowego stosu elems.push_front(tmp.top()); tmp.pop(); return *this;

9 Parametrami szablonów mogą być również szablony klas, jako tak zwane szablony parametrów szablonów.template template typename ALLOC = std::allocator > class CONT = std::deque > class Stack { private: CONT elems; ... } Stack > vStack; Argumenty szablonów parametrów szablonów podlegają ścisłemu dopasowaniu. Dopasowanie to ignoruje argumenty domyślne szablonów parametrów szablonów. Aby zagwarantować inicjalizację składowych i metod szablonów wartościami domyślnymi również dla szablonów konkretyzowanych typami wbudowanymi, należy wykorzystać konstruktor domyślny. template void foo () { T x = T();

10 Literały łańcuchowe (napisy) są podczas dedukcji argumentów poddawane konwersji z typu tablicowego do typu wskaźnikowego tylko wtedy, gdy są przekazywane przez wartość. // uwaga: parametry przekazywane przez referencję template inline T const& max (T const& a, T const& b) { return a < b ? b : a; } int main() { std::string s; ::max("jabłko","wiśnia"); // DOBRZE: typy zgodne ::max("jabłko","pomidor"); // BŁĄD: różne typy ::max("jabłko",s); // BŁĄD: różne typy

11 Zastosowanie szablonówKorzystanie z szablonów oznacza konieczność rewizji tradycyjnego modelu kompilator-konsolidator. Opracowano więc rozmaite metody organizowania kodu szablonów: model włączania, konkretyzację jawną i model separacji. Konkretyzacja jawna // jawna konkretyzacja szablonu klasy Stack<> dla typu int template Stack; // jawna konkretyzacja niektórych metod szablonu klasy Stack<> dla typu std::string template Stack::Stack(); template void Stack::push(std::string const&); Zazwyczaj zalecane jest stosowanie modelu włączania (czyli umieszczenia całości kodu szablonu w plikach nagłówkowych). Rozdzielając definicję i deklarację szablonu pomiędzy różnymi plikami nagłówkowymi, można dowolnie wybierać pomiędzy modelem włączania i modelem konkretyzacji jawnej. Standard języka C++ definiuje dla szablonów model oddzielnej kompilacji (wykorzystujący słowo kluczowe export). Model ten nie doczekał się jeszcze powszechnej implementacji.

12 Siła polimorfizmu szablonówPolimorfizm implementowany przez dziedziczenie Polimorfizm implementowany za pośrednictwem szablonów ograniczony, bo interfejsy typów uczestniczących w polimorfizmie są określone przez projekt klasy bazowej (inwazyjność) nieograniczony, bo interfejsy typów uczestniczących w polimorfizmie nie są z góry określone dynamiczny, bo wiązanie interfejsu z implementacją odbywa się w czasie wykonania statyczny, bo wiązanie interfejsu z implementacją odbywa się w czasie kompilacji Dynamiczny polimorfizm Statyczny polimorfizm łatwa obsługa zbiorów obiektów niejednorodnych potencjalnie mniejszy rozmiar kodu wykonywalnego możliwość pełnej kompilacji kodu łatwa implementacja kolekcji typów wbudowanych potencjalnie większa szybkość działania wygenerowanego kodu możliwość korzystania z typów udostępniających interfejsy częściowe

13 Nowe formy wzorców projektowychInterfejs Implementation *body; operationA() { body->operationA() } operationB() { body->operationB() body->operationC() Implementacja virtual operationA() = 0; virtual operationB() = 0; virtual operationC() = 0; body Implementacja A virtual operationA(); virtual operationB(); virtual operationC(); Implementacja B virtual operationA(); virtual operationB(); virtual operationC(); Impl Interfejs Impl body; operationA() { body.operationA() } operationB() { body.operationB() body.operationC() Implementacja A operationA(); operationB(); operationC(); Implementacja B operationA(); operationB(); operationC();

14 niska szybkość wykonywania (obsługa wywołań wirtualnych), Object Iterator Iterator (Collection&) void reset() Object *operator++() Object *operator() () Collection vrtual void doRest(Iterator &) vrtual Object *doNext(Iterator &) vrtual void doFinish(Iterator &) ... SeqCInt Bag Set Stack LinkedList OrderedCInt IdentSet Dictionary Hierarchia klas biblioteki NIHCL SortedCInt IdentDict Typy kontenerowe były główną motywacją wprowadzenia do języka C++ mechanizmu szablonów. National Institutes of Health Class Library (NIHCL) – biblioteka implementująca kontenery za pośrednictwem hierarchii polimorficznych. Wady NIHCL: niska szybkość wykonywania (obsługa wywołań wirtualnych), duża zajętość pamięci (kopertowanie typów wbudowanych).

15 Klasy cech i wytycznychCechy reprezentacją dodatkowe właściwości parametru szablonu. Wytyczne reprezentują konfigurowalne zachowania ogólnych funkcji i typów. Przykład – kumulowanie ciągu elementów template inline T accum (T const* beg, T const* end) { T total = T(); // zakładamy, że T() utworzy wartość zerową while (beg != end) { total += *beg; ++beg; } return total; Problemy: utworzenie wartości zerowej, określenie typu zmiennej kumulującej.

16 Parametryzacja cech template typename AT = AccumulationTraits > class Accum { public: static typename AT::AccT accum (T const* beg, T const* end) { typename AT::AccT total = AT::zero(); while (beg != end) { total += *beg; ++beg; } return total; }; Szablon AccumulationTraits zwany jest szablonem cechy, gdyż przechowuje cechę parametru typu template class AccumulationTraits; template<> class AccumulationTraits { public: typedef int AccT; static AccT zero() { return 0; } }; template<> class AccumulationTraits { public: typedef long AccT; static AccT zero() { return 0; } };

17 Klasa wytycznych (klasa ukierunkowana) – klasa udostępniająca interfejs jednego lub więcej wytycznych algorytmu. template typename Policy = SumPolicy, typename Traits = AccumulationTraits > class Accum { public: typedef typename Traits::AccT AccT; static AccT accum (T const* beg, T const* end) { AccT total = Traits::zero(); while (beg != end) { Policy::accumulate(total, *beg); ++beg; } return total; }; class SumPolicy { template static void accumulate (T1& total, T2 const & value) { total += value;

18 Biblioteka standardowa udostępnia tak zwane cechy iteratorów.// stl_iterator_base_types.h template typename _Distance = ptrdiff_t, typename _Pointer = _Tp*, typename _Reference = _Tp&> struct iterator { /// One of iterator_tags tag typedef _Category iterator_category; /// The type "pointed to" by the iterator. typedef _Tp value_type; /// Distance between iterators is represented as this type. typedef _Distance difference_type; /// This type represents a pointer-to-value_type. typedef _Pointer pointer; /// This type represents a reference-to-value_type. typedef _Reference reference; };

19 Metaprogramy Metaprogramowanie polega na „programowaniu programu”, a więc na tworzeniu takiego kodu, na podstawie którego system kompilacji wygeneruje inny kod, implementujący docelowy zestaw funkcji programu. Cel: maksymalizacja wydajności, uproszczenie interfejsu. // szablon podstawowy obliczania N-tej potęgi liczby 3 template class Pow3 { public: enum { result = 3 * Pow3::result }; }; // specjalizacja pełna, kończąca rekurencję template<> class Pow3<0> { enum { result = 1 }; Pow3<7>::result

20 Zupełność obliczeniowa zmienne stanu (parametry szablonów), pętle (szablony rekurencyjne), wybór ścieżki obliczeniowej (wyrażenia warunkowe i specjalizacje), arytmetyka liczb całkowitych. Metaprogramowanie w rozwijaniu pętli // Obliczanie iloczynu skalarnego. template inline T dot_product (int dim, T* a, T* b) { T result = T(); for (int i=0; i result += a[i]*b[i]; } return result; Kompilator optymalizuje pętle dla wielu iteracji, co w tym przypadku daje efekt raczej odwrotny od pożądanego. Pożądanym efektem byłoby rozwinięcie pętli do postaci: a[0]*b[0] + a[1]*b[1] + a[2]*b[2]

21 Obliczanie iloczynu skalarnego z wykorzystaniem szablonów.// szablon podstawowy template class DotProduct { public: static T result (T* a, T* b) { return *a * *b + DotProduct::result(a+1,b+1); } }; // specjalizacja częściowa jako kryterium wyjścia z pętli template class DotProduct<1,T> { return *a * *b; // wygodna funkcja inline T dot_product (T* a, T* b) { return DotProduct::result(a,b); Biblioteki takie jak Blitz++, MTL czy POOMA wykorzystują metaprogramy do zwiększenia efektywności procedur numerycznych algebry liniowej.

22 Szablony wyrażeń Szablony wyrażeń opierają się na głęboko zagnieżdżonych konkretyzacjach szablonów. Początkowo służyły wyłącznie do obsługi klas tablic numerycznych. // mnożenie dwóch tablic SArrays template SArray operator* (SArray const& a, SArray const& b) { SArray result(a.size()); for (size_t k = 0; k result[k] = a[k]*b[k]; } return result; int main() { SArray x(1000), y(1000); x = 1.2*x + x*y;

23 Obiekty tymczasowe i rozdzielanie pętliEfektywność takiej implementacji okazuje się być wysoce niezadowalająca, a to z dwóch powodów: Każde zastosowanie operatora powoduje utworzenie przynajmniej jednej tablicy tymczasowej. Każde zastosowanie operatora wymaga dodatkowego przeglądu tablic argumentów i tablicy wynikowej. tmp1 = 1.2 * x tmp2 = x * y tmp3 = tmp1 + tmp2 x = tmp3

24 Kodowanie wyrażeń obliczeniowych za pomocą argumentów szablonów.Wyrażenie 1.2*x + x*y jest tłumaczone do obiektu następującego typu: A_Add< A_Mult< A_Scalar, Array >, A_Mult, Array > > + * * 1.2 x x y Drzewo składniowe odpowiadające wyrażeniu 1.2*x+x*y

25 // klasa obiektów reprezentujących dodawanie dwóch operandówtemplate class A_Add { private: typename A_Traits::ExprRef op1; // pierwszy operand typename A_Traits::ExprRef op2; // drugi operand public: // konstruktor inicjalizujący odwołania do operandów A_Add (OP1 const& a, OP2 const& b) : op1(a), op2(b) { } // oblicz sumę T operator[] (size_t idx) const { return op1[idx] + op2[idx]; // size jest rozmiarem maksymalnym size_t size() const { assert (op1.size()==0 || op2.size()==0 || op1.size()==op2.size()); return op1.size()!=0 ? op1.size() : op2.size(); };

26 Typ Array i operatory template > class Array { // dodawanie dwóch tablic Array template Array > operator+ (Array const& a, Array const& b) { return Array > (A_Add(a.rep(),b.rep())); }

27 Wydajność szablonów wyrażeń i ich ograniczenia.Wiele niewielkich funkcji rozwijanych w miejscu wywołania wywołuje się wzajemnie, co powoduje alokowanie na stosie wielu prostych obiektów szablonów wyrażeń. Szablony wyrażeń nie mogą rozwiązywać wszystkich trudności związanych z tablicowymi obliczeniami numerycznymi. Przykładowo nie da się ich zastosować do mnożenia macierzowego w postaci: x = A*x; Ciekawe zastosowanie szablonów wyrażeń zawiera biblioteka Lambda Library autorstwa Jaakko Jarvi’ego i Gary’ego Powella. Biblioteka ta wykorzystuje w roli szablonów wyrażeń standardowe obiekty funkcyjne. void lambda_demo (std::vector &ones) { std::sort (ones.begin(), ones.end(), *_1 > *_2); } Biblioteka standardowa języka C++ zawiera szablon klasy o nazwie valarray, który miał być wykorzystywany do tablicowych obliczeń numerycznych.

28 Inteligentne wskaźnikiDwa modele posiadania zasobu – z wyłącznym prawem własności i ze wspólnym prawem własności. Bibliotek standardowa C++ zawiera szablon inteligentnych wskaźników, opatrzony nazwą auto_ptr. void do_something() { AnyT *ptr = 0; try { ptr = new AnyT; ptr->perform(); ... } catch (...) { delete ptr; throw; } void do_something() { Holder ptr(new AnyT); ptr->perform(); }

29 Bibliografia "C++ Szablony. Vademecum profesjonalisty" (tytuł oryg. "C++ Template - The Complete Guide") autorstwa Davida Vandevoorde'a i Nicolaia M. Josuttisa, Wydawnictwo Helion, 2003 Dobre omówienia tematu inteligentnych wskaźników można znaleźć w książce „Język C++ bardziej efektywny”, Scott Meyers, Wydawnictwa Naukowo-Techniczne, 1998