Zaawansowane CPP/Wykład 3: Szablony II

Wprowadzenie

Mechanizm szablonów jest bardzo użyteczny ale może się okazać że kod ogólny który szablon implementuje nie nadaje się do stosowania w każdym przypadku. W tej sytuacji mamy do dyspozycji dodatkowe własności implementacji szablonów w C++: przeciążanie i specjalizację. W poniższym wykładzie omówię sposób stosowania tych mechanizmów i różnice pomiędzy nimi.

Przeciążanie szablonów funkcji

Przeciążenie szablonu funkcji, podobnie jak przeciążenie zwykłych funkcji, definiuje nam nowy szablon. Możemy za pomocą przeciążenia zdefiniować np. funkcję służącą do znajdywania maksymalnego elementu w tablicy:

template<typename T> T max(T *data,size_t n) {
T _max = data[0];
for(size_t i=0;i<n;i++i)
        if(data[i]>_max) _max=data[i];
return _max;
}

Oba szablony: powyższy i wcześniej zdefiniowany

template<typename T> T max(T a,T b) {return (a>b)?a:b;};

Przykład 3.1

mogą ze sobą współistnieć i kompilator automatycznie wybierze poprawną definicję na podstawie argumentów wywołania funkcji. Oczywiście w obu przypadkach zadziała mechanizm automatycznej dedukcji argumentu szablonu.

int i,j,k;
double x,t[20];

k=max(i,j);   wywołanie max<int>(int,int)
x=max(t,k);   wywołanie max<double>(double *,int)

(Źródło: Max_overload)

Możemy jednak chcieć nie tyle zdefiniować nową funkcję, ile zmienić kod już istniejącego szablonu tak aby dla pewnego podzbioru parametrów działał inaczej. Np. działanie funkcji max dla dwu wskaźników nie koniecznie jest tym czego byśmy sobie życzyli. Możemy się spodziewać że w tej sytuacji funkcja powinna zwrócić wskaźnik do większej wartości a nie wskaźnik o wyższym adresie. Definiujemy więc nowy przeciążony szablon funkcji max:

template<typename T> T* max(T *a,max T *b) {
return ((*a)>(*b))?a:b;
}

(Źródło: Max_overload)

Przykład 3.2

Teraz sytuacja nie jest już jednoznaczna. Kompilator napotykając wyrażenie

int i,j;
max(&i,&j);

