Wersja 2013-04
Wersja 2013-04
Zaawansowane techniki
programowania
Szablony
Szablony
Człowiek- najlepsza inwestycja
 Zaawansowane techniki programowania
Szablony
vð
Funkcje uogólnione
" Często spotyka się funkcje (algorytmy), które można zastosować do
szerokiej klasy typów i struktur danych. Typowym przykładem jest
funkcja obliczająca maksimum dwu wartości:
int max(int a, int b) {return (a>b)?a:b;};
int max(int a, int b) {return (a>b)?a:b;};
double max(double a,double b) {return (a>b)?a:b;};
double max(double a,double b) {return (a>b)?a:b;};
string max(string a,string b) {return (a>b)?a:b;};
string max(string a,string b) {return (a>b)?a:b;};
skorzystaliśmy tu z dostępnej w C++ możliwości przeładowywania funkcji
skorzystaliśmy tu z dostępnej w C++ możliwości przeładowywania funkcji
main() {
main() {
cout<< max(7,5)<cout<< max(7,5)<cout<< max(3.1415,2.71)<cout<< max(3.1415,2.71)<cout<< max("Ania","Basia")<cout<< max("Ania","Basia")<}}
 Zaawansowane techniki programowania
Funkcje uogólnione
vð
Makra i void
«%
W C++ mamy mechanizm nadpisywania nazw funkcji  jak
widać działający. Ale ile trzeba się napisać ...
«%
Jeszcze w C był wykorzystywany mechanizm makrodefinicji:
" #define max(a,b) ( (a>b)?a:b) )
" Podstawowa wada  brak możliwości debugowania takiego kodu i
trudności z jego prawidłowym tworzeniem
«%
Inne rozwiązanie (też z C) - używanie wskaz
ników typów
ogólnych, takich jak void *,
" Przykład - qsort ze standardowej biblioteki C:
void qsort(void *base, size_t nmemb, size_t size,
void qsort(void *base, size_t nmemb, size_t size,
int(*compar)(const void *, const void *));
int(*compar)(const void *, const void *));
" CiÄ…gle nie jest to rozwiÄ…zanie wystarczajÄ…co elastyczne i
bezpieczne, choć kiedyś było często wykorzystywane.
 Zaawansowane techniki programowania
Funkcje uogólnione
vð
Dziedziczenie
«%
Można się również pokusić o próbę rozwiązania tego problemu
za pomocą mechanizmów programowania obiektowego.
" W sumie jest to bardziej wyrafinowana odmiana rzutowania na void *.
" Polega na zdefiniowaniu ogólnego typu dla obiektów, które mogą być
porównywane, kopiowane, itp...:
class GreaterThanComparable {
class GreaterThanComparable {
public:
public:
virtual bool operator>(const GreaterThanComparable &) const = 0;
virtual bool operator>(const GreaterThanComparable &) const = 0;
};
};
const GreaterThanComparable & max(const GreaterThanComparable &a, const GreaterThanComparable &b) {
const GreaterThanComparable & max(const GreaterThanComparable &a, const GreaterThanComparable &b) {
return (a>b)? a:b;
return (a>b)? a:b;
}}
class Int:public GreaterThanComparable {
class Int:public GreaterThanComparable {
int val;
int val;
public: Int(int i = 0):val(i) {};
public: Int(int i = 0):val(i) {};
operator int() {return val;};
operator int() {return val;};
virtual bool operator>(const GreaterThanComparable &b) const {
virtual bool operator>(const GreaterThanComparable &b) const {
return val > static_cast(b).val;
return val > static_cast(b).val;
}
}
};
};
main() {
main() {
Int a(1),b(2),c;
Int a(1),b(2),c;
c = (const Int &)::max(a,b);
c = (const Int &)::max(a,b);
cout<<(int)c<cout<<(int)c<}}
 Zaawansowane techniki programowania
Funkcje uogólnione
vð
Dziedziczenie
żð
to podejście wymaga sporego nakładu pracy, a więc jest
wysoce niepraktyczne. Ogólnie rzecz biorąc ma ono
następujące wady:
«%
Wymaga dziedziczenia z abstrakcyjnej klasy bazowej
GreaterThanComparable - może być zastosowane tylko do
typów zdefiniowanych przez nas. Inne typy, w tym typy
wbudowane, wymagajÄ… kopertowania w klasie opakowujÄ…cej,
takiej jak klasa Int w powyższym przykładzie.
«%
Ponieważ potrzebujemy polimorfizmu, funkcja operator>()
musi być funkcją wirtualną, a więc musi być funkcją składową
klasy i nie może być typu inline. W przypadku tak prostych
funkcji niemożność rozwinięcia ich w miejscu wywołania może
prowadzić do dużych narzutów w czasie wykonania.
«%
Funkcja max zwraca zawsze referencje do
GreaterThanComparable, więc konieczne jest rzutowanie na
typ wynikowy (tu Int).
 Zaawansowane techniki programowania
