Zaawansowane CPP/Wykład 12: Używanie funktorów: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m (→‎Wstęp: lit.)
 
(Nie pokazano 49 wersji utworzonych przez 3 użytkowników)
Linia 2: Linia 2:
  
 
W poprzednim wykładzie omawiałem pojęcie obiektu funkcyjnego, jako
 
W poprzednim wykładzie omawiałem pojęcie obiektu funkcyjnego, jako
uogolnienia wskaźników do funkcji. I choć funktory można wywoływać
+
uogólnienia wskaźników do funkcji. I choć funktory można wywoływać
 
bezpośrednio tak jak funkcje, to dużo częściej używa się ich jako
 
bezpośrednio tak jak funkcje, to dużo częściej używa się ich jako
parametrów przekazywanych do innych funkcji, w celu dostarczenie tej
+
parametrów przekazywanych do innych funkcji, w celu dostarczenia tej
 
funkcji informacji koniecznych do wykonania swojego zadania. W tej
 
funkcji informacji koniecznych do wykonania swojego zadania. W tej
kategorii zastosowań mieści się większość bibliotek, w tym STL gdzie
+
kategorii zastosowań mieści się większość bibliotek, w tym STL, gdzie
funktory służa jako argumenty do uogólnionych algorytmów. Przykłady
+
funktory służą jako argumenty do uogólnionych algorytmów. Przykłady
 
takich zastosowań były już podawane w poprzednich wykładach, a na tym
 
takich zastosowań były już podawane w poprzednich wykładach, a na tym
 
wykładzie omówię je trochę bardziej szczegółowo.
 
wykładzie omówię je trochę bardziej szczegółowo.
Linia 15: Linia 15:
 
jej wykonania. Wygląda to zwykle następująco: Klient definiuje funkcje
 
jej wykonania. Wygląda to zwykle następująco: Klient definiuje funkcje
 
i przekazuje ich wskaźniki do aplikacji, aplikacja wywołuje te funkcje
 
i przekazuje ich wskaźniki do aplikacji, aplikacja wywołuje te funkcje
w wybranym przez siebie czasie. Klient nie ma pojęcie kiedy zostaną
+
w wybranym przez siebie czasie. Klient nie ma pojęcia kiedy zostaną
 
wywołane przekazane przez niego funkcje, a aplikacja nie wie jakie
 
wywołane przekazane przez niego funkcje, a aplikacja nie wie jakie
 
one mają działanie. Taka technika funkcji zwrotnych
 
one mają działanie. Taka technika funkcji zwrotnych
 
(callbacks) jest podstawą implementacji wielu szkieletów graficznych
 
(callbacks) jest podstawą implementacji wielu szkieletów graficznych
interfejsów użytkownika i w <i>"patterns"</i> wymieniona jest jako wzorzec
+
interfejsów użytkownika i w E. Gamma, R. Helm, R. Johnson, J. Vlissides <i>"Wzorce projektowe. Elementy oprogramowania obiektowego wielokrotnego użytku"</i> wymieniona jest jako wzorzec
 
polecenie. Aby używać funktorów definiowanych na poprzednim wykładzie,
 
polecenie. Aby używać funktorów definiowanych na poprzednim wykładzie,
we wzorcu polecenie trzeba będzie je troche dostosować. Zostanie to
+
we wzorcu polecenie trzeba będzie je trochę dostosować. Zostanie to
 
opisane w drugiej części tego wykładu.
 
opisane w drugiej części tego wykładu.
  
 
==Algorytmy  uogólnione i programowanie funkcyjne==
 
==Algorytmy  uogólnione i programowanie funkcyjne==
  
Algorytmy stanowią jak już to opisałem w rozdziale <font color=red>{[##|Uzupelnic |]}</font> jedną z części biblioteki STL, większośc z tych algorytmów posiada wersje
+
Algorytmy stanowią, jak już to opisałem w [http://osilek.mimuw.edu.pl/index.php?title=Zaawansowane_CPP/Wyk%C5%82ad_2:_Programowanie_uog%C3%B3lnione  wykładzie 2], jedną z części biblioteki STL, większośc z tych algorytmów posiada wersje
przyjmujące funktor jako jeden z argumentów. Ne jest moim celem
+
przyjmujące funktor jako jeden z argumentów. Nie jest moim celem
 
przedstawianie tutaj wszystkich algorytmów, jest ich zresztą blisko
 
przedstawianie tutaj wszystkich algorytmów, jest ich zresztą blisko
100, choć gorąco zachęcam państwa do zapoznania się z nimi. W tym celu
+
100, choć gorąco zachęcam Państwa do zapoznania się z nimi. W tym celu
polecam książke STL i stronę <tt>www.sgi.com/tech/stl/</tt>.
+
polecam książke N.M. Josuttis <i>"C++ Biblioteka Standardowa. Podręcznik programisty"</i> i stronę [http://www.sgi.com/tech/stl/ http://www.sgi.com/tech/stl/].
Znakomita jest też pozycja STL, jak zresztą wszystkie
+
Znakomita jest też pozycja S. Meyers <i>"STL w praktyce. 50 sposobów efektywnego wykorzystania"</i>, jak zresztą wszystkie
 
książki tego autora.
 
książki tego autora.
  
W tym wykładzie chciałbym tylko zwrócić uwagę że biblioteka algorytmów
+
W tym wykładzie chciałbym tylko zwrócić uwagę, że biblioteka algorytmów
 
wprowadza do C++ elementy programowania funkcyjnego. Programowanie
 
wprowadza do C++ elementy programowania funkcyjnego. Programowanie
 
funkcyjne polega, z grubsza rzecz biorąc, na zastępowaniu pętli
 
funkcyjne polega, z grubsza rzecz biorąc, na zastępowaniu pętli
poleceniami które potrafią wywołać daną funkcję na każdym elemencie
+
poleceniami, które potrafią wywołać daną funkcję na każdym elemencie
 
danej kolekcji. Taki styl programowania jest często spotykany w
 
danej kolekcji. Taki styl programowania jest często spotykany w
 
językach interpretowanych, np. używa go pakiet <tt>Mathematica</tt>,
 
językach interpretowanych, np. używa go pakiet <tt>Mathematica</tt>,
 
podobnie pakiet do obliczeń numerycznych w Perlu: Perl Data Language i
 
podobnie pakiet do obliczeń numerycznych w Perlu: Perl Data Language i
 
wiele innych. Biblioteka STL oferuje tylko namiastkę tego stylu, ale
 
wiele innych. Biblioteka STL oferuje tylko namiastkę tego stylu, ale
właśnie nią chciałbym przedstawić w tej części wykładu.  
+
właśnie chciałbym przedstawić w tej części wykładu.  
  
Podstawą programowania funkcyjnego są funkcje które wywołują inne
+
Podstawą programowania funkcyjnego są funkcje, które wywołują inne
 
funkcje na każdym obiekcie z kolekcji. STL oferuje kilka takich algorytmów,
 
funkcje na każdym obiekcie z kolekcji. STL oferuje kilka takich algorytmów,
 
podstawowym z nich jest <tt>for_each</tt>.
 
podstawowym z nich jest <tt>for_each</tt>.
Linia 57: Linia 57:
 
modyfikować wywoływany obiekt i może powodowac inne skutki uboczne.
 
modyfikować wywoływany obiekt i może powodowac inne skutki uboczne.
 
Jego kopia jest zwracana po wykonaniu wszystkich operacji. Wartość
 
Jego kopia jest zwracana po wykonaniu wszystkich operacji. Wartość
zwracana przez funktor <tt>op</tt> jest ignorowana.
+
zwracana przez funktor <tt>op</tt> jest ignorowana. Algorytm zwraca kopię funktora <tt>op</tt>.
  
 
Podobnym algorytmem jest <tt>transform</tt>. W swojej pierwszej wersji
 
Podobnym algorytmem jest <tt>transform</tt>. W swojej pierwszej wersji
Linia 65: Linia 65:
 
                           OutputIterator result, UnaryFunction op);
 
                           OutputIterator result, UnaryFunction op);
  
działa  podobnie jak <tt>for_each</tt>, z tą różnicą że wyniki wywołania
+
działa  podobnie jak <tt>for_each</tt>, z tą różnicą, że wyniki wywołania
operacji <tt>op<tt> na wartościach zakresu <tt>[firts,last)</tt> są zapisywane poprzez
+
operacji <tt>op</tt> na wartościach zakresu <tt>[firts,last)</tt> są zapisywane poprzez
 
iterator <tt>result</tt>. Ważną cechą tego algorytmu jest to, że może on operować
 
iterator <tt>result</tt>. Ważną cechą tego algorytmu jest to, że może on operować
 
na dwu wejściowych zakresach. Jego druga wersja
 
na dwu wejściowych zakresach. Jego druga wersja
Linia 81: Linia 81:
 
iterator wyjściowy <tt>result</tt>.
 
iterator wyjściowy <tt>result</tt>.
  
Warto też zwrócić uwagę na algorytmu numeryczne, które pomimo ich
+
Warto też zwrócić uwagę na algorytmy numeryczne, które pomimo ich
nazwy mogą spokojnie zostać użyte do innych ogólnych zastosowań. Są to
+
nazwy mogą spokojnie zostać użyte do innych ogólnych zastosowań. Są to:
  
 
  template <class InputIterator, class T, class BinaryFunction>
 
  template <class InputIterator, class T, class BinaryFunction>
Linia 88: Linia 88:
 
               BinaryFunction op);
 
               BinaryFunction op);
  