może dopasować zarówno orginalny szablon {[##ex:max1|Uzupelnic ex:max1|]} z T = int* lub szablon {[##ex:max2|Uzupelnic ex:max2|]} z T = int. I chodź wydaje się że otrzymamy bład kompilacji, to do głosu dochodzi mechanizm rostrzygania przeciążenia i kompilator wybierze dopasowanie drugiego szablonu jako “bardziej wyspecjalizowanego” tzn. do którego pasuje mniejszy zbiór argumentów. Ewidentnie algorytm rozstrzygania przeciążenia szablonów funkcji nie jest prosty, polega on na częściowym porządkowaniu przeciążonych funkcji według stopnia ich specjalizacji. Dokładny opis tego algorytmu można znaleźć w D. Vandervoorde, N. Josuttis: "C++ Szablony, Vademecum profesjonalisty", rozd. 12. Z grubsza rzecz biorąc szablon funkcji F jest bardziej wyspecjalizowany niż szablon G jeśli każdy zestaw argumentów który da się dopasować do F da sie również dopasować do szablonu G ale nie na odwrót. W naszym przypadku do szablonu {[##ex:max2|Uzupelnic ex:max2|]} da się dopasować argumenty typu (T *,T *), które ewidentnie można dopasować również do szablonu {[##ex:max1|Uzupelnic ex:max1|]}. Na odwrót już nie: np (int,int)pasuje do {[##ex:max1|Uzupelnic ex:max1|]} a do szablonu {[##ex:max2|Uzupelnic ex:max2|]} nie.

Specjalizacja szablonów funkcji

Przy dotychczasowych definicjach szablonów max

template<typename T> T  max(T a,max T b);      (1)
template<typename T> T* max(T *a,max T *b);    (2)
template<typename T> T  max(T *data,size_t n); (3)

będziemy dalej mieli kłopoty z funkcją max wywołaną dla argumentów typu char*. Takie argumenty zwyczajowo oznaczają napisy. Zgodne z tym co napisałem wcześniej, wywołany zostanie dla nich przeciążony szablon (2) i porówna tylko pierwsze litery napisów co ewidentnie nie jest tym czego się oczekuje.

Na szczęście można dokonać specjalizacji tego szablonu dla argumentów typu char * i const char *:

template<> char *max<char *>(char *a,char *a) {
        return (strcmp(a,b)>0)?a:b;
      }
template<> const char  *
max<const char *>(const char *a,const char *a) {
        return (strcmp(a,b)>0)?a:b;
      }  

Jak zwykle możemy pominąć argumenty szablonu podane w nawiasach ostrych za nazwą szablonu jeśli mogą być one wydedukowane na podstawie argumentów wywołania i częściej spotkamy się z następującym kodem:

template<> char *max(char *a,char *a) {
        return (strcmp(a,b)>0)?a:b;
      }
template<> const char  *
max(const char *a,const char *a) {
        return (strcmp(a,b)>0)?a:b;
      }  

(Źródło: Max_spec.cpp)

Powyższe specjalizacje są pełne, tzn. określają dokładnie wszystkie argumenty wywołania szablonu. Dlatego lista parametrów szablonu w tych szablonach jest pusta. Tylko takie specjalizacje są dozwolone dla szablonów funkcji. Specjalizacja w przeciwieństwie do przeciążenia musi dotyczyć już istniejącego szablonu. Dlatego nie dozwolona jest specjalizacja:

template<> const char *
max<char *>(char *a,const char *a) {
  return (strcmp(a,b)>0)?a:b;}

(Źródło: Max_spec.cpp)

Przykład 3.3

Ponieważ argumenty są typu char * i const char *, i jako takie nie pasują do żadnego z istniejących szablonów (1-3). Musimy więc zdefiniować kolejne przeciążenie:

template<typename T> const T* max(T *a,const T*b) {
return (*a)>(*b))?a:b;
}

i dopiero wtedy kompilacja kodu 3.3 się powiedzie możliwa. Sytuację podsumowuje rysunek 3.1.

<flash>file=cpp-3-max_spec1.swf|width=600|height=350</flash>

<div.thumbcaption>Rysunek 3.1.

Jawne podstawienie argumentów szablonu w miejsce parametru, może prowadzić w przypadku istnienia szablonów przeciążonych do powstanie szeregu przeciążonych funkcji. Wtedy obowiązują "zwykłe" reguły rozstrzygania przeciążenia np. wyrażenie

max<int>(0,0);

spowoduje "wygenerowanie" trzech funkcji

int   max(int,int);
int  *max(int *,int*);
int   max(int *,int);

(Źródło: Max_over_explicit.cpp)

Ponieważ zero lepiej pasuje do int-a niż do wskaźnika na int wybrana zostaniene pierwsza z powyższych funkcji.

Funkcje zwykłe a szablony

Obok szablonów mogą istnieć zwykłe funkcje o tej samej nazwie. Algorytm rozstrzygający przeciążenie preferuje dopasowanie zwykłych funkcji nad szablonami więc jeśli, zdefiniujemy sobie funkcję

int max(int i, int j)

to kompilator dokona następujących podstawień:

max(0,1);     zwykla funkcja int max(int,int)
max(0,1.0);   zwykla funkcja int max(int,int) z rzutowaniem double na int
max(1.0,1.0); szablon max<double>(double, double)

(Źródło: Maxfunc.cpp)

Z pozoru specjalizacje pełne opisane w poprzedniej części zachowują się jak zwykłe funkcje i moglibyśmy napisać:

char *max(char *a,char *a) {
        return (strcmp(a,b)>0)?a:b;}

zamiast

template<> char *max<char *>(char *a,char *a) {
        return (strcmp(a,b)>0)?a:b;}

Jest tak jednak tylko, jeśli możliwa jest dedukcja argumentów szablonu. W przypadku szablonu

template<typename T,typename U> T convert(U u) {
        return static_cast<T>(u);
};

możememy zdefiniować np. specjalizacje:

template<> int    convert<int,double>(U u) {...};
template<> double convert<double,double>(U u) {...};

i używać ich podając jawnie pierwszy, niededukowalny argument szablonu:

convert<int>(3.14);
convert<double>(2.71);

natomiast zdefiniowane dwu funkcji o tej samej nazwie i argumentach wywołania, różniących się tylko zwracanym typem nie jest możliwe.

Nieudane podstawienie nie jest błędem

Jawne podstawienie wszystkich argumentów szablonu funkcji generuje nam jedną lub więcej funkcji "zwykłych". Może się jednak zdażyć że niektóre podstawienia generują niepoprawny kod:

template<typename T> typename T::value t(T x) {
cerr<<"t1"<<endl;
};

Wywołanie

  t<int>(0);

(Źródło: Sfinae.cpp)

prowadz do int::value i jest nieprawidłowe. Spowoduje to błąd kompilacji ale tylko wtedy jeśli nie bedzie innych przeciążonych szablonów funkcji t. Jeśli dodamy przeciążenie

template<typename T> void t(T x ) {cerr<<"t2"<<endl;};

(Źródło: Sfinae.cpp)

to wyrażenie t<int>(0) zostanie do niego dopasowane. Innymi słowy algorytm dopasowanie przeciążenia pomija błędne podstawienia nie generując błędów kompilacji.

Specjalizacje szablonów klas

Podobnie jak dla szablonów funkcji również dla szablonów klas istnieje możliwość podania różnych implementacji dla różnych zestawów argumentów szablonu. W przeciwieństwie jednak do szablonów funkcji szablony klas nie mogą być przeciążane a jedynie specjalizowane. Oznacza to w programie może istnieć tylko jeden szablon podstawowy o danej nazwie. Szablon podstawowy to szablon w którego definicji nie występują nawiasy ostre po nazwie szablonu. Wszystkie szablony prezentowane do tej pory były podstawowe. Z tej reguły wynika że trzy zdefiniowane do tej pory szablony stosu

template<typename T> Stack {...};
template<typename T,int N = 100> stos {...}; błąd szablon Stack juz istnieje
template<typename T,template<typename X> C> Stack {
C<T> _rep;
} błąd szablon Stack juz istnieje

nie mogą istnieć razem! Oczywiście w przypadku zastosowania domyślnych parametrów szablonu pierwsza definicja jest niepotrzebna, ale również bardziej pożyteczny trzeci szablon jest niedozwolony.

To ograniczenie można po części obejść dokonując specjalizacji częściowej która jest dozwolona tylko dla szablonów klas i daje możliwość specjalizacji szablonu dla pewnego podzbioru jego argumentów a nie dla pojedynczego zestawu jak specjalizacja pełna. Oczywiście specjalizacja pełna też jest możliwa. Rozważmy następujący przykład: definiując szablon podstawowy:

template<typename T,int N = 100> class Stack {};

możemy dokonać następujących specjalizacji:

template<typename T>        class Stack<T,666>     {}; 
template<typename T,int N>  class Stack<T*,N>      {};
template<int N>             class Stack<double ,N> {};
template<int N>             class Stack<int *,N>   {};
template<>                  class Stack<double,666>{};
template<>                  class Stack<double *,44> {};

(Źródło: Stackspec.cpp)

Każda z tych specjalizacji definiuje pewien podzbiór parametrów szablonu podstawowego (zob. rysynek {[##fig:zbiory|Uzupelnic fig:zbiory|]}). Jeśli któryś z podzbiorów zawiera się w drugim to mówimy że jedna specjalizacja jest bardziej wyspecjalizowana od drugiej. Hierarchia specjalizacji dla powyższego przykładu pokazana jest na rys. {[##fig:specstos|Uzupelnic fig:specstos|]}. Jeżeli jakiś zestaw parametrów należy do dwu (lub więcej podzbiorów) które się przecinaja ale żeden nie zawiera się w drugim, to dla tych parametrów kompilator nie bedzie w stanie wybrać specjalizacji.

<flash>file=cpp-3-zbiory.swf|width=500|height=350</flash>

<div.thumbcaption>Rysunek 3.2. Symboliczne przedstawienie zbiorów argumentów dla różnych specjalizacji szablonu Stack<T,N>.

<flash>file=cpp-3-specstos.swf|width=500|height=350</flash>

<div.thumbcaption>Rysunek 3.3. Uporządkownie specjalizacji szablonu Stack<T,N>.

Oczywiście ten przykład jest bardzo sztuczny i trudno sobie wyobrazić powód tworzenia takich specjalizacji. Rozważmy bardziej realistyczny przypadek: Deklarujemy szablon podstawowy, ale bez podawania jego definicji. Będziemy korzystac jedynie z jego spejalizacji:

template<typename T,int N = 100, typename R = T*> class Stack;

Następnie definiujemy dwie specjalizacje. Pierwszą dla stosów opartych o zwykłe tablice:

template<typename T,int N> class Stack<T,N,T*> {
T _rep[N];
unsigned int _top;
public:
Stack():_top(0){};
void push(T e) {_rep[_top++]=e;}
T pop() {return _rep[--_top];}
};

i drugą opartą o kontenery STL:

template<typename T,int N,template<typename E> class Sequence> 
class Stack<T,N,Sequence<T> > {
Sequence<T> _rep;
public:
void push(T e) {_rep.push_back(e);};
T pop() {T top = _rep.top();_rep.pop_back();return top;}
bool is_empty() const {return _rep.empty();}
};

(Źródło: Stack_2.cpp)

Korzystając z tych specjalizacji możemy pisać następujący kod.

main() {
  Stack<int,100,int *>            s_table;
  Stack<int,100>                  s_default ;
  Stack<int,0,std::vector<int> >  s_container;
}

(Źródło: Stack_2.cpp)

W każdym przypadku kompilator wybierze implementację odpowiednią dla podanych parametrów.

Szablony a dziedziczenie

Szablony klas mogą oczywiście dziedziczyć z innych klas. Deklaracja

template<typename T> Stack: public Container {
...
}; 

Oznacza to że każda instancja danego szablonu Stack<T> dziedziczy z klasy Container. Ponieważ konkretna instancja szablonu jest klasą to dowolna klasa czy szablon może dziedziczyć z instancji szablonu:

class special Stack_int : public Stack<int> {...}

Definiując specjalizację szablonu klasy możemy dziedziczyć z innych specjalizacji tej samej klasy, nie może to jednak prowadzić do rekurencji. Jeśli napiszemy:

template<typename T,int N> Stack {...};
template<typename T> 
Stack<T*,N>: private Stack<void *,N> {...};

(Źródło: Stackvoid.cpp)

to kompilator odmówi skompilowania tego kodu z powodu rekurencyjnej definicji specjalizacji szablonu Stack. Wszystko będzie w porządku jeśli dodamy specjalizację dla typu void *:

template<int N> class Stack<void *,N> {...}

(Źródło: Stackvoid.cpp)

Dlaczego mielibyśmy jednak dziedziczyć implementację klasy void*? Powodem jest unikanie powielania kodu. Ponieważ każda konkretyzacja (instancja) szablonu jest osobną klasa, to dla każdej generowany jest pełny kod potrzebnych funkcji. Jesli te funkcje są proste to nie jest to kłopot. W praktyce implementacja stosu musi zwykle uwzględniać dynamiczne zarządzanie pamięcią i może być dużo bardziej skomplikowana a zatem generowany kod będzie odpowiednio większy. Ogólnie jest to nie do uniknięcia, ale ponieważ wszystkie wskaźniki mają ten sam rozmiar i można je rzutować na void * to możemy wykorzystać implementację Stack<void *> do implementacji pozostałych typów wskaźnikowych:

template<typename T,size_t N> 
Stack<T*,N>: private Stack<void *,N> {
public:
   T* pop() {
     return static_cast<T*>(Stack<void *>::pop());
   };

   void push(T *e) {
     Stack<void *>::push(e);
   }

   bool is_empty() {return Stack<void *>::is_empty();} 
};

(Źródło: Stackvoid.cpp)

Korzystamy tu z automatycznej konwersji T* na void *. W ten sposób np. kod funkcji Stack<int *>::push(int *) będzie zawierał tylko parę instrukcji opakowujących wywołanie kodu funkcji Stack<void *>::push(void *). Proszę zwrócić uwagę na zastosowanie dziedziczenia prywatnego.

Zależne klasy bazowe

Szablon klasy może również dziedziczyć z innego szablonu klasy którego argumenty bedą zależały od jego parametrów:

template <typename T> class Base<T> {...};
template<typename S> 
class Derived: public Base<S> {};

przy tych definicjach klasa Derived<double> dziedziczy z klasy Base<double>. Taką klasę nazywamy zależną klasą bazową i jest to bardzo częsta konstrukcja w programowaniu uogólnionym.

Z zależnymi klasami bazowymi wiąże się jednak pewna zasada, związana z wyszukiwaniem nazw, która może być sporym zaskoczeniem. Rozważmy następujący przykład:

template<typename T>  class Base {
public:
  Base():basefield(0){};
  int basefield;
};
template<typename T> class DD :public Base<T> {       
public:
  void f() {std::cerr<<basefield<<std::endl;} 
};

(Źródło: Base.cpp)

Ten kod się nie skompiluje przy pomocy kompilatora C++ zgodnego ze standardem. Ten fakt mało nie przyprawił mnie o zawał serca, kiedy kod nad którym pracowałem ponad miesiąc przestał się kompilować. Dopiero po dobrej chwili zorientowałem się że powodem jest zmiana kompilatora z g++-3.3 na g++3.4 a nie wirus który uszkodził kod źródłówy.

Powód tego faktu jest następujący: nazwa basefield występująca w klasie DD jest nazwą niezależna (od parametru szablonu). Klasa bazowa w której ta nazwa jest zdefiniowana jest klasą bazową zależną (od parametru szablonu). Według standardu kompilator nie wyszukuje nazw niezależnych w zależnych klasach bazowych. Kompilator g++3.4 jest bliżej stadardu niż g++-3.3 i stąd to całe zamieszanie. Więcej o tym napiszę w module <nazwy>, a na razie podam tylko rozwiązanie problemu. Należy uczynić tą nazwę zależną np.poprzez kwalifikowanie jej nazwą klasy:

template<typename T> class DD :public Base<T> {       
public:
  void f() {std::cerr<<basefield<<std::endl;} 
};

(Źródło: Base.cpp)

lub przez

template<typename T> class DD :public Base<T> {       
public:
  void f() {std::cerr<<this->basefield<<std::endl;} 
};

(Źródło: Base.cpp)

CRTP

Dziedziczenie szablonów można też wykorzystać do przydatnej "sztuczki" zwanej po angielsku "couriously reccuring template pattern" (CRTP). Rozważmy następujący problem: chcemy zaimplementować mechanizm automatycznego liczenia ilości obiektów danej klasy. To standardowe zadanie na zastosowanie konstruktorów, destruktorów i statycznych składowych klasy:

class Countable {
protected:
static size_t _counter;
public:
Countable() {++_counter;};
Countable(const Countable &) {++_counter;};
virtual ~Countable {--_counter};

static size_t counter()  {return _conter;} 
};

size_t Contable::_counter = 0;

Oczywiście wspisywanie tego kodu do każdej klasy której obiekty chcemy zliczać jest nużące i łamie zasadę niepowielania kodu. Postaramy się więc wykorzystać kod klasy Countable dziedzicząc go w innych klasach:

class MyClass1 : public Countable {
...
};

class MyClass2 : public Countable {
...
};

Niestety ponieważ obie klasy MyClass1 i MyClass2 dziedziczą z tej samej klasy, dziedziczą również ten sam wspólny licznik. Tak więc zliczaniu podlegać będą obiekty obu klas wspólnie. W rozwiązaniu pomogą nam szablony. Wystarczy uczynić klasę Countable szablonem

template<tyname T> class Countable {
protected:
static size_t _counter;
public:
Countable() {++_counter;};
Countable(const Countable &) {++_counter;};

virtual ~Countable() {--_counter};
static size_t counter()  {return _counter;} 
};
template<typename T> size_t Contable<T>::_counter = 0;

(Źródło: Countable.cpp)

i używać go w następujący sposób:

class MyClass1 : public Countable<MyClass1> {
...
};

class MyClass2 : public Countable<MyClass2> {
...
};

(Źródło: Countable.cpp)

Ponieważ każda konkretyzacja szablonu jest osobną klasą, klasy MyClass1 i MyClass2 dziedziczą z różnych klas bazowych i będą posiadać różne liczniki, ale ciągle wspólne w ramach każdej klasy. Parametryzowanie klasy bazowej typem klasy dziedziczącej gwarantuje jej unikatowość.