Szablony funkcji
vð
Szablony
«%
W C++ wprowadzono mechanizmy programowania
generycznego (uogólnionego).
«%
Opiera się ono o pojęcie szablonu:
" Definicja szablonu funkcji max, odpowiadajÄ…cej definicji 1.1
wygląda następująco:
template T max(T a,T b) {return (a>b)?a:b;};
" Wyrażenie template oznacza, że mamy do czynienia
z szablonem, który posiada jeden parametr formalny nazwany T.
" Słowo kluczowe typename oznacza, że T jest typem (nazwą typu).
" Zamiast słowa typename możmy użyć słowa kluczowego class.
" Nazwa parametru może być następnie wykorzystywana w definicji
funkcji w miejscach, gdzie spodziewamy siÄ™ nazwy typu.

Powyższe wyrażenie definiuje funkcję max, która przyjmuje dwa
argumenty typu T i zwraca wartość typu T, będącą wartością większego
z dwu argumentów. Typ T jest na razie niewyspecyfikowany. W tym
sensie szablon definiuje całą rodzinę funkcji.
 Zaawansowane techniki programowania
Szablony funkcji
vð
Szablony
«%
Pojęcie szablonu:
" KonkretnÄ… funkcjÄ™ z tej rodziny wybieramy poprzez podstawienie za
formalny parametr T konkretnego typu będącego argumentem
szablonu.
" Argument szablonu umieszczamy w nawiasach ostrych za nazwÄ…
szablonu
int i,j,k;
k=max(i,j);
" Wracając do przykładu z początku:
main() {
cout<<::max(7,5)<cout<<::max(3.1415,2.71)<cout<<::max("Ania","Basia")<}
" Warunkiem poprawności szablonu jest istnienie operatorów i funkcji
wykorzystywanych wewnątrz funkcji uogólnionej, zdefiniowanych
dla typu dla którego następuje konkretyzacja
" Poprawność jest sprawdzana na etapie kompilacji
 Zaawansowane techniki programowania
Szablony funkcji
vð
Dedukcja argumentów
«%
Argumenty nie muszą być podawane jawnie
" Jeśli kompilator jest w stanie je wydedukować na podstawie
argumentów, sam dobierze odpowiednie typy
int i,j,k;
k=max(i,j);
" Tylko podstawienie za T int pozwoli na prawidłowe rozwinięcie
funkcji
" Można podać argumenty funkcji uniemożliwiające dopasowanie
wzorca - otrzymamy wtedy błąd kompilacji.
" Mechanizm automatycznego dopasowywania argumentów szablonu
powoduje wyłączenie automatycznej konwersji argumentów funkcji.
" Podanie jawnie argumentów szablonu (w nawiasach ostrych za
nazwą szablonu) jednoznacznie określa sygnaturę funkcji, a więc
umożliwia automatyczną konwersję typów.
 Zaawansowane techniki programowania