który oblicza uogólnioną sumę podanego zakresu:
+
który oblicza uogólnioną sumę podanego zakresu
  
 
<center><math>\displaystyle  
 
<center><math>\displaystyle  
Linia 95: Linia 95:
 
</math></center>
 
</math></center>
  
<tt>inner_product<tt>
+
iloczyn skalarny <tt>inner_product</tt>:
 
  template <class InputIterator1, class InputIterator2, class T,
 
  template <class InputIterator1, class InputIterator2, class T,
 
           class BinaryFunction1, class BinaryFunction2>
 
           class BinaryFunction1, class BinaryFunction2>
Linia 102: Linia 102:
 
                 BinaryFunction2 op2);
 
                 BinaryFunction2 op2);
  
który oblicza uogólniony iloczyn skalarny:
+
który oblicza uogólniony iloczyn skalarny
  
 
<center><math>\displaystyle  
 
<center><math>\displaystyle  
Linia 108: Linia 108:
 
</math></center>
 
</math></center>
  
oraz sumy i różnice cześciowe:
+
oraz sumy i różnice częściowe:
  
 
  template <class InputIterator, class OutputIterator, class BinaryOperation>
 
  template <class InputIterator, class OutputIterator, class BinaryOperation>
Linia 119: Linia 119:
 
                                     BinaryFunction op);
 
                                     BinaryFunction op);
  
zwracające w poprzez iterator <tt>result</tt> odpowiednio:
+
zwracające poprzez iterator <tt>result</tt> odpowiednio:
  
 
<center><math>\displaystyle  
 
<center><math>\displaystyle  
Linia 130: Linia 130:
 
a_1,a_2 \operatorname{op} a_1,a_3 \operatorname{op} a2,\ldots, a_{n} \operatorname{op} a_{n-1}
 
a_1,a_2 \operatorname{op} a_1,a_3 \operatorname{op} a2,\ldots, a_{n} \operatorname{op} a_{n-1}
 
</math></center>
 
</math></center>
 
  
  
Linia 146: Linia 145:
 
   generate_n(back_insert_iterator<list<int> >(li),10,SequenceGen<int>(1,2));<br>
 
   generate_n(back_insert_iterator<list<int> >(li),10,SequenceGen<int>(1,2));<br>
 
   adjacent_difference(li.begin(),li.end(),back_insert_iterator<list<int> >(res),print);
 
   adjacent_difference(li.begin(),li.end(),back_insert_iterator<list<int> >(res),print);
 +
([[media:Sums.cpp | Źródło: sums.cpp]])
  
Ten przykładzik ilustruje niedogodność posługiwania się algorytmami przyjmującymi zakres wyjściowy, takich jak <tt>adjacent_difference</tt> czy <tt>transform</tt>, do prostego działania funkcją, która nie zwraca żadnych wartości. Do tego przeznaczony jest algorytm <tt>for_each</tt>. Niestety, ten algorytm nie pozwala bezpośrednio operować na parach kolejnych elementów, tak jak <tt>adjacent_difference</tt>. To by jeszcze można zasymulować używając odpowiedniego funktora, ale <tt>for_each</tt> nie potrafi operować na parach elementów pochodzych z dwu zakresów, tak jak potrafi to <tt>transpose</tt>.
+
Ten przykładzik ilustruje niedogodność posługiwania się algorytmami przyjmującymi zakres wyjściowy, takimi jak <tt>adjacent_difference</tt> czy <tt>transform</tt>, do prostego działania funkcją, która nie zwraca żadnych wartości. Do tego przeznaczony jest algorytm <tt>for_each</tt>. Niestety, ten algorytm nie pozwala bezpośrednio operować na parach kolejnych elementów, tak jak <tt>adjacent_difference</tt>. To by jeszcze można zasymulować używając odpowiedniego funktora, ale <tt>for_each</tt> nie potrafi operować na parach elementów pochodzących z dwu zakresów, tak jak potrafi to <tt>transpose</tt>.
  
 
Jest kilka możliwości rozwiązania tego problemu. Możemy np. napisać własne algorytmy (zob. zadania). Możemy też dalej korzystać np. z <tt>adjacent_difference</tt> ale napisać narzędzia pomagające adoptować takie algorytmy do naszych celów. Jak by to mogło wyglądać?  
 
Jest kilka możliwości rozwiązania tego problemu. Możemy np. napisać własne algorytmy (zob. zadania). Możemy też dalej korzystać np. z <tt>adjacent_difference</tt> ale napisać narzędzia pomagające adoptować takie algorytmy do naszych celów. Jak by to mogło wyglądać?  
  
Patrzac na nasz przykład i deklaracje <tt>adjacent_difference</tt> widzimy że są dwa problemy: po pierwsze wartość zwracana z funkcji <tt>op</tt> musi być tego samego typu jak typ elementów w zakresie wejściowym, po drugie musimy jakoś "zjeść" te zwracane wartości. Potrzebny więc będzie funktor opakowywujący dowolną funkcję, i zwracający wartość zadanego typu, oraz iterator pełniący rolę <tt>/dev/null</tt>, czyli "czarnej dziury" połykającej wszystko co się do niej zapisze. Mając takie obiekty możemy powyższy kod zapisać następująco:
+
Patrzac na nasz przykład i deklarację <tt>adjacent_difference</tt> widzimy, że są dwa problemy: po pierwsze wartość zwracana z funkcji <tt>op</tt> musi być tego samego typu jak typ elementów w zakresie wejściowym, po drugie musimy jakoś "zjeść" te zwracane wartości. Potrzebny więc będzie funktor opakowujący dowolną funkcję i zwracający wartość zadanego typu, oraz iterator pełniący rolę <tt>/dev/null</tt>, czyli "czarnej dziury" połykającej wszystko co się do niej zapisze. Mając takie obiekty możemy powyższy kod zapisać następująco:
  
 
  void print(int i,int j) {
 
  void print(int i,int j) {
Linia 161: Linia 161:
 
   adjacent_difference(li.begin(),li.end(),dev_null<char>(),dummy<char>(print));
 
   adjacent_difference(li.begin(),li.end(),dev_null<char>(),dummy<char>(print));
  
Obiekt klasy <tt>dev_null<T></tt> to iterator typu <tt>output_iterator</tt> którego <tt>value_type</tt> jest równy <tt>T</tt>. Iterator ten ignoruje wszelkie operacje na nim wykonywane, w tym przypisanie do niego. Funckja <tt>dummy<T>(F f, T val <nowiki>=</nowiki> T())</tt> zwraca funktor który wywołuje funkcję <tt>f</tt> a następnie zwraca wartośc <tt>val</tt> typu <tt>T</tt>. Implementacje tych szablonów pozostawiam jako ćwiczenie (zob. zadania).
+
Obiekt klasy <tt>dev_null<T></tt> to iterator typu <tt>output_iterator</tt>, którego <tt>value_type</tt> jest równy <tt>T</tt>. Iterator ten ignoruje wszelkie operacje na nim wykonywane, w tym przypisanie do niego. Funckja <tt>dummy<T>(F f, T val <nowiki>=</nowiki> T())</tt> zwraca funktor, który wywołuje funkcję <tt>f</tt>, a następnie zwraca wartośc <tt>val</tt> typu <tt>T</tt>. Implementacje tych szablonów pozostawiam jako ćwiczenie (zob. zadania).
  
Pomysły można mnożyć. Jako ostatni zaprezentuję iterator który nie wstawia nic do żadanego kontenera, ale wywołuje na przypisywanym do niego obiekcie jakąś zadaną funkcję:
+
Pomysły można mnożyć. Jako ostatni zaprezentuję iterator, który nie wstawia nic do żądanego kontenera, ale wywołuje na przypisywanym do niego obiekcie jakąś zadaną funkcję:
  
 
  void p(double x) {
 
  void p(double x) {
Linia 175: Linia 175:
 
  std::transform(li.begin(),li.end(),function_iterator<double>(p),frac);
 
  std::transform(li.begin(),li.end(),function_iterator<double>(p),frac);
  
Taki iterator łatwo zaimplementować przy pomocy klas proxy.
+
Taki iterator łatwo zaimplementować przy pomocy klas proxy (zob. zadania).
  
 
==Wzorzec Polecenie==
 
==Wzorzec Polecenie==
  
Wzorzec polecenie najlepiej omówić na przykładzie, jak już wspomniałem
+
Wzorzec polecenie najlepiej omówić na przykładzie. Jak już wspomniałem,
 
typowe zastosowanie to graficzny interfejs użytkownika (GUI). Taki
 
typowe zastosowanie to graficzny interfejs użytkownika (GUI). Taki
 
interfejs musi reagować na różne zdarzenia: kliknięcie myszą,
 
interfejs musi reagować na różne zdarzenia: kliknięcie myszą,
Linia 185: Linia 185:
 
biblioteki GUI nie może wiedziec jakie działanie ma pociągnąć dane
 
biblioteki GUI nie może wiedziec jakie działanie ma pociągnąć dane
 
zdarzenie.  Nawet jednak gdybyśmy sami pisali cały kod, to
 
zdarzenie.  Nawet jednak gdybyśmy sami pisali cały kod, to
"zaszycie" polecenia na stałe w kodzie danego elementu interfejsu,
+
"zaszycie" polecenia na stałe w kodzie danego elementu interfejsu
 
jest bardzo złą praktyką programistyczną. Dlatego używa się w tym celu
 
jest bardzo złą praktyką programistyczną. Dlatego używa się w tym celu
 
funkcji zwrotnych. I tak w jakiejś hipotetycznej klasie  
 
funkcji zwrotnych. I tak w jakiejś hipotetycznej klasie  
Linia 196: Linia 196:
  
 
służącą do przekazania wskaźnika do funkcji, która zostanie wywołana po
 
służącą do przekazania wskaźnika do funkcji, która zostanie wywołana po
naciśnięciu myszką na oknie. Podobnie dla innych kompentów:
+
naciśnięciu myszką na oknie. Podobnie dla innych komponentów:
  
 
  class Button {
 
  class Button {
Linia 203: Linia 203:
 
  ...
 
  ...
 
  }
 
  }
 
itd.
 
  
 
Ponieważ typ funkcji określony jest poprzez typ jej parametrów i typ
 
Ponieważ typ funkcji określony jest poprzez typ jej parametrów i typ
Linia 211: Linia 209:
 
dobrodziejstwa jakie daje nam zastosowanie obiektów funkcyjnych
 
dobrodziejstwa jakie daje nam zastosowanie obiektów funkcyjnych
 
zamiast funkcji, musimy je dziedziczyć ze wspólnej klasy bazowej,
 
zamiast funkcji, musimy je dziedziczyć ze wspólnej klasy bazowej,
ponieważ jedną z podstawowych cech funktorów jest to że posiadają swój
+
ponieważ jedną z podstawowych cech funktorów jest to, że posiadają swój
 
typ.  Żeby więc móc przekazywać różne funktory za pomocą tej samej
 
typ.  Żeby więc móc przekazywać różne funktory za pomocą tej samej
 
sygnatury, musimy je rzutować w górę na wspólny typ. To jest cała
 
sygnatury, musimy je rzutować w górę na wspólny typ. To jest cała
esencja wzorca polecenie (zob. <i>"patterns"</i>).
+
esencja wzorca polecenie (zob. E. Gamma, R. Helm, R. Johnson, J. Vlissides <i>"Wzorce projektowe. Elementy oprogramowania obiektowego wielokrotnego użytku"</i>).
  
Oznacza to jednak że nie możemy skorzystać z całej technologii
+
Oznacza to jednak, że nie możemy skorzystać z całej technologii
wyprowadzanej na poprzednim wykładzie. Szablony też nam nie pomogą,
+
wyprowadzonej na poprzednim wykładzie. Szablony też nam nie pomogą,
 
ponieważ wenątrz elementów GUI musimy jakoś przechować funktor
 
ponieważ wenątrz elementów GUI musimy jakoś przechować funktor
zwrotny. Aby przechowayć różne funktory musielibysmy parametryzować
+
zwrotny. Aby przechowywać różne funktory musielibyśmy parametryzować
 
nasz element typem funktora, co doprowadziłoby do tego, że typ elementu
 
nasz element typem funktora, co doprowadziłoby do tego, że typ elementu
 
interfejsu zależałby od konkretnego polecenia, które wywołuje! To
 
interfejsu zależałby od konkretnego polecenia, które wywołuje! To
Linia 225: Linia 223:
  
 
Żeby więc wykorzystać już istniejące funkcje i funktory musimy je
 
Żeby więc wykorzystać już istniejące funkcje i funktory musimy je
opakować w typ który będzie zależał tylko od typów wartości zwracanej
+
opakować w typ, który będzie zależał tylko od typów wartości zwracanej
i argumentów podobnie jak w przypadku zwykłych funkcji. Poniżej
+
i argumentów, podobnie jak w przypadku zwykłych funkcji. Poniżej
przedstawię zarys konstrukcji szablonu który umożliwia robienie tego
+
przedstawię zarys konstrukcji szablonu, który umożliwia robienie tego
 
automatycznie. Będę się opierał na implementacji zamieszczonej w
 
automatycznie. Będę się opierał na implementacji zamieszczonej w
Alexandrescu: <i>"Nowoczesne projektowanie"</i>, ale ograniczę się do funktorów zero, jedno i
+
A. Alexandrescu: <i>"Nowoczesne projektowanie w C++"</i>, ale ograniczę się do funktorów zero-, jedno- i
 
dwuargumentowych.
 
dwuargumentowych.
  
Linia 240: Linia 238:
 
problem: C++ nie dopuszcza zmiennej liczby parametrów szablonu.
 
problem: C++ nie dopuszcza zmiennej liczby parametrów szablonu.
 
Najprostszym nasuwającym się rozwiązaniem jest stworzenie trzech
 
Najprostszym nasuwającym się rozwiązaniem jest stworzenie trzech
różnych szablonów <tt>Function0</tt>, <tt>Function1</tt> i <tt>Function2</tt>
+
różnych szablonów <tt>Function0</tt>, <tt>Function1</tt> i <tt>Function2</tt>,
 
każdy z odpowiednią liczbą parametrów. Takie rozwiązanie jest jednak
 
każdy z odpowiednią liczbą parametrów. Takie rozwiązanie jest jednak
niegodne prawdziwego uogólnionego programisty :) Poszukajmy więc typów
+
niegodne prawdziwego uogólnionego programisty :). Poszukajmy więc typów,
 
które zawierają w sobie inne typy.  Możliwości mamy całkiem sporo,
 
które zawierają w sobie inne typy.  Możliwości mamy całkiem sporo,
 
moglibyśmy np. wykorzystać klasy ze zdefiniowanymi odpowiednimi typami
 
moglibyśmy np. wykorzystać klasy ze zdefiniowanymi odpowiednimi typami
stowarzyszonymi, można wykorzystać typy funkcyjne, lub typy wskaźników
+
stowarzyszonymi, można wykorzystać typy funkcyjne lub typy wskaźników
do funkcji, no i listy typów wprowadzonych na <font color=red>wykładzie&nbsp;{[##|Uzupelnic |]}</font> właśnie do takich celów. Orginalne rozwiązanie w Alexandrescu: <i>"Nowoczesne projektowanie"</i> wykorzystuje listy typów (autor tej pozycji jest ich twórcą), ja użyję typów
+
do funkcji, no i listy typów wprowadzonych w [http://osilek.mimuw.edu.pl/index.php?title=Zaawansowane_CPP/Wyk%C5%82ad_6:_Funkcje_typ%C3%B3w_i_inne_sztuczki#6.3_Listy_typ.C3.B3w wykładzie 6.3] właśnie do takich celów. Orginalne rozwiązanie w A. Alexandrescu <i>"Nowoczesne projektowanie w C++"</i> wykorzystuje listy typów (autor tej pozycji jest ich twórcą), ja użyję typów
wskaźnikow do funkcji. To, że bedę używał wskaźników a nie samych typów funkcji, podyktowane jest względami czysto technicznymi: moja klasa cech <tt>functor_traits</tt> rozpoznaje typy wskaźników do funkcji, a same typy funkcyjne już nie (choć jest to tylko kwestia dodania odpowiednich specjalizacji). Deklaracja szablonu <tt>Function</tt> wyglądała będzie
+
wskaźnikow do funkcji. To, że bedę używał wskaźników, a nie samych typów funkcji, podyktowane jest względami czysto technicznymi: moja klasa cech <tt>functor_traits</tt> rozpoznaje typy wskaźników do funkcji, a same typy funkcyjne już nie (choć jest to tylko kwestia dodania odpowiednich specjalizacji). Deklaracja szablonu <tt>Function</tt> wyglądała będzie
 
więc następująco:
 
więc następująco:
  
Linia 258: Linia 256:
 
  ...
 
  ...
 
  };
 
  };
 +
([[media:Universal.h | Źródło: universal.h]])
  
 
Dziedziczenie z <tt>functor_traits<FT>::f_type</tt> zapewnia nam, że
 
Dziedziczenie z <tt>functor_traits<FT>::f_type</tt> zapewnia nam, że
 
<tt>Function</tt> będzie posiadał odpowiednie typy stowarzyszone zgodnie z
 
<tt>Function</tt> będzie posiadał odpowiednie typy stowarzyszone zgodnie z
konwencją STL
+
konwencją STL.
  
Jako klasa opakowywująca <tt>Function</tt> musi zawierać
+
Jako klasa opakowująca <tt>Function</tt> musi zawierać
opakowywany funktor. Nie może jednak tego robić bezpośrednio bo nie
+
opakowywany funktor. Nie może jednak tego robić bezpośrednio, bo nie
 
znamy typu tego funktora (a raczej nie chcemy go znać). <tt>Function</tt>  
 
znamy typu tego funktora (a raczej nie chcemy go znać). <tt>Function</tt>  
 
będzie więc zawierał wskaźnik do abstrakcyjnej klasy  
 
będzie więc zawierał wskaźnik do abstrakcyjnej klasy  
Linia 271: Linia 270:
 
  std::auto_ptr<AbstractFunctionHolder<FT> > _ptr_fun;
 
  std::auto_ptr<AbstractFunctionHolder<FT> > _ptr_fun;
  
Z tej klasy będą dziedziczyć klasy opakowywujące konkretne typy funktorów:
+
Z tej klasy będą dziedziczyć klasy opakowujące konkretne typy funktorów:
  
 
  template<typename FT,typename F>  
 
  template<typename FT,typename F>  
Linia 282: Linia 281:
 
     F _fun;
 
     F _fun;
 
  };  
 
  };  
 +
([[media:Universal.h | Źródło: universal.h]])
  
 
Konstruktor klasy <tt>FunctionHolder</tt> będzie inicjalizował pole <tt>_fun</tt>:
 
Konstruktor klasy <tt>FunctionHolder</tt> będzie inicjalizował pole <tt>_fun</tt>:
Linia 293: Linia 293:
 
  template<typename F>  Function(F fun):
 
  template<typename F>  Function(F fun):
 
   _fun(new FunctionHolder<FT,F>(fun)){};
 
   _fun(new FunctionHolder<FT,F>(fun)){};
 +
([[media:Universal.h | Źródło: universal.h]])
  
Ten konstruktor zamienia statyczną informacje o typie <tt>F</tt> na
+
Ten konstruktor zamienia statyczną informację o typie <tt>F</tt> na
 
informację dynamiczną zawartą we wskaźniku <tt>_ptr_fun</tt>.  
 
informację dynamiczną zawartą we wskaźniku <tt>_ptr_fun</tt>.  
informację  odzyskujemy za pomocą polimorfizmu. W celu uzyskania
+
informację  odzyskujemy za pomocą polimorfizmu. W celu uzyskania
 
polimorficznego zachowania przy kopiowaniu i przypisywaniu obiektów
 
polimorficznego zachowania przy kopiowaniu i przypisywaniu obiektów
 
<tt>Function</tt> skorzystamy z klonowania:
 
<tt>Function</tt> skorzystamy z klonowania:
Linia 304: Linia 305:
 
   _fun.reset(f._fun->Clone());
 
   _fun.reset(f._fun->Clone());
 
  }
 
  }
 +
([[media:Universal.h | Źródło: universal.h]])
  
 
Wymaga to dodania do klasy <tt>AbstractFunctionHolder</tt> wirtualnych funkcji:
 
Wymaga to dodania do klasy <tt>AbstractFunctionHolder</tt> wirtualnych funkcji:
Linia 309: Linia 311:
 
  virtual  AbstractFunctionHolder* Clone()<nowiki>=</nowiki>0;
 
  virtual  AbstractFunctionHolder* Clone()<nowiki>=</nowiki>0;
 
  virtual &nbsp;AbstractFunctionHolder() {};   
 
  virtual &nbsp;AbstractFunctionHolder() {};   
 +
([[media:Universal.h | Źródło: universal.h]])
  
 
Klasa <tt>FunctionHolder</tt> implementuje funkcję <tt>Clone()</tt> następująco:
 
Klasa <tt>FunctionHolder</tt> implementuje funkcję <tt>Clone()</tt> następująco:
  
 
  FunctionHolder*Clone() {return new FunctionHolder(*this);}
 
  FunctionHolder*Clone() {return new FunctionHolder(*this);}
 +
([[media:Universal.h | Źródło: universal.h]])
  
 
Proszę zwrócić uwage na typ argumentu konstruktorów. Zgodnie z tym co
 
Proszę zwrócić uwage na typ argumentu konstruktorów. Zgodnie z tym co
napisałem w <font color=red>podrozdziale&nbsp;{[##|Uzupelnic |]}</font> użyłem wywołania przez wartość <tt>(F fun)</tt>, inaczej nie można by inicjalizować pola <tt>F _fun</tt> w przypadku gdyby <tt>F</tt> był typem funkcyjnym. Należy nadmienić że implementacja opisana w Alexandrescu: <i>"Nowocesne projektowanie"</i> zawiera właśnie taki bład, który nie występuje w kodzie biblioteki <tt>loki</tt> dostępnym w Internecie.  
+
napisałem w [http://osilek.mimuw.edu.pl/index.php?title=Zaawansowane_CPP/Wyk%C5%82ad_11:_Funktory#Funkcje.2C_wska.C5.BAniki_i_referencje__do_funkcji wykładzie 11.2], użyłem wywołania przez wartość <tt>(F fun)</tt>, inaczej nie możnaby inicjalizować pola <tt>F _fun</tt> w przypadku gdyby <tt>F</tt> był typem funkcyjnym. Należy nadmienić, że implementacja opisana w A. Alexandrescu: <i>"Nowoczesne projektowanie w C++"</i> zawiera właśnie taki błąd, który nie występuje w kodzie biblioteki <tt>loki</tt> dostępnym w Internecie.
  
 
===Wywoływanie: operator()===
 
===Wywoływanie: operator()===
  
W ten sposób mamy już wszystko poza najważniejszym: operatorem który
+
W ten sposób mamy już wszystko poza najważniejszym: operatorem <tt>operator()(...)</tt>, który czyni funktor funktorem.
czyni funktor funktorem. Pozostała nam jeszcze implementacja operatora
 
<tt>operator()(...)</tt>.  
 
  
 
Zacznijmy od operatora nawiasów w klasie <tt>Function</tt>. Problem polega
 
Zacznijmy od operatora nawiasów w klasie <tt>Function</tt>. Problem polega
na tym, że nie ma możliwości zdefiniowanie operatora odpowiadającego
+
na tym, że nie ma możliwości zdefiniowania operatora odpowiadającego
 
przekazanemu typowi funkcyjnemu (można by ewentulanie go
 
przekazanemu typowi funkcyjnemu (można by ewentulanie go
 
zadeklarować), bo wymagałoby to definicji dopuszczającej zmienną
 
zadeklarować), bo wymagałoby to definicji dopuszczającej zmienną
 
liczbę argumengtów (tak, tak, wiem w C jest taka możliwość,
 
liczbę argumengtów (tak, tak, wiem w C jest taka możliwość,
ale lepiej z niej nie korzystać, zreszta nie ma potrzeby). Możliwe
+
ale lepiej z niej nie korzystać, zresztą nie ma potrzeby). Możliwe
 
rozwiązanie to specjalizacja szablonu dla funktorów bez argumentów, z
 
rozwiązanie to specjalizacja szablonu dla funktorów bez argumentów, z
 
jednym lub z dwoma argumentami i w każdej specjalizacji
 
jednym lub z dwoma argumentami i w każdej specjalizacji
Linia 334: Linia 336:
 
argumentów. Okazuje się, że nie ma takiej potrzeby, możemy zdefiniować
 
argumentów. Okazuje się, że nie ma takiej potrzeby, możemy zdefiniować
 
wszystkie wersje operatora wywołania funkcji w tej samej klasie i
 
wszystkie wersje operatora wywołania funkcji w tej samej klasie i
polegać na mechaniźmie opóżnionej konkretyzacji: dopóki nie wywołamy
+
polegać na mechaniźmie opóźnionej konkretyzacji: dopóki nie wywołamy
 
operatora ze złą ilością argumentów, to nie będzie on konkretyzowany.
 
operatora ze złą ilością argumentów, to nie będzie on konkretyzowany.
Dodajemy więc do klasy <tt>Function</tt> następujace linijki:
+
Dodajemy więc do klasy <tt>Function</tt> następujące linijki:
  
 
  res_type operator()() {return (*_ptr_fun)();};
 
  res_type operator()() {return (*_ptr_fun)();};
Linia 343: Linia 345:
 
   return (*_ptr_fun)(x,y);
 
   return (*_ptr_fun)(x,y);
 
  };
 
  };
 +
([[media:Universal.h | Źródło: universal.h]])
  
Wskaźnik <tt>_ptr_fun</tt> jest typu <tt>AbstractFunctionHolder*</tt> musimy  
+
Wskaźnik <tt>_ptr_fun</tt> jest typu <tt>AbstractFunctionHolder*</tt>, musimy  
 
więc zaimplementować w tej klasie operator nawiasów.
 
więc zaimplementować w tej klasie operator nawiasów.
 
Klasa <tt>AbstractFunctionHolder*</tt> nie posiada wystarczającej w tym celu  
 
Klasa <tt>AbstractFunctionHolder*</tt> nie posiada wystarczającej w tym celu  
informacji więc deklarujemy te funkcje  jako czyste funkcje wirtualne,
+
informacji, więc deklarujemy te funkcje  jako czyste funkcje wirtualne,
 
które zostaną zdefiniowane dopiero w klasie pochodnej <tt>FunctionHolder</tt>.
 
które zostaną zdefiniowane dopiero w klasie pochodnej <tt>FunctionHolder</tt>.
Niestety deklaracja trzech różnyc wariantów operatora  
+
Niestety deklaracja trzech różnych wariantów operatora  
  
 
   virtual res_type operator()() <nowiki>=</nowiki> 0;
 
   virtual res_type operator()() <nowiki>=</nowiki> 0;
Linia 361: Linia 364:
 
   res_type operator()(arg1_type x,arg2_type y) {return _fun(x,y);};
 
   res_type operator()(arg1_type x,arg2_type y) {return _fun(x,y);};
  
spowodują błedy w kompilacji już przy konstrukcji klasy. Dzieje się
+
spowodują błędy w kompilacji już przy konstrukcji klasy. Dzieje się
 
tak dlatego, że funkcje wirtualne mogą niepodlegać konkretyzacji
 
tak dlatego, że funkcje wirtualne mogą niepodlegać konkretyzacji
opóżnionej i w implmentacji kompilatora <tt>g++</tt> nie podlegają. Tzn.
+
opóźnionej i w implementacji kompilatora <tt>g++</tt> jej nie podlegają. Tzn.
 
kiedy kompilator dokonuje konkretyzacji klasy
 
kiedy kompilator dokonuje konkretyzacji klasy
<tt>FunctionHolder<FT,F></tt>, wymaganej przez konstruktor inicjalizujacy
+
<tt>FunctionHolder<FT,F></tt>, wymaganej przez konstruktor inicjalizujący
 
klasy <tt>Function</tt>, konkretyzuje wszystkie funkcje wirtualne, a tylko
 
klasy <tt>Function</tt>, konkretyzuje wszystkie funkcje wirtualne, a tylko
 
jedna wersja operatora wywołania jest prawidłowa. W tym przypadku nie
 
jedna wersja operatora wywołania jest prawidłowa. W tym przypadku nie
 
unikniemy więc konieczności specjalizowania szablonów dla każdej
 
unikniemy więc konieczności specjalizowania szablonów dla każdej
ilości agumentów. Na szczeście wystarczy wyspecjalizować tylko klasę  
+
ilości agumentów. Na szczęście wystarczy wyspecjalizować tylko klasę  
 
<tt>AbstractFunctionHolder</tt>:
 
<tt>AbstractFunctionHolder</tt>:
  
Linia 378: Linia 381:
 
   virtual R operator()(A1 x, A2 y) <nowiki>=</nowiki> 0;
 
   virtual R operator()(A1 x, A2 y) <nowiki>=</nowiki> 0;
 
   virtual  AbstractFunctionHolder* Clone()<nowiki>=</nowiki>0;
 
   virtual  AbstractFunctionHolder* Clone()<nowiki>=</nowiki>0;
   virtual &nbsp;AbstractFunctionHolder() {};<br>
+
   virtual &nbsp;AbstractFunctionHolder() {};
 
  } ;
 
  } ;
<i>i tak samo dla funkcji z jednym i bez argumentów</i>
+
([[media:Universal.h | Źródło: universal.h]])
 +
 
 +
i tak samo dla funkcji z jednym i bez argumentów.
  
 
Szablon <tt>FunctionHolder</tt> może dalej definiować wszystkie warianty
 
Szablon <tt>FunctionHolder</tt> może dalej definiować wszystkie warianty
Linia 389: Linia 394:
 
  Function<double(*)(double)> Func1;
 
  Function<double(*)(double)> Func1;
  
Konstrutor klasy <tt>Funcion<double (*)(double)></tt> wywoła konstruktor  
+
Konstrutor klasy <tt>Function<double (*)(double)></tt> wywoła konstruktor  
 
klasy <tt>FunctionHandler<double (*)(double),double (*)(double)></tt>,
 
klasy <tt>FunctionHandler<double (*)(double),double (*)(double)></tt>,
 
co pociągnie za sobą konieczną konkretyzację tego szablonu.  
 
co pociągnie za sobą konieczną konkretyzację tego szablonu.  
Linia 400: Linia 405:
 
  virtual double operator(double x) <nowiki>=</nowiki> 0
 
  virtual double operator(double x) <nowiki>=</nowiki> 0
  
Ale to oznacza że z trzech wariantów operatora wywołania
+
Ale to oznacza, że z trzech wariantów operatora wywołania
 
zdefiniowanych w <tt>FunctionHandler<double (*)(double),double (*)(double)></tt> tylko jeden jest wirtualny: ten dobry! I właśnie ten zostanie skonkretyzowany, pozostałe dwa są zwykłymi funkcjami składowymi i nie zostaną utworzone jesli ich nie użyjemy. Jeśli jednak spróbujemy ich użyć dostaniemy błąd kompilacji, co jest w tej sytuacji zachowaniem pożądanym.
 
zdefiniowanych w <tt>FunctionHandler<double (*)(double),double (*)(double)></tt> tylko jeden jest wirtualny: ten dobry! I właśnie ten zostanie skonkretyzowany, pozostałe dwa są zwykłymi funkcjami składowymi i nie zostaną utworzone jesli ich nie użyjemy. Jeśli jednak spróbujemy ich użyć dostaniemy błąd kompilacji, co jest w tej sytuacji zachowaniem pożądanym.
  
Używając szablomu <tt>Function</tt> możemy teraz napisać:
+
Używając szablonu <tt>Function</tt> możemy teraz napisać:
  
 
  #include"universal.h"
 
  #include"universal.h"
Linia 415: Linia 420:
 
  Function<double (*)(double)> my_exp(exp);<br>
 
  Function<double (*)(double)> my_exp(exp);<br>
 
  std::cout<<my_exp(1.0)<<"";
 
  std::cout<<my_exp(1.0)<<"";
 +
([[media:Test_universal.cpp | Źródło: test_universal.cpp]])
  
 
===boost::functions===
 
===boost::functions===
  
Podobną funkcjonalność dostarcza biblioteka <tt>functions</tt> z repozytorium <tt>boost</tt>.  Zresztą z tamtąd wziąłem pomysł parametryzowania funktorów typem funkcyjnym. Kod używający tej biblioteki będzie wyglądał bardzo podbnie:
+
Podobną funkcjonalność dostarcza biblioteka <tt>functions</tt> z repozytorium <tt>boost</tt>.  Zresztą stamtąd wziąłem pomysł parametryzowania funktorów typem funkcyjnym. Kod używający tej biblioteki będzie wyglądał bardzo podobnie:
  
 
  #include<boost/function.hpp>
 
  #include<boost/function.hpp>
Linia 429: Linia 435:
 
                             f);<br>
 
                             f);<br>
 
  std::cout<<fc(1.0,1.0)<<"";
 
  std::cout<<fc(1.0,1.0)<<"";
 +
([[media:Boost_function.cpp | Źródło: boost_function.cpp]])

Aktualna wersja na dzień 11:51, 11 gru 2007

Wstęp

W poprzednim wykładzie omawiałem pojęcie obiektu funkcyjnego, jako uogólnienia wskaźników do funkcji. I choć funktory można wywoływać bezpośrednio tak jak funkcje, to dużo częściej używa się ich jako parametrów przekazywanych do innych funkcji, w celu dostarczenia tej funkcji informacji koniecznych do wykonania swojego zadania. W tej kategorii zastosowań mieści się większość bibliotek, w tym STL, gdzie funktory służą jako argumenty do uogólnionych algorytmów. Przykłady takich zastosowań były już podawane w poprzednich wykładach, a na tym wykładzie omówię je trochę bardziej szczegółowo.

Inny popularny schemat użycia wskaźników funkcji (a więc i funktorów) to rozdzielenie miejsca i czasu definicji funkcji od miejsca i czasu jej wykonania. Wygląda to zwykle następująco: Klient definiuje funkcje i przekazuje ich wskaźniki do aplikacji, aplikacja wywołuje te funkcje w wybranym przez siebie czasie. Klient nie ma pojęcia kiedy zostaną wywołane przekazane przez niego funkcje, a aplikacja nie wie jakie one mają działanie. Taka technika funkcji zwrotnych (callbacks) jest podstawą implementacji wielu szkieletów graficznych interfejsów użytkownika i w E. Gamma, R. Helm, R. Johnson, J. Vlissides "Wzorce projektowe. Elementy oprogramowania obiektowego wielokrotnego użytku" wymieniona jest jako wzorzec polecenie. Aby używać funktorów definiowanych na poprzednim wykładzie, we wzorcu polecenie trzeba będzie je trochę dostosować. Zostanie to opisane w drugiej części tego wykładu.

Algorytmy uogólnione i programowanie funkcyjne

Algorytmy stanowią, jak już to opisałem w wykładzie 2, jedną z części biblioteki STL, większośc z tych algorytmów posiada wersje przyjmujące funktor jako jeden z argumentów. Nie jest moim celem przedstawianie tutaj wszystkich algorytmów, jest ich zresztą blisko 100, choć gorąco zachęcam Państwa do zapoznania się z nimi. W tym celu polecam książke N.M. Josuttis "C++ Biblioteka Standardowa. Podręcznik programisty" i stronę http://www.sgi.com/tech/stl/. Znakomita jest też pozycja S. Meyers "STL w praktyce. 50 sposobów efektywnego wykorzystania", jak zresztą wszystkie książki tego autora.

W tym wykładzie chciałbym tylko zwrócić uwagę, że biblioteka algorytmów wprowadza do C++ elementy programowania funkcyjnego. Programowanie funkcyjne polega, z grubsza rzecz biorąc, na zastępowaniu pętli poleceniami, które potrafią wywołać daną funkcję na każdym elemencie danej kolekcji. Taki styl programowania jest często spotykany w językach interpretowanych, np. używa go pakiet Mathematica, podobnie pakiet do obliczeń numerycznych w Perlu: Perl Data Language i wiele innych. Biblioteka STL oferuje tylko namiastkę tego stylu, ale właśnie ją chciałbym przedstawić w tej części wykładu.

Podstawą programowania funkcyjnego są funkcje, które wywołują inne funkcje na każdym obiekcie z kolekcji. STL oferuje kilka takich algorytmów, podstawowym z nich jest for_each.

template <class InputIterator, class UnaryFunction>
UnaryFunction 
for_each(InputIterator first,InputIterator last, 
         UnaryFunction op);

Działanie tego algorytmu polega na wywołaniu podanego funktora op na każdym elemencie zakresu [first,last). Funktor może modyfikować wywoływany obiekt i może powodowac inne skutki uboczne. Jego kopia jest zwracana po wykonaniu wszystkich operacji. Wartość zwracana przez funktor op jest ignorowana. Algorytm zwraca kopię funktora op.

Podobnym algorytmem jest transform. W swojej pierwszej wersji

template <class InputIterator, class OutputIterator, class UnaryFunction>
OutputIterator transform(InputIterator first, InputIterator last,
                         OutputIterator result, UnaryFunction op);

działa podobnie jak for_each, z tą różnicą, że wyniki wywołania operacji op na wartościach zakresu [firts,last) są zapisywane poprzez iterator result. Ważną cechą tego algorytmu jest to, że może on operować na dwu wejściowych zakresach. Jego druga wersja

template <class InputIterator1, class InputIterator2, 
          class OutputIterator,class BinaryFunction>
OutputIterator 
transform(InputIterator1 first1, InputIterator1 last1,
          InputIterator2 first2, OutputIterator result,
          BinaryFunction op);

wywołuje operację binarną op na parach wartości wziętych po jednej z każdego zakresu wejściowego. Wynik zapisywany jest poprzez iterator wyjściowy result.

Warto też zwrócić uwagę na algorytmy numeryczne, które pomimo ich nazwy mogą spokojnie zostać użyte do innych ogólnych zastosowań. Są to:

template <class InputIterator, class T, class BinaryFunction>
T accumulate(InputIterator first, InputIterator last, T init,
             BinaryFunction op);

który oblicza uogólnioną sumę podanego zakresu

iloczyn skalarny inner_product:

template <class InputIterator1, class InputIterator2, class T,
          class BinaryFunction1, class BinaryFunction2>
T inner_product(InputIterator1 first1, InputIterator1 last1,
                InputIterator2 first2, T init, BinaryFunction1 op1,
                BinaryFunction2 op2);

który oblicza uogólniony iloczyn skalarny

oraz sumy i różnice częściowe:

template <class InputIterator, class OutputIterator, class BinaryOperation>
OutputIterator 
partial_sum(InputIterator first,   InputIterator last,
            OutputIterator result, BinaryOperation binary_op);
template <class InputIterator, class OutputIterator, class BinaryFunction> OutputIterator adjacent_difference(InputIterator first, InputIterator last, OutputIterator result, BinaryFunction op);

zwracające poprzez iterator result odpowiednio:

i


Zwłaszcza algorytm adjacent_difference jest ciekawy, umożliwia bowiem zastosowanie dwuargumentowej operacji do kolejnych par elementów:

int print(int i,int j) {
  cout<<"("<<i<<":"<<j<<")";
  return 0;
}
main() {
  list<int> li;
  list<int> res;
  generate_n(back_insert_iterator<list<int> >(li),10,SequenceGen<int>(1,2));
adjacent_difference(li.begin(),li.end(),back_insert_iterator<list<int> >(res),print);

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

Ten przykładzik ilustruje niedogodność posługiwania się algorytmami przyjmującymi zakres wyjściowy, takimi jak adjacent_difference czy transform, do prostego działania funkcją, która nie zwraca żadnych wartości. Do tego przeznaczony jest algorytm for_each. Niestety, ten algorytm nie pozwala bezpośrednio operować na parach kolejnych elementów, tak jak adjacent_difference. To by jeszcze można zasymulować używając odpowiedniego funktora, ale for_each nie potrafi operować na parach elementów pochodzących z dwu zakresów, tak jak potrafi to transpose.

Jest kilka możliwości rozwiązania tego problemu. Możemy np. napisać własne algorytmy (zob. zadania). Możemy też dalej korzystać np. z adjacent_difference ale napisać narzędzia pomagające adoptować takie algorytmy do naszych celów. Jak by to mogło wyglądać?

Patrzac na nasz przykład i deklarację adjacent_difference widzimy, że są dwa problemy: po pierwsze wartość zwracana z funkcji op musi być tego samego typu jak typ elementów w zakresie wejściowym, po drugie musimy jakoś "zjeść" te zwracane wartości. Potrzebny więc będzie funktor opakowujący dowolną funkcję i zwracający wartość zadanego typu, oraz iterator pełniący rolę /dev/null, czyli "czarnej dziury" połykającej wszystko co się do niej zapisze. Mając takie obiekty możemy powyższy kod zapisać następująco:

void print(int i,int j) {
  cout<<"("<<i<<":"<<j<<")";
}
main() {
  list<int> li;
generate_n(back_insert_iterator<list<int> >(li),10,SequenceGen<int>(1,2));
adjacent_difference(li.begin(),li.end(),dev_null<char>(),dummy<char>(print));

Obiekt klasy dev_null<T> to iterator typu output_iterator, którego value_type jest równy T. Iterator ten ignoruje wszelkie operacje na nim wykonywane, w tym przypisanie do niego. Funckja dummy<T>(F f, T val = T()) zwraca funktor, który wywołuje funkcję f, a następnie zwraca wartośc val typu T. Implementacje tych szablonów pozostawiam jako ćwiczenie (zob. zadania).

Pomysły można mnożyć. Jako ostatni zaprezentuję iterator, który nie wstawia nic do żądanego kontenera, ale wywołuje na przypisywanym do niego obiekcie jakąś zadaną funkcję:

void p(double x) {
  std::cout<<"printing  "<<x<<"";
};
double frac(int i) { return i/10.0; } list<int> li; generate_n(back_insert_iterator<list<int> >(li),10,SequenceGen<int>(1,2));
std::transform(li.begin(),li.end(),function_iterator<double>(p),frac);

Taki iterator łatwo zaimplementować przy pomocy klas proxy (zob. zadania).

Wzorzec Polecenie

Wzorzec polecenie najlepiej omówić na przykładzie. Jak już wspomniałem, typowe zastosowanie to graficzny interfejs użytkownika (GUI). Taki interfejs musi reagować na różne zdarzenia: kliknięcie myszą, naciśnięcie przycisku, wybranie polecenia z menu. Ewidentnie twórca biblioteki GUI nie może wiedziec jakie działanie ma pociągnąć dane zdarzenie. Nawet jednak gdybyśmy sami pisali cały kod, to "zaszycie" polecenia na stałe w kodzie danego elementu interfejsu jest bardzo złą praktyką programistyczną. Dlatego używa się w tym celu funkcji zwrotnych. I tak w jakiejś hipotetycznej klasie

class Window {

znajdziemy na pewno funkcję w rodzaju

on_mouse_click(void (*)(int,int))

służącą do przekazania wskaźnika do funkcji, która zostanie wywołana po naciśnięciu myszką na oknie. Podobnie dla innych komponentów:

class Button {
void (*_f)() ; /*wskaźnik do funkcji */
void when_pressed(void (*f)()) {_f=f;};
...
}

Ponieważ typ funkcji określony jest poprzez typ jej parametrów i typ wartości zwracanej to możemy w ten sposób ustawić dowolną fukcję o odpowiedniej sygnaturze. Niestety, jeżeli chcemy wykorzystać dobrodziejstwa jakie daje nam zastosowanie obiektów funkcyjnych zamiast funkcji, musimy je dziedziczyć ze wspólnej klasy bazowej, ponieważ jedną z podstawowych cech funktorów jest to, że posiadają swój typ. Żeby więc móc przekazywać różne funktory za pomocą tej samej sygnatury, musimy je rzutować w górę na wspólny typ. To jest cała esencja wzorca polecenie (zob. E. Gamma, R. Helm, R. Johnson, J. Vlissides "Wzorce projektowe. Elementy oprogramowania obiektowego wielokrotnego użytku").

Oznacza to jednak, że nie możemy skorzystać z całej technologii wyprowadzonej na poprzednim wykładzie. Szablony też nam nie pomogą, ponieważ wenątrz elementów GUI musimy jakoś przechować funktor zwrotny. Aby przechowywać różne funktory musielibyśmy parametryzować nasz element typem funktora, co doprowadziłoby do tego, że typ elementu interfejsu zależałby od konkretnego polecenia, które wywołuje! To uniemożliwiłoby w praktyce jakiekolwiek funkcjonowanie szkieletu.

Żeby więc wykorzystać już istniejące funkcje i funktory musimy je opakować w typ, który będzie zależał tylko od typów wartości zwracanej i argumentów, podobnie jak w przypadku zwykłych funkcji. Poniżej przedstawię zarys konstrukcji szablonu, który umożliwia robienie tego automatycznie. Będę się opierał na implementacji zamieszczonej w A. Alexandrescu: "Nowoczesne projektowanie w C++", ale ograniczę się do funktorów zero-, jedno- i dwuargumentowych.

Uniwersalny funktor

Uniwersalny funktor (nazwiemy go Function) ma z założenia odpowiadać typowi funkcyjnemu, czyli zależeć jedynie od typu wartości zwracanej i typów argumentów. Musi więc być zdefiniowany jako szablon, paremetryzowany właśnie tymi typami. Tu napotykamy pierwszy problem: C++ nie dopuszcza zmiennej liczby parametrów szablonu. Najprostszym nasuwającym się rozwiązaniem jest stworzenie trzech różnych szablonów Function0, Function1 i Function2, każdy z odpowiednią liczbą parametrów. Takie rozwiązanie jest jednak niegodne prawdziwego uogólnionego programisty :). Poszukajmy więc typów, które zawierają w sobie inne typy. Możliwości mamy całkiem sporo, moglibyśmy np. wykorzystać klasy ze zdefiniowanymi odpowiednimi typami stowarzyszonymi, można wykorzystać typy funkcyjne lub typy wskaźników do funkcji, no i listy typów wprowadzonych w wykładzie 6.3 właśnie do takich celów. Orginalne rozwiązanie w A. Alexandrescu "Nowoczesne projektowanie w C++" wykorzystuje listy typów (autor tej pozycji jest ich twórcą), ja użyję typów wskaźnikow do funkcji. To, że bedę używał wskaźników, a nie samych typów funkcji, podyktowane jest względami czysto technicznymi: moja klasa cech functor_traits rozpoznaje typy wskaźników do funkcji, a same typy funkcyjne już nie (choć jest to tylko kwestia dodania odpowiednich specjalizacji). Deklaracja szablonu Function wyglądała będzie więc następująco:

template<typename FT> class Function:
public  functor_traits<FT>::f_type {
typedef typename functor_traits<FT>::result_type res_type; typedef typename functor_traits<FT>::arg1_type arg1_type; typedef typename functor_traits<FT>::arg2_type arg2_type; public: ... };

( Źródło: universal.h)

Dziedziczenie z functor_traits<FT>::f_type zapewnia nam, że Function będzie posiadał odpowiednie typy stowarzyszone zgodnie z konwencją STL.

Jako klasa opakowująca Function musi zawierać opakowywany funktor. Nie może jednak tego robić bezpośrednio, bo nie znamy typu tego funktora (a raczej nie chcemy go znać). Function będzie więc zawierał wskaźnik do abstrakcyjnej klasy AbstractFunctionHolder<FT> parametryzowanej tym samym typem.

std::auto_ptr<AbstractFunctionHolder<FT> > _ptr_fun;

Z tej klasy będą dziedziczyć klasy opakowujące konkretne typy funktorów:

template<typename FT,typename F> 
class FunctionHolder: public AbstractFunctionHolder<FT> {
typedef typename functor_traits<FT>::result_type res_type; typedef typename functor_traits<FT>::arg1_type arg1_type; typedef typename functor_traits<FT>::arg2_type arg2_type; ...
private: F _fun; };

( Źródło: universal.h)

Konstruktor klasy FunctionHolder będzie inicjalizował pole _fun:

FunctionHolder(F fun):_fun(fun) {}; 

Korzystać z niego będzie konstruktor klasy Function, który musi być szablonem aby pozwolić na inicjalizowanie Function dowolnym typem funktora:

template<typename F>  Function(F fun):
  _fun(new FunctionHolder<FT,F>(fun)){};

( Źródło: universal.h)

Ten konstruktor zamienia statyczną informację o typie F na informację dynamiczną zawartą we wskaźniku _ptr_fun. Tę informację odzyskujemy za pomocą polimorfizmu. W celu uzyskania polimorficznego zachowania przy kopiowaniu i przypisywaniu obiektów Function skorzystamy z klonowania:

Function(const Function& f):_fun(f._fun->Clone()) {};
Function &operator=(const Function &f) {
  _fun.reset(f._fun->Clone());
}

( Źródło: universal.h)

Wymaga to dodania do klasy AbstractFunctionHolder wirtualnych funkcji:

virtual  AbstractFunctionHolder* Clone()=0;
virtual  AbstractFunctionHolder() {};  

( Źródło: universal.h)

Klasa FunctionHolder implementuje funkcję Clone() następująco:

FunctionHolder*Clone() {return new FunctionHolder(*this);}

( Źródło: universal.h)

Proszę zwrócić uwage na typ argumentu konstruktorów. Zgodnie z tym co napisałem w wykładzie 11.2, użyłem wywołania przez wartość (F fun), inaczej nie możnaby inicjalizować pola F _fun w przypadku gdyby F był typem funkcyjnym. Należy nadmienić, że implementacja opisana w A. Alexandrescu: "Nowoczesne projektowanie w C++" zawiera właśnie taki błąd, który nie występuje w kodzie biblioteki loki dostępnym w Internecie.

Wywoływanie: operator()

W ten sposób mamy już wszystko poza najważniejszym: operatorem operator()(...), który czyni funktor funktorem.

Zacznijmy od operatora nawiasów w klasie Function. Problem polega na tym, że nie ma możliwości zdefiniowania operatora odpowiadającego przekazanemu typowi funkcyjnemu (można by ewentulanie go zadeklarować), bo wymagałoby to definicji dopuszczającej zmienną liczbę argumengtów (tak, tak, wiem w C jest taka możliwość, ale lepiej z niej nie korzystać, zresztą nie ma potrzeby). Możliwe rozwiązanie to specjalizacja szablonu dla funktorów bez argumentów, z jednym lub z dwoma argumentami i w każdej specjalizacji zdefiniowanie operatora operator()(...) z odpowiednią liczbą argumentów. Okazuje się, że nie ma takiej potrzeby, możemy zdefiniować wszystkie wersje operatora wywołania funkcji w tej samej klasie i polegać na mechaniźmie opóźnionej konkretyzacji: dopóki nie wywołamy operatora ze złą ilością argumentów, to nie będzie on konkretyzowany. Dodajemy więc do klasy Function następujące linijki:

res_type operator()() {return (*_ptr_fun)();};
res_type operator()(arg1_type x) {return (*_ptr_fun)(x);};
res_type operator()(arg1_type x,arg2_type y) {
  return (*_ptr_fun)(x,y);
};

( Źródło: universal.h)

Wskaźnik _ptr_fun jest typu AbstractFunctionHolder*, musimy więc zaimplementować w tej klasie operator nawiasów. Klasa AbstractFunctionHolder* nie posiada wystarczającej w tym celu informacji, więc deklarujemy te funkcje jako czyste funkcje wirtualne, które zostaną zdefiniowane dopiero w klasie pochodnej FunctionHolder. Niestety deklaracja trzech różnych wariantów operatora

 virtual res_type operator()() = 0;
 virtual res_type operator()(arg1_type x) = 0;
 virtual res_type operator()(arg1_type x,arg2_type y)=0;

i odpowiadające im definicje w klasie FunctionHolder

 res_type operator()() {return _fun();};
 res_type operator()(arg1_type x) {return _fun(x);};
 res_type operator()(arg1_type x,arg2_type y) {return _fun(x,y);};

spowodują błędy w kompilacji już przy konstrukcji klasy. Dzieje się tak dlatego, że funkcje wirtualne mogą niepodlegać konkretyzacji opóźnionej i w implementacji kompilatora g++ jej nie podlegają. Tzn. kiedy kompilator dokonuje konkretyzacji klasy FunctionHolder<FT,F>, wymaganej przez konstruktor inicjalizujący klasy Function, konkretyzuje wszystkie funkcje wirtualne, a tylko jedna wersja operatora wywołania jest prawidłowa. W tym przypadku nie unikniemy więc konieczności specjalizowania szablonów dla każdej ilości agumentów. Na szczęście wystarczy wyspecjalizować tylko klasę AbstractFunctionHolder:

template<typename FT> class AbstractFunctionHolder ;
template<typename R,typename A1,typename A2> class AbstractFunctionHolder<R (*)(A1,A2)> { public: virtual R operator()(A1 x, A2 y) = 0; virtual AbstractFunctionHolder* Clone()=0; virtual  AbstractFunctionHolder() {}; } ;

( Źródło: universal.h)

i tak samo dla funkcji z jednym i bez argumentów.

Szablon FunctionHolder może dalej definiować wszystkie warianty operatora wywołania. Prześledźmy teraz konkretyzację tych szablonów na przykładzie:

double f(double x) {return x;}
Function<double(*)(double)> Func1;

Konstrutor klasy Function<double (*)(double)> wywoła konstruktor klasy FunctionHandler<double (*)(double),double (*)(double)>, co pociągnie za sobą konieczną konkretyzację tego szablonu. Ten szablon dziedziczy z

AbstractFunctionHandler<double (*)(double)>

która ma zdefiniowany tylko jeden operator

virtual double operator(double x) = 0

Ale to oznacza, że z trzech wariantów operatora wywołania zdefiniowanych w FunctionHandler<double (*)(double),double (*)(double)> tylko jeden jest wirtualny: ten dobry! I właśnie ten zostanie skonkretyzowany, pozostałe dwa są zwykłymi funkcjami składowymi i nie zostaną utworzone jesli ich nie użyjemy. Jeśli jednak spróbujemy ich użyć dostaniemy błąd kompilacji, co jest w tej sytuacji zachowaniem pożądanym.

Używając szablonu Function możemy teraz napisać:

#include"universal.h"
  Cov f(1.0,2.0,2.0);
Function<double (*)(double,double)> fc; fc=compose_f_gxy( __gnu_cxx::compose1(std::ptr_fun(exp), std::negate<double>()), f);
std::cout<<fc(1.0,1.0)<<"";
Function<double (*)(double)> my_exp(exp);
std::cout<<my_exp(1.0)<<"";

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

boost::functions

Podobną funkcjonalność dostarcza biblioteka functions z repozytorium boost. Zresztą stamtąd wziąłem pomysł parametryzowania funktorów typem funkcyjnym. Kod używający tej biblioteki będzie wyglądał bardzo podobnie:

#include<boost/function.hpp>
using namespace boost;
Cov f(1.0,2.0,2.0);
boost::function<double (double,double)> fc; fc=compose_f_gxy( __gnu_cxx::compose1(std::ptr_fun(exp), std::negate<double>()), f);
std::cout<<fc(1.0,1.0)<<"";

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