C++ bez cholesterolu: Programowanie generyczne w C++: Wzorce 3.2 Wzorce Wiadomości wstępne Wzorce są jednym z najsilniejszych, choć - "niestety", jak niektórzy powiedzą - statycznych narzędzi. Zgodnie jednak ze swoim przeznaczeniem, powinny służyć do tego, aby maksymalnie skrócić konieczność pisania i powtarzania tych samych sekwencji. Wcześniej podobną rolę spełniały makrogeneratory (jak np. słynny m4, również podobnie jak preprocesor języka C dostępny na unixach przez program `cpp'), jednak porównanie wzorców do makrogeneratorów jest absolutnym nieporozumieniem. Makrogeneratory bowiem działają w zupełnym oderwaniu od języka, na rzecz którego generują źródła, natomiast wzorce ściśle się trzymają konwencji języka, czego konsekwencją jest to, że mamy do dyspozycji dwa podstawowe rodzaje wzorców: wzorzec funkcji i wzorzec struktury. Struktura wzorców Definicję wzorca rozpoczyna się zawsze od sekwencji: template < parametry-wzorca > definicja-wzorca Tutaj parametry wzorca są wyjątkowo w nawiasach ostrych. Parametry te przypominają właściwie argumenty funkcji, z tym, że na liście parametrów może wystąpić parametr typu, który zazwyczaj nazywa się `class'). Oczywiście parametr wzorca może być również np. typu size_t, ale class jest to niewątpliwie wzorców najmocniejsza strona. Jeśli chodzi o kwestie składniowe to zaznaczam od razu: jeśli jednym z parametrów wzorca jest jakiś inny konkretyzowany wzorzec, to NIGDY nie wolno pisać: wz1<costam,wz2<int>> Należy zawsze nawiasy ostre pisać rozdzielnie: > >. Wielu napewno zarzuci, że bardzo niedobrze, że typ, podany jako parametr typu class, jest to na liście argumentów po prostu typ, nie pozwalający określać, że ma to być typ mający taką a nie inną klasę podstawową itd.. Tak naprawdę nic takiego nie jest potrzebne. Jeśli poda się tam taki typ, który nie będzie spełniał wymogów jego użycia w danym wzorcu, to po prostu kompilator taki kod odrzuci (mało tego - jeśli z danej SPECJALIZACJI wzorca nie używa się jakiejś metody, której próba użycia byłaby składniowo niepoprawna, bo typ wzorca nie spełnia jakichś jej wymogów, to też wszystko działa!). Koncepcja tworzenia konkretów ze wzorców zupełnie nie przypomina tworzenia klas. Aby stworzyć wzorzec, dla parametru będącego typem należy stworzyć "koncept", który jest tylko i wyłącznie zbiorem wymagań stawianych konkretnemu (konkretyzującemu ten wzorzec) typowi, nie jest ten koncept jednak zapisywany w żaden sposób w języku C++ - może on istnieć wyłącznie w głowie programisty (choć nawet z całym szacunkiem dla wszelkich głów, lepiej jest ten koncept udokumentować :*). W tym temacie przede wszystkim polecam dokumentację do STL-a. Przykładem konceptu jest "przypisywalny", który stanowi, że pasujący do tego konceptu typ musi posiadać operator przypisania i konstruktor kopiujący - jak widać koncepty można wyróżniać także w typach WBUDOWANYCH - i to właśnie jest chyba wzorców najmocniejsza strona. Wzorzec oczywiście to tylko wzorzec i nie jest przeznaczony do żadnego użycia. Użyć można dopiero twór powstały po jego KONKRETYZACJI. Konkretyzacja wzorca struktury staje się strukturą, podobnie jak konkretyzacja wzorca funkcji staje się funkcją. Konkretyzację przedstawię już na konkretnych przykładach. wzorzec funkcji Ten wzorzec jest zdecydowanie łatwiejszy. Oto jeden z najprostszych przykładów; funkcja Min: template <class T> inline const T& Min( const T& t1, const T& t2 ) { if ( t1 < t2 ) return t1; return t2; } Jeśli teraz użyjemy tej funkcji: int b, c; ... int a = Min( b, c ); to ze wzorca funkcji Min zostanie wygenerowana funkcja o nagłówku inline const int& Min( const int&, const int& ); Oczywiście na pewno ktoś zarzuci, że dużo łatwiej jest zrobić to tak: #define Min( t1, t2 ) ((t1)<(t2)? (t1) : (t2)) Jednak w takim wypadku życzę miłego szukania błędu przy wywołaniu np. Min( x, y++ ); Pamiętajmy oczywiście, że wzorzec jest z natury statyczny, nie "mutuje się" podczas wykonywania programu, jak to ma miejsce w "językach funkcyjnych". Zatem z reguły wzorce funkcji należy deklarować jako inline; kompilator bowiem wygeneruje dla każdego zestawu parametrów wzorca osobną postać funkcji. Często dobrym rozwiązaniem jest napisanie kilku wrapperów, które będą wzorcami funkcji i będą dostosowywać argumenty do wywołania jednej "głównej" funkcji. Wzorzec funkcji oczywiście zostanie skonkretyzowany, jeśli się go użyje (jak w powyższym przykładzie). Ale uwaga: jeśli a i b będą innego typu, to kompilator będzie miał problem. To znaczy dokładnie to użytkownik będzie miał problem, bowiem żadne "inteligentne konwersje", jak w przypadku operatorów dla typów ścisłych, nie będą wykonywane. Gdyby np. w powyższym przykładzie `a' było typu float, to należałoby przekonwertować albo `a' na int, albo `b' na float. W razie konieczności oczywiście, można wzorzec zadeklarować z dwoma parametrami (tyle, że w tym wypadku należałoby zdecydować, który typ miałby być zwrócony, a to chyba tutaj nie byłoby możliwe...). Oczywiście, podstawowym sposobem konkretyzacji wzorca jest podanie parametru wzorca po jego nazwie (w nawiasach ostrych oczywiście): return Min<float>( a, b ); Dlaczego dopuszcza się więc napisanie Min( a, b )? Otóż jest to coś podobnego do argumentów domyślnych funkcji; na podstawie użycia wzorca kompilator może "domniemać", jaki parametr wzorca tam należy zastosować (nazywa się to dopasowaniem do wzorca). W tym celu jednak w każdym miejscu, gdzie on wystąpi, musi być on zdezasygnowany identycznie, w przeciwnym razie danej konstrukcji kompilator w ogóle nie potraktuje za próbe zastosowania danego wzorca. Parę uwag na koniec. Innym powodem, dla którego powinno się wzorce funkcji deklarować jako "krótkie inline" to ten, że nie da się praktycznie użyć wzorca funkcji w innym module kompilacji, niż ten, w którym jest on zadeklarowany. Gdyby było to możliwe, kompilator miałby kłopot nie lada. Kompilacja każdej jednostki przebiega oddzielnie, zatem jeśli jeden z modułów tylko "używa" wzorca funkcji, a jej definicja jest w oddzielnej jednostce (i to nie wiadomo jakiej), to całość "do kupy" można złożyć (czyli również "rozwinąć" wzorzec) dopiero na etapie wiązania! A to wymaga już dostosowania do C++ programu wiążącego (linkera). Nie znaczy to wcale, że C++ nigdy nie będzie takiej właściwości posiadał. Istnieje w C++ takie słowo kluczowe export (stawia się go przed template), które oznacza, że wzorzec ma być przystosowany do eksportowania, czyli będzie można go wywołać z innego modułu. Jak na razie jednak tylko "słyszałem" o tej właściwości, jednak nie słyszałem o kompilatorze, który by to implementował. I jeszcze jedno. Wzorce funkcji mają takie ograniczenie, że nie da się napisać tak wzorca, żeby parametr wzorca mógł nie być użyty w jej definicji (ale żeby było możliwe napisanie kilku wersji tej samej funkcji różniącej się tylko parametrem wzorca), co pozwoliłoby zadeklarować grupę wariantów funkcji. Są jednak na to dwie metody - albo zadeklarować dodatkowy argument (być może domyślny), albo zadeklarować funkcję jako funkcję statyczną jakiegoś wzorca struktury... Wzorzec struktury Jednym z najczęstszych motywów użycia wzorca struktury jest typ zbiorczy. Wielu bowiem próbowało deklarować listę, ale za każdym razem trzeba było robić to inaczej (inną metodą było zadeklarowanie elementu jako `void*', aczkolwiek jest to typowo "Smalltalkowskie" podejście). Najprościej liste (w stylu C) można było zrobić tak: struct node { int i; node* next; }; Jednak typ int jest niezbyt szczęśliwym typem do trzymania go w liście. Dlatego, zamiast `int', można zastosować parametr wzorca, czyli: template <class T> struct node { T i; node<T>* next; }; Zauważ, że typu `node' nie można "nie konkretyzować" (można wstawić parametr domyślny, ale to jest mało istotne), jeśli się go zamierza używać. Jeśli chodzi jednak ogólnie o listy, to istnieje kilka koncepcji ich budowania. Przedstawiona koncepcja to przez pod-obiekt. Podobnie ma się koncepcja przez beta-obiekt, z tym tylko, że jako parametr wzorca należy podać wskaźnik na dany typ. W C można zrobić podobnie (sposobem Smalltalkowym): struct node { void* vo; node* next; }; Istnieje jednak trzecia możliwość - wyprowadzanie typu trzymanego w liście z typu węzła. Brzmi trochę tajemniczo, ale postaram się to odsłonić zlekka w drugiej części. Oczywiście, wzorce mogą mieć również parametry domyślne (też przez znak `='), a nawet w ich definicjach można użyć tego, co zostało podane w parametrach wcześniej (czego nie da się w funkcjach). Na przykład: template < class Type, class Pointer = Type* > ... Jest o możliwe jednak tylko we wzorcach struktury. Przy okazji wyjaśnię jeszcze, co oznacza to `class' w parametrach wzorca. Jak się można domyślać, chodzi tu o to, że ten podany parametr jest klasą. Nie oznacza to bynajmniej, że musi to być typ zadeklarowany słowem class; może to być dowolny identyfikator, który tylko oznacza jakikolwiek typ. Ostatnio zaczęto używać zamiast class `typename'. Można tak, aczkolwiek nie do końca do tego celu jest to słowo stworzone. Jest czasem taki problem ze wzorcami, że koncept określa kwestię zdefiniowania przez dany typ jakiegoś jego elementu. I np. chcemy, żeby dany typ zdefiniował w swoim wnętrzu identyfikator będący nazwą typu. W definicji wzorca określamy, jak dany identyfikator ma zostać użyty. Niestety wszystko przebiegnie prawidłowo tylko wtedy, jeżeli faktycznie tak jest ten identyfikator zdefiniowany. Jeśli będzie to coś innego, niż nazwa typu (np. nazwa pola), to kompilator nie zgłosi błędu tylko zgłupieje -- interpretacja wyrażenia w C++ zależy od tego, czym jest dany identyfikator; zatem to samo wyrażenie może mieć wiele różnych interpretacji w zależności od tego, czym są użyte w nim idetyfikatory. Spróbuj sobie wyobrazić, czy zinterpretował(a)byś wyrażenie, w którym po identyfikatorze podano nawiasy. Wyrażenie takie jest prawidłowe, gdy identyfikator jest nazwą funkcji, nazwą typu i nazwą automatycznego lub statycznego obiektu klasy, której zdefiniowano operator (). Właśnie za tą kwestię twórcy kompilatorów siarczyście klną na C++. Właśnie dlatego zatem, żeby wymóc, że dany identyfikator jest nazwą typu, wprowadzono słowo kluczowe typename. Dzięki temu kompilator nie głupieje przy wyrażeniach, które nie wiadomo, co oznaczają (w razie deklaracji zmiennej takiego typu wręcz wymusza użycie słowa typename), a gdyby wyciągnięty ze wzorca identyfikator nie był typem, kompilator będzie o tym wiedział i zgłosi błąd. Twórcy biblioteki STL postarali się również o rozszerzenie tego pomysłu. Np. większość definiowanych tam funkcji przeznaczonych do bezpośredniego użycia wywołuje odpowiednią inną funkcję z dodatkowymi argumentami (zazwyczaj typów pusto-zdefiniowanych, czyli np. struktura z pustymi klamrami). Służy to do sprawdzenia, czy dany typ ma wymagane możliwości, np. czy jest typem całkowitym. Zdefiniowano tam taki wzorzec klasy o nazwie type_traits (patrz type_traits.h). Specjalizacja wzorców Oczywiście z konkretyzowaniem wzorców są jeszcze lepsze numery. Np. kiedy mamy w strukturze jakąś metodę, staje się ona również wzorcem. Jednak wzorzec funkcji może być tylko w zapowiedzi wzorcem. W realizacji można zrobić np. coś takiego: template < class tT > tT Funkcja( const tT& ); int Funkcja( const int& i ) { ... } float Funkcja( const float& f ) { ... } template < class tT > tT Funkcja( const tT& t ) { ... } W takiej sytuacji, jeśli wywoła się funkcję z argumentem float, czy int - będzie wywołana jedna z bezpośrednio zdefiniowanych funkcji, jeśli inny typ - odpowiednia funkcja zostanie wygenerowana z podanego wzorca. Obiecałem wcześniej, że pokażę wersję NULL lepiej dostosowaną do C++. Oto ona: static class empty_pointer_value { void* const __internal_data; // needed for `...' public: empty_pointer_value(): __internal_data( 0 ) {} template <class tT> tT* cast() { return (tT*)0; } template <class tT> operator tT* const() { return cast(); } } null; Nazwałem go `null', żeby nazwa nie kolidowała z NULL; ta wartość jest bowiem objęta innymi regułami, niż NULL, którego reguły są identyczne z wartością bezstanową 0. Tak zdefiniowane null adoptuje się do każdego wskaźnika (tylko nie do funkcji, metody, czy pola!), można go przypisywać, przekazywać jako argument, jak również porównywać. Ale to jeszcze nie wszystko. Celowo zadeklarowałem metodę cast(), żeby łatwiej było ją przedefiniować. Jeśli np. zrobimy to dla typu Klocek... template <> Klocek* empty_pointer_value::cast<Klocek>() { return null_klocek; } to wtedy instrukcja Klocek* k = null; w istocie przypisze do k wartość null_klocek. Tak samo wartość null_klocek zostanie przekazana do funkcji, jeśli na tym miejscu oczekiwała typu Klocek*. Tak samo też dowolna wartość typu Klocek*, jeśli zostanie porównana z null, w rzeczywistości zostanie porównana z null_klocek. Wzorców nie musimy również specjalizować w całości. Jedną z nowszych właściwości wzorców w C++ jest tzw. częściowa specjalizacja ("partial specialization"). Nie będę już wyszczególniał. Umożliwia ona stworzenie nowego wzorca o tej samej nazwie, z tym tylko, że np.: wzorzec pierwotny miał dwa parametry, a nasz nowy ma tylko jeden; drugi jest sprecyzowany wymyślamy całkiem nową strukturę wzorca o innych parametrach, tzn. specyfikujemy parametry wzorca pierwotnego, ale w bieżącym dodajemy jakieś nowe lub inne - tu należy trochę uważać na niejednoznaczności, mniej więcej podobnie jak przy przeciążaniu funkcji Osobiście udało mi się uzyskać jedno z bardziej wyrafinowanych zastosowań wzorców (coś, co możnaby nazwać "krzyżyjące się wzorce"). Zapraszam do lektury. Mam nadzieje, że znasz angielski wystarczająco dobrze :*). Przykład oczywiście nie ma żadnego jako-takiego sensu. Całość sprowadza się jedynie do "wyszukania danego elementu w danym zbiorze na podstawie danego kryterium". Ani zbiór, ani kryterium, ani typ elementu nie mogą być tu podane wprost. Mamy tutaj zastosowane dwa rodzaje wariantów: warianty dla typów (tutaj użyte są float i int) oraz warianty dla kryteriów. Użycie float i int jest drobnym mankamentem tego przykładu (wymusiło to też konieczność zdefiniowania funkcji FindInt i FindFloat), ale mam nadzieje, że dobrze obrazuje użycie. Typy liczb determinują sposób ich przygotowania (czyli rodzaju operacji z podanym argumentem), natomiast warianty (eSices) determinują sposób wybierania liczby (tylko parzyste lub tylko nieparzyste). Główną częścią jest funkcja Find; cała reszta to tylko najróżniejsze opakowania i plugin'y pozwalające używać tej funkcji w różnych wariantach (cały przykład jest właściwie pod to robiony, że SPOSÓB - nie kryterium - wyszukiwania danego elementu, zakodowany w `Find' może być bardzo skomplikowany). Oczywiście wielu zarzuci mi, że "wyważam otwarte drzwi" - gdyby to miało mieć jakieś poważne zastosowanie, z pewnością bym się zgodził; dużo szybciej i łatwiej wykona się to za pomocą STL-owskiego algorytmu `find'. Jednak mnie chodziło tylko o eksperyment. #include <iostream> using namespace std; // Basics inline bool IsOdd( const int number ) { return number & 1; } inline bool IsEven( const int number ) { return !IsOdd( number ); } // Variants for numbers types are int/float // Variants for sices are MALE/FEMALE enum eSices { MALE, FEMALE }; // 1-3 crossing: variant for number type (number preparing) int Prepare( int arg, int item ) { return arg - item; } int Prepare( int arg, float item ) { return int( arg + item ); } template< eSices sex > struct Check { // Check what? static bool Number( int ); }; // 2-4 crossing: variant for sex (prepared number checking) bool Check<MALE>::Number( int nr ) { return IsEven( nr ); } bool Check<FEMALE>::Number( int nr ) { return IsOdd( nr ); } // Main checking function template (link within both variations) template < eSices sex, typename tT > struct Kind { static bool IsOk( int a, const tT* t ) { return Check<sex>::Number( Prepare( a, *t ) ); } }; // Look over given array to find a number corresponding to `argument' template< eSices sex, typename tT > inline tT* Find( int argument, tT* tab ) { for ( tT* p = tab; p != tab + 3; p++ ) if ( Kind<sex, tT>::IsOk( argument, p ) ) return p; return 0; } // We need arrays. Sorry, this is a little complication, but // it depends on using int/float types. In serious implementation // the elements would be accessed thru either the type name or the // item pointer; NEVER thru a uniq table name (that means, the container // would be accessed variantly). If the table name is universal, the // difference between FindInt and FindFloat would be only at numerical // types those can be requested with the second template parameter. int itab[] = { 1, 2, 3, 4 }; float ftab[] = { 4, 3, 2, 1 }; template< eSices sex > inline int* FindInt( int arg ) { return Find<sex, int>( arg, itab ); } template< eSices sex > inline float* FindFloat( int arg ) { return Find<sex, float>( arg, ftab ); } int main() { cout << "Male of 2: "; int* t = FindInt<MALE>( 2 ); if ( !t ) cout << "Not found.\n"; else cout << *t << endl; cout << "Female of 2: "; t = FindInt<FEMALE>( 2 ); if ( !t ) cout << "Not found.\n"; else cout << *t << endl; return 0; } Podsumowanie wzorców W kwestii podsumowania przypomnę jeszcze dokładnie, jakie są najważniejsze różnice pomiędzy wzorcem funkcji i wzorcem struktury. Wzorzec funkcji swoje parametry może domniemać na podstawie podanych do funkcji argumentów. Argument może mieć definicję upstrzoną parametrami wzorca, które w ten właśnie sposób zostaną wyciągnięte. Na przykład: template<size_t size, class T> inline size_t array_size( T (&t)[size] ) { return size; } Tu, jak widać, żąda się referencji do tablicy (zatem może ta funkcja przyjąć łańcuch tekstowy, jak też tablicę zainicjalizowaną bez podania rozmiaru, ale nie wskaźnik!), która jest rozmiaru określonego parametrem size. Właśnie dlatego ona jest inline, gdyż kompilator wygenerowałby dla każdego rozmiaru tablicy inną wersję. Wzorce funkcji mają właśnie tę fajną właściwość, że mogą dedukować parametry na podstawie podanych argumentów funkcji. Wzorce funkcji jednak NIE mogą posiadać ani parametrów domyślnych, ani nie mogą być częściowo specjalizowane. Również wszystkie parametry MUSZĄ uczestniczyć w definicjach argumentów funkcji. Te ostatnie właściwości posiadają jedynie wzorce struktury. Częściowa specjalizacja polega na tym, żeby zdefiniować wzorzec na bazie innego wzorca. To znaczy: najpierw trzeba zadeklarować wzorzec ogólny, tzn. generyczny (a jeśli lubimy określenie "polimorfizm parametryczny", to można też go nazwać "holomorficznym" - ale to mówię tylko dla rozbawienia studentów i absolwentów studiów inżynierskich :): template <class X, size_t s> struct Klocek { ... A dopiero potem można je częściowo specjalizować, tzn.: template <class Z> struct Klocek<Z, 0> { ... Jeśli definicje klas mają się różnić tylko i wyłącznie np. implementacją jednej metody, to nie trzeba specjalizować w tym celu jednek klasy, wystarczy wyspecjalizować tylko metodę. Oczywiście nadal można jedynie sprecyzować parametry wzorca struktury (bo tak przy okazji - właściwość zwana "wzorce metod" też nie była dostępna od samego początku!). Ponieważ w programowaniu wzorców bardzo często konieczne jest wyzyskanie zarówno domniemania parametrów, jak i częściowej specjalizacji, często stosuje się na przemian wzorzec funkcji i wzorzec struktury. Widać to np. w STL-u, gdzie stosuje się funkcje pomocnicze tworzące obiekt tymczasowy właśnie po to, aby domniemać parametr, który będzie typem argumentu, a następnie tym parametrem sprecyzować odpowiedni wzorzec struktury - jak np. inserter() do insert_iterator, czy ptr_fun() do pointer_to_unary_function i pointer_to_binary_function (szczegóły w następnym rozdziale). Istnieje też odwrotne wspomaganie: aby móc uzyskać częściową specjalizację dla wzorców funkcji, wzorzec funkcji wywołuje metodę statyczną zdefiniowaną wewnątrz wzorca struktury. Ze znanych w C++ wzorców struktury mamy przede wszystkim typ complex (nagłówek <complex>). Można go konkretyzować dowolnym typem, choć istnieją skonkretyzowane warianty complex, czyli float_complex, double_complex i long_double_complex. Nie będę się rozpisywał nt. tej klasy (można się wszystkiego dowiedzieć z plików nagłówkowych). Dostępne są wszelkie operacje arytmetyczne, jak również wszelkie metody i funkcje matematyczne konieczne dla typu complex. Jedną z najlepszych bibliotek opartych na wzorcach jest oczywiście STL, która jest aktualnie częścią biblioteki standardowej. Istnieje jednak też wiele innych bibliotek opartych na wzorcach, jak np. BOOST (www.boost.org). Charakterystyczną cechą takich bibliotek jest przede wszystkim ich uniwersalność i bardzo prosta rozszerzalność. Jeśli jednak chodzi o BOOST to jest to jedna z najbardziej zaawansowanych i funkcjonalnych bibliotek - choć opiera się nie tylko na wzorcach.