Szablony funkcji
vð
Dedukcja argumentów
«%
Argumenty nie muszą być podawane jawnie
" Ilustracja dopasowania szablonu i konwersji typów
template T max(T a,T b) {return (a>b)?a:b;}
main() {
cout<<::max(3.14,2)< // błąd: kompilator nie jest w stanie wydedukowac argumentu
cout<<::max(3.14,2)< cout<<::max(3.14,2)< int i;
cout<<::max(&i,i)< //błąd: nie istnieje konwersja z typu int na int*
" Automatyczna dedukcja parametrów szablonu jest możliwa tylko wtedy, jeśli
parametry wywołania funkcji w jakiś sposób zależą od parametrów szablonu.

Jeśli tej zależności nie ma trzeba parametry podawać jawnie.

Wtedy istotna jest kolejność parametrów na liście. Jeżeli parametry,
których nie da się wydedukować, umieścimy jako pierwsze, wystarczy,
że tylko je podamy jawnie, a kompilator wydedukuje resztę.
 Zaawansowane techniki programowania
Szablony funkcji
vð
Używanie szablonów
«%
Gdzie je definiować / deklarować?
" Z użyciem szablonów wiąże się parę zagadnień niewidocznych w
prostych przykładach.

W językach C i C++ rozdzielamy deklarację funkcji od jej definicji i
umieszczamy deklarację w plikach nagłówkowych *.h, a definicję w plikach
z
ródłowych *.c, *.cpp itp. Pliki nagłówkowe są w czasie kompilacji włączane do
plików, w których chcemy korzystać z danej funkcji, a pliki z
ródłowe są
pojedynczo kompilowane do plików  obiektowych *.o, te następnie łączone w
plik wynikowy.

W pliku korzystającym z danej funkcji nie musimy więc znać jej definicji, a
tylko deklaracjÄ™.

Podobne podejście do kompilacje szablonów nie powiedzie się.
 Zaawansowane techniki programowania
Szablony funkcji
vð
Używanie szablonów
«%
Gdzie je definiować / deklarować?
 Zaawansowane techniki programowania
Szablony funkcji
vð
Używanie szablonów
" Powodem jest fakt, że w trakcie kompilacji pliku utils.cpp kompilator
nie wie jeszcze, że potrzebna będzie funkcja max, wobec
czego nie generuje kodu żadnej funkcji, a jedynie sprawdza
poprawność gramatyczną szablonu. Z kolei podczas kompilacji pliku
main.cpp kompilator już wie, że ma skonkretyzować szablon dla T =
int, ale nie ma dostępu do kodu szablonu.
«%
Gdzie więc zamieszczać?
" Możemy zamieścić wszystkie deklaracje i definicje szablonów w
pliku nagłówkowym, włączanym do plików, w których z tych
szablonów korzystamy.

Podobnie jak w przypadku funkcji inline reguła jednej definicji zezwala na
powtarzanie definicji/deklaracji szablonów w różnych jednostkach
translacyjnych, pod warunkiem, że są one identyczne. Stąd konieczność
umieszczania ich w plikach nagłówkowych.
" Możemy też w jakiś sposób dać znać kompilatorowi, że podczas
kompilacji pliku utils.cpp powinien wygenerować kod dla funkcji
max. Można to zrobić dodając jawne żądanie konkretyzacji
szablonu
 Zaawansowane techniki programowania
Szablony funkcji
vð
Używanie szablonów
«%
Gdzie je definiować / deklarować?
 Zaawansowane techniki programowania
Szablony funkcji
vð
Parametry pozatypowe
«%
Poza parametrami określającymi typ szablony funkcji mogą
przyjmować również parametry innego rodzaju. W obecnym
standardzie parametry pozatypowe mogą być albo innym
szablonem, albo muszą mieć jeden z poniższych typów:
" typ całkowitoliczbowy bądz
typ wyliczeniowy
" typ wskaz
nikowy
" typ referencyjny.
«%
W praktyce z parametrów pozatypowych najczęściej używa się
parametrów typu całkowitoliczbowego:
" template T dot_product(T *a,T *b) {
T total=0.0;
for(size_t i=0;itotal += a[i]*b[i] ;
return total;
};
«%
Zwróćcie uwagę na kolejność parametrów:
double x[3],y[3];
dot_product<3>(x,y);
 Zaawansowane techniki programowania
Szablony funkcji
vð
Parametry pozatypowe
" Używając pozatypowych parametrów szablonów pamiętajcie, że
odpowiadające im argumenty muszą być stałymi wyrażeniami
czasu kompilacji (jeszcze silniej niż w przypadku tablic
statycznych).
vð
Szablony parametrów szablonu
«%
Parametrami szablonu funkcji mogą być również szablony klas.
Szablony parametrów szablonu umożliwiają przekazanie nazwy
szablonu jako argumentu szablonu funkcji.
" Ciekawostka: w jaki sposób można dedukować wartości
pozatypowych argumentów szablonu:
template< template class C,int K> void f(C){
cout<};
template struct SomeClass {};
main() {
SomeClass<1> c1; SomeClass<2> c2;
f(c1); C=SomeClass K=1
f(c2); C=SomeClass K=2
}
 Zaawansowane techniki programowania
Szablony funkcji
vð
Szablony metod
«%
C++ umożliwia definiowanie szablonów metod klasy np.:
struct Max {
template T max(T a,T b) {return (a>b)?a:b;}
};
main() {
Max m;
m.max(1,2);
}
«%
Reguły dotyczące funkcji obowiązują też przy szablonach
metod.
 Zaawansowane techniki programowania
Szablony klas
vð
Typy uogólnione
«%
W językach takich jak Java czy Smalltalk, które posiadają
uniwersalną klasę Object, z której są dziedziczone wszystkie inne
klasy, a nie posiadają szablonów, uniwersalne kontenery są
implementowane właśnie poprzez rzutowanie na ten ogólny typ. W
przypadku C++ to rozwiÄ…zanie nie jest praktyczne, bo C++ nie
posiada pojedynczej hierarchii klas.
 Zaawansowane techniki programowania
Szablony klas
vð
Typy uogólnione
«%
Stosujemy gdy mamy do czynienia z kodem, który w
niezmienionej postaci musimy powielać dla różnych typów.
Sztandarowym przykładem takiego kodu są różnego rodzaju
kontenery (pojemniki), Kod kontenera jest w dużej mierze
niezależny od typu obiektów w nim przechowywanych. Jako
przykład wez
my stos liczb całkowitych.
class Stack {
private:
int rep[N];
size_t top;
public:
static const size_t N=100;
Stack():_top(0) {};
void push(int val) {_rep[_top++]=val;}
int pop() {return rep[--top];}
bool is_empty {return (top==0);}
}
«%
Ewidentnie ten kod będzie identyczny dla stosu obiektów
dowolnego innego typu, pod warunkiem, że typ ten posiada
zdefiniowany operator=() i konstruktor kopiujÄ…cy.
 Zaawansowane techniki programowania
Szablony klas
vð
Szablony klas
«%
Rozwiązaniem są znów szablony, tym razem szablony klas.

template class Stack {
public:
static const size_t N=100;
private:
T _rep[N];
size_t _top;

public:
Stack():_top(0) {};
void push(T val) {_rep[_top++]=val;}
T pop() {return _rep[--_top];}
bool is_empty {return (_top==0);}
};
«%
Tak zdefiniowanego szablonu możemy używać podając jawnie
jego argumenty.
Stack st ;
st.push("jancio");
st.push("wodnik");
st.push("ogonek");
while(!st.is_empty() ){
cout<}
 Zaawansowane techniki programowania
Szablony klas
vð
Dedukcja parametrów
«%
Dla szablonów klas nie ma możliwości automatycznej dedukcji
argumentów szablonu, ponieważ klasy nie posiadają
argumentów wywołania, które mogłyby do tej dedukcji
posłużyć. Jest natomiast możliwość podania argumentów
domyślnych:
template Stack {
...
}
«%
Wtedy możemy korzystać ze stosu bez podawania
argumentów szablonu
«%
Dla domyślnych argumentów szablonów klas obowiązują te
same reguły, co dla domyślnych argumentów wywołania
funkcji.
«%
Należy pamiętać, że każda konkretyzacja szablonu klasy dla
różniących się zestawów argumentów jest osobną klasą:
Stack si;
Stack sd;
sd=si; //błąd: to są obiekty różnych klas
 Zaawansowane techniki programowania
Szablony klas
«%
Próba zdefiniowania operatora przypisania, który np.
przypisywałby do siebie stosy różnych typów, nie jest łatwa,
ponieważ dwa takie stosy nie widzą swoich reprezentacji.
vð
Pozatypowe parametry szablonów klas
«%
Zestaw możliwych parametrów szablonów klas jest taki sam
jak dla szablonów funkcji:
template class Stack {
private:
T rep[N];
size_t top;
public:
Stack():_top(0) {};
void push(T val) {_rep[_top++]=val;}
T pop() {return rep[--top];}
bool is_empty {return (top==0);}
}
 Zaawansowane techniki programowania
Szablony klas
vð
Szablony parametrów szablonu
«%
Można zamiast szablonu użyć zwykłego parametru typu:
template class stos {
C rep;
public:
...
}
«%
i używać go w następujący sposób:
stos > sv;
«%
W przypadku użycia szablonu jako parametru szablonu zapewniamy
konsystencję pomiędzy typem T i kontenerem C, uniemożliwiając
pomyłkę podstawienia niepasujących parametrów:
stos > sv; //niezgodność typów
«%
Mimo że szablon jest lepszy  w STL jest typ. Dzięki temu można
adaptować na stos dowolny kontener, niekoniecznie będący
szablonem.
«%
Szablony kontenerów z STL posiadają po dwa parametry typów, z tym,
że drugi posiada wartość domyślną (standard dopuszcza dowolną ilość
argumentów w implementacji kontenerów STL jak długo będą one
posiadały wartości domyślne)
 Zaawansowane techniki programowania
Szablony klas
vð
Konkretyzacja na żądanie
«%
Konkretyzacja szablonów zazwyczaj odbywa się "na żądanie".
W takim przypadku kompilator będzie konkretyzował tylko
funkcje napotkane w kodzie.
" I tak, jeśli np. nie użyjemy w naszym kodzie funkcji
Stack::pop(), to nie zostanie ona wygenerowana. Można z
tego skorzystać i konkretyzować klasy typami, które nie spełniają
wszystkich ograniczeń nałożonych na parametry szablonu.
Wszystko będzie w porządku jak długo nie będziemy używać funkcji
łamiących te ograniczenia. Np. załóżmy, że do szablonu Stack
dodajemy możliwość jego sortowania:
template void Stack::sort() {
bubble_sort(_rep,N);
};
" Możemy teraz np. używać
Stack > sc;
sc.push( std::complex(0,1));
sc.pop();
" ale nie
sc.sort();
" Konkretyzacja jawna nie będzie w tym przykładzie możliwa
 Zaawansowane techniki programowania
Szablony klas
vð
Typy stowarzyszone
«%
W klasach poza metodami i polami możemy definiować
również typy, które nazywa się stowarzyszonymi z daną klasą.
Przykład:
template Stack {
public:
typedef T value_type;
...
}
" Możemy teraz używać tej definicji w innych szablonach
template void f(S s) {
typename S::value_type total;
while(!s.is_empty() ) {
total+=s.pop();
}
return total;
}

typename jest wymagane, inaczej kompilator założy, że S::value_type
odnosi się do statycznej składowej klasy
" Bez takich możliwości musielibyśmy przekazać typ elementów
stosu w osobnym argumencie. Mechanizm typów stowarzyszonych
jest bardzo często używany w uogólnionym kodzie.
 Zaawansowane techniki programowania
Programowanie uogólnione
«%
Szablony okazały się bardzo silnym narzędziem
" Ich zastosowanie daleko przekracza implementacjÄ™ prostych
kontenerów i można spokojnie stwierdzić, że ich prawdziwy
potencjał jest ciągle odkrywany.
«%
Szablony idealnie wspierajÄ… styl programowania nazywany
programowaniem uogólnionym.
" Polega on na generalizowaniu algorytmów i struktur danych tak,
aby były w dużej mierze niezależne od typów danych, na których
działają lub z których się składają.
«%
W programowaniu uogólnionym ważną rolę gra pojęcie
konceptu.
" Koncept to abstrakcyjna definicja rodziny typów. To pojęcie pełni
podobnÄ… rolÄ™ jak interfejs
" do konceptu należą typy, które spełniają pewne wymagania.

Czyli jeśli coś kwacze jak kaczka to jest to kaczka, a nie: to jest kaczka
jeśli należy do rodziny "kaczowatych"
«%
Przykłady:

Najważniejszą i najbardziej znaną aplikacją programowania ogólnego jest
Standardowa Biblioteka Szablonów (STL - Standard Template Library).

Drugi przykład - repozytorium bibliotek boost.
 Zaawansowane techniki programowania
Programowanie uogólnione
vð
Obiektowość
" Programowanie uogólnione samo w sobie szczególnie obiektowe nie
jest, choć oczywiście wymaga możliwości definiowania własnych
typów.
" Oba style programowania: uogólniony i obiektowy można stosować
razem. Każdy ma swoje charakterystyczne cechy.
żð
Polimorfizm dynamiczny
" Możliwość decydowania o tym jaka funkcja zostanie wywołana pod
danÄ… nazwÄ… nie w momencie kompilacji (czyli pisania kodu), ale w
samym momencie wywołania.
żð
Polimorfizm statyczny
" Możemy zrezygnować z wymuszania typu argumentu wywołania
funkcji poprzez użycie szablonu funkcji:

template void draw_template(T table[],size_t n) {
for(size_t i=0;i table[i].draw();
}
" Taką funkcję możemy wywołać dla dowolnej tablicy, byle tylko
przechowywany typ posiadał metodę draw.
 Zaawansowane techniki programowania
Programowanie uogólnione
vð
Polimorfizm
" Korzystając z szablonów uzyskaliśmy pewien efekt zachowania
polimorficznego.
żð
Polimorfizm statyczny vs. dynamiczny
«%
Dziedziczenie i funkcje wirtualne

umożliwia pracę ze zbiorami niejednorodnych obiektów i korzysta z
polimorfizmu dynamicznego

wymaga wspólnej hierarchii dziedziczenia

wymusza korzystanie ze wskaz
ników lub referencji i funkcji wirtualnych

zazwyczaj generuje mniejszy kod.
«%
Szablony

implementuje polimorfizm statyczny

bezpiecznie obsługuje jednorodne zbiory obiektów

nie trzeba korzystać ze wskaz
ników i referencji ani funkcji wirtualnych

nie musimy korzystać ze wspólnej hierarchii dziedziczenia.

Otrzymany kod może być szybszy
 Zaawansowane techniki programowania
Programowanie uogólnione
vð
Koncepty
«%
Szablony mogą wymagać pewnych zachowań od typów
którymi są specjalizowane (kaczka musi  kwakać )
«%
Można definiować ograniczenia i warunki dla każdego szablonu
osobno
«%
Możemy szukać wspólnych, powtarzających się zestawów
warunków.
" Taki zestaw nazwiemy konceptem i będziemy go traktować jako
abstrakcyjną definicję całej rodziny typów, niezależną od
konkretnego szablonu.
" Typ spełniający warunki konceptu nazywamy modelem konceptu
lub mówimy, że modeluje ten koncept.
" Mając wybrany, dobrze przygotowany zestaw konceptów dla danej
dziedziny, możemy się nimi posługiwać przy definiowaniu typów i
algorytmów uogólnionych.
«%
Koncepty mogą tworzyć hierarchie analogiczne do hierarchii
dziedziczenia

Mówimy, że koncept A jest bardziej wyspecjalizowany niż B (A
is-refinement-of B), jeśli zestaw ograniczeń konceptu B zawiera się w
zestawie ograniczeń konceptu A.
 Zaawansowane techniki programowania
Programowanie uogólnione
vð
Koncepty
«%
Pojęcie konceptu pełni więc przy programowaniu za pomocą
szablonów podobną rolę jak pojęcie interfejsu przy
programowaniu zorientowanym obiektowo.
" W przeciwieństwie do interfejsu jest to jednak pojęcie bardziej
"ulotne", bo nie narzucamy go za pomocÄ… formalnej definicji.
Koncepty definiujemy poprzez mniej lub bardziej ścisłe wypisanie
nakładanych przez nie ograniczeń. Ograniczenia te mogą zawierać
między innymi:

Prawidłowe wyrażenia. Zestaw wyrażeń języka C++, które muszą się
poprawnie kompilować.

Typy stowarzyszone. Ewentualne dodatkowe typy występujące w
prawidłowych wyrażeniach.

Semantyka: znaczenie wyrażeń. Jednym ze sposobów określanie
semantyki jest podawanie niezmienników, czyli wyrażeń, które dla
danego konceptu sÄ… zawsze prawdziwe.

Złożoność algorytmów. Gwarancje co do czasu i innych zasobów
potrzebnych do wykonania danego wyrażenia.
«%
Programowanie uogólnione polega na wyszukiwaniu
konceptów na tyle ogólnych, aby pasowały do dużej liczby
typów i na tyle szczegółowych, aby zezwalały na wydajną
implementacjÄ™.
 Zaawansowane techniki programowania
Programowanie uogólnione
vð
Definiowanie konceptów
«%
Wez
my za przykład szablon funkcji max
template max(T a,T b) {return (a>b)?a:b;}
«%
Jakie koncepty możemy tu odkryć?
" Gramatyka

Jakie warunki musi spełniać typ T, aby podstawienie go jako argument
szablonu max dawało poprawne wyrażenie? Musi mieć zdefiniowany
operator porównania bool operator>(...). Nie jest ważna sygnatura tego
operatora. Nie ma znaczenia jak parametry sÄ… przekazywane, czy
operator jest w klasie, czy jako funkcja, itp... jedno co ważne to że jeśli x
i y są obiektami typu T to wyrażenie:
x>y
jest poprawne (skompiluje siÄ™).

A
atwiej jest przeoczyć fakt, że ponieważ argumenty wywołania są
zwracane i przekazywane przez wartość, to typ T musi posiadać
konstruktor kopiujący. Oznacza to, że jeśli x i y są obiektami typu T to
wyrażenia:
T(x);
T x(y);
T x = y;
sÄ… poprawne.

Spełnienie obydwu tych warunków zapewni nam poprawność
gramatyczną wywołania szablonu z danym typem, tzn. kod się
skompiluje.
 Zaawansowane techniki programowania
Programowanie uogólnione
vð
Definiowanie konceptów
«%
Przykład max c.d.
" Semantyka

Mogłoby sie wydawać, że jest bez znaczenia jak zdefiniujemy
operator>(...). Koncept typu T jest jednak częścią kontraktu dla funkcji
max. Kontrakt stanowi, że jeżeli użytkownik dostarczy do funkcji
argumenty o typach zgodnych z konceptem i o wartościach
spełniających być może inne warunki wstępne, to twórca funkcji
gwarantuje, że zwróci ona poprawny wynik.

Z definicji maksimum żaden element argument funkcji max nie może być
większy od wyniku, czyli wyrażenie
!śąaąmaxśąa , bźąźą'"!śąbąmaxśąa ,bźąźą
musi być zawsze prawdziwe. Jasne jest, że jeśli dla jakiegoś typu X
zdefiniujemy operator porównania tak, aby zwracał zawsze prawdę lub
aby był równoważny operatorowi równości to wyrażenie nie może być
prawdziwe dla żadnej wartości a i b. Musimy narzucić pewne
ograniczenia semantyczne na operator>() - żądanie, aby relacja
większości definiowana przez ten operator była relacją porządku
!śą xÄ…xźą= false ,śąxÄ… yźą'"śą yÄ…zźąÒ! xÄ…z
częściowego:
To rozumowanie można by ciągnąć dalej i zauważyć, że nawet z tym
ograniczeniem uzyskamy nieintuicyjne wyniki w przypadku, gdy obiekty
a i b będą nieporównywalne, tzn. !(a>b) i !(b>a).
 Zaawansowane techniki programowania
Programowanie uogólnione
vð
Comparable i Assignable
«%
Dostaliśmy zbiór warunków, które musi spełniać typ T, aby
móc go podstawić do szablonu funkcji max. Jak go nazwać?
" Comparable - ale istnienie konstruktora kopiujÄ…cego nie ma z tym
nic wspólnego.

Próbujemy upchnąć dwa niezależne pojęcia do jednego worka. Co więcej
bardzo łatwo jest zrezygnować z konieczności posiadania konstruktora
kopiujÄ…cego, zmieniajÄ…c deklaracjÄ™ max na:
template const T& max(const T&,const T&);
Teraz argumenty i wartość zwracana przekazywane są przez referencję i
nie ma potrzeby kopiowania obiektów.
" Logiczne jest wydzielenie dwu konceptów: jednego definiującego
typy porównywalne, drugiego - typy "kopiowalne".

Dalej możemy zauważyć, że istnienie operatora > automatycznie
pozwala na zdefiniowanie operatora < poprzez:
bool operator<(const T& a,const T&b) {return b>a;};

Podobnie istnienie konstruktora kopiujÄ…cego jest blisko zwiÄ…zane z
istnieniem operatora przypisania.
«%
Comparable - obiekty można porównywać za pomocą
operatorów < i >
«%
Assignable - obiekty możemy kopiować i przypisywać do
siebie.
 Zaawansowane techniki programowania
Programowanie uogólnione
vð
Definiowane konceptów
«%
Co z operatorem porównania operator==()?, co z
konstruktorem defaultowym? itd.
«%
Wybór używanych abstrakcji jest zawsze sprawą mniej lub
bardziej subiektywną i silnie zależną od rozpatrywanego
problemu.
«%
Czy dwa pojęcia włączymy do jednego konceptu czy nie
decyduje odpowiedz
na pytanie czy prawdopodobne jest
użycie kiedykolwiek któregoś z tych pojęć osobno?
«%
Koncepty są definiowane dla każdej biblioteki niezależnie
«%
Koncepty STL  poczytajcie na na stronach SGI.
 Zaawansowane techniki programowania
Biblioteka STL
vð
STL
żð
Biblioteka składa się zasadniczo z dwu części, i łącznika:
«%
uogólnionych kontenerów,
«%
uogólnionych algorytmów,
«%
iteratorów.
żð
Kontenery
«%
obiekty służące do przechowywania innych obiektów.

Kontenery w STL są jednorodne, tzn. mogą przechowywać tylko zbiory
(kolekcje) obiektów tego samego typu.
żð
Iteratory
«%
Abstrakcyjny interfejs dostępu do elementów kontenera.

W STL iterator posiada semantykÄ™ wskaz
nika, w szczególności może być
zwykłym wskaz
nikiem, choć normalnie jest to wskaz
nik inteligentny.
std::list l;// gdzieś ją wypełniamy
for(list::iterator it=l.begin();it!=l.end();it++) {
cout<<*it<}
 Zaawansowane techniki programowania
Biblioteka STL
vð
STL
żð
Algorytmy
«%
Uogólnione funkcje oparte na iteratorach
template
T accumulate(InputIterator first, InputIterator last, T init)
{
T total=init;
for( ; first != last;++first)
total+= *first;
return total;
}
 Zaawansowane techniki programowania
Biblioteka STL
vð
Kontenery
żð
Standard C++ definiuje dwa zestawy kontenerów STL:
«%
Sekwencje czyli pojemniki, w których kolejność elementów jest
ustalana przez korzystajÄ…cego z pojemnika (klienta):
" vector
" deque
" list
«%
Kontenery asocjacyjne, czyli pojemniki, w których klient nie ma
kontroli nad kolejnością elementów:
" set
" map
" multiset
" multimap
«%
Różni dostawcy oferują dodatkowe pojemniki ... ale standard to
tylko to co wyżej
 Zaawansowane techniki programowania
Biblioteka STL
vð
Koncepty dla STL
 Zaawansowane techniki programowania
Biblioteka STL
vð
Koncepty dla STL
 Zaawansowane techniki programowania
Biblioteka STL
vð
Kontenery
«%
Ueee ... czy to nie dorabianie teorii na siłę? Trochę tak ...
" Hierarchia ma znaczenie jeśli dodajemy własne elementy do
biblioteki
żð
Kontener jest właścicielem obiektów
" Każde dodanie to kopiowanie, podobnie przesuwanie
" Te operacje wiążą się z realokacją w niektórych kontenerach

Iteratory mogą tracić ważność
std::vector::iterator it;
int i;
std::vector v(1);
v[0]=0;
it=v.begin();
i=(*it);
for(int i=0;i<10;++i)
v.push_back(i);
cout<<(*it)< Zaawansowane techniki programowania
Biblioteka STL
vð
Iteratory
 Zaawansowane techniki programowania
Biblioteka STL
vð
Iteratory
«%
Iterator to uogólniony wskaz
nik
«%
Iterator nie wie jaki kontener wskazuje
«%
Zawsze jest jeden iterator  poza kontenerem - bez
prawidłowej wartości, ale za to prawidłowy iterator
«%
begin() - iterator do poczÄ…tku
«%
end() - iterator poza koniec

Błędny kod:
cout << *(v.end());
«%
Do sprawdzania zakresu stosujcie != a nie < - nie wszystkie operatory
sÄ… uporzÄ…dkowane, wszystkie sÄ… jedynie EqualityComparable
 Zaawansowane techniki programowania
Biblioteka STL
vð
Algorytmy
«%
Algorytmy działają na zakresach elementów kontenera definiowanych
przez dwa iteratory, a nie na kontenerach.
" oznacza to, że algorytmy ogólne nie mogą usuwać elementów z kontenera.
«%
Część algorytmów, np. sort, wymaga bardziej wyrafinowanych
iteratorów, nie dostarczanych przez każdy kontener.
«%
Poza iteratorami uogólnione algorytmy wykorzystują obiekty funkcyjne
czyli funktory.
" Obiekt funkcyjny to koncept będący uogólnieniem pojęcia funkcji, czyli coś
do czego można zastosować składnię wywołania funkcji. W C++ mogą to
być funkcje, wskaz
niki do funkcji oraz obiekty klas, w których zdefiniowano
operator()(...).
«%
Funktory w STL są podzielone ze względu na liczbę argumentów
wywołania.
" Generator nie przyjmuje żadnego argumentu,
" UnaryFunction posiada jeden argument,
" BinaryFunction - dwa argumenty wywołania.
 Zaawansowane techniki programowania
Biblioteka STL
vð
Algorytmy
«%
Ważną podklasą są funkcje zwracające wartość typu bool, nazywane
predykatami.
" UnaryPredicate
" BinaryPredicate.
«%
Przykład  generowanie sekwencji obiektów.
" Funktor:
template class SequenceGen {
private:
T _start;
T _step;
public:
SequenceGen(T start=T(),T step=1 ):_start(start),_step(step){};
T operator()() {T tmp=_start; _start+=_step; return tmp;}
};
" Wypełnienie wektora sekwencją 20 pierwszych nieparzystych liczb całkowitych:
const size_t n = 20 ;
vector v(n);
generate_n(v.begin(),n,SequenceGen(1,2));
 Zaawansowane techniki programowania
Biblioteka STL
vð
Algorytmy
«%
Przykład  generowanie sekwencji obiektów.
" Standardowy algorytm:
template
OutputIterator generate_n(OutputIterator first, Size n, Generator
gen);
" służy właśnie do wypełniania kontenerów za pomocą n kolejnych wyników
wywołania funktora gen.
" W tak wypełnionym można poszukać pierwszego elementu > od czterech
template
InputIterator find_if(InputIterator first,
InputIterator last,Predicate pred);
" Potrzebujemy jeszcze predykatu, który testuje czy dana wartość jest większa
od czterech. Wykorzystajmy adapter funkcji bind2nd - przyjmuje funktor
dwuargumentowy F(T,U) i jakąś wartość x typu U i zwraca funktor
jednoparametrowy F(T,x):
vector::iterator it= find_if(v.begin(),v.end(),
bind2nd(greater(),4));
if(it!=v.end())
cout<<*it<else cout<<"nie znaleziono zadanego elementu"; }