har*); PFV set_slist_handler(PFV a) { PFV old = slist_handler; slist_handler = a; return old; } PFV slist_handler = &default_slist_handler; Osobye situacii, kotorye obsuzhdayutsya v glave 9, ne tol'ko dayut al'ternativnyj sposob obrabotki oshibok, no i sposob realizacii slist_handler. 8.3.4 Iteraciya V klasse slist_base net funkcij dlya prosmotra spiska, mozhno tol'ko vstavlyat' i udalyat' elementy. Odnako, v nem opisyvaetsya kak drug klass slist_base_iter, poetomu mozhno opredelit' podhodyashchij dlya spiska iterator. Vot odin iz vozmozhnyh, zadannyj v tom stile, kakoj byl pokazan v $$7.8: class slist_base_iter { slink* ce; // tekushchij element slist_base* cs; // tekushchij spisok public: inline slist_base_iter(slist_base& s); inline slink* operator()() }; slist_base_iter::slist_base_iter(slist_base& s) { cs = &s; ce = cs->last; } slink* slist_base_iter::operator()() // vozvrashchaet 0, kogda iteraciya konchaetsya { slink* ret = ce ? (ce=ce->next) : 0; if (ce == cs->last) ce = 0; return ret; } Ishodya iz etih opredelenij, legko poluchit' iteratory dlya Slist i Islist. Snachala nado opredelit' druzhestvennye klassy dlya iteratorov po sootvetstvuyushchim kontejnernym klassam: template<class T> class Islist_iter; template<class T> class Islist { friend class Islist_iter<T>; // ... }; template<class T> class Slist_iter; template<class T> class Slist { friend class Slist_iter<T>; // ... }; Obratite vnimanie, chto imena iteratorov poyavlyayutsya bez opredeleniya ih shablonnogo klassa. |to sposob opredeleniya v usloviyah vzaimnoj zavisimosti shablonov tipa. Teper' mozhno opredelit' sami iteratory: template<class T> class Islist_iter : private slist_base_iter { public: Islist_iter(Islist<T>& s) : slist_base_iter(s) { } T* operator()() { return (T*) slist_base_iter::operator()(); } }; template<class T> class Slist_iter : private slist_base_iter { public: Slist_iter(Slist<T>& s) : slist_base_iter(s) { } inline T* operator()(); }; T* Slist_iter::operator()() { return ((Tlink<T>*) slist_base_iter::operator()())->info; } Zamet'te, chto my opyat' ispol'zovali priem, kogda iz odnogo bazovogo klassa stroitsya semejstvo proizvodnyh klassov (a imenno, shablonnyj klass). My ispol'zuem nasledovanie, chtoby vyrazit' obshchnost' klassov i izbezhat' nenuzhnogo dublirovaniya funkcij. Trudno pereocenit' stremlenie izbezhat' dublirovaniya funkcij pri realizacii takih prostyh i chasto ispol'zuemyh klassov kak spiski i iteratory. Pol'zovat'sya etimi iteratorami mozhno tak: void f(name* p) { Islist<name> lst1; Slist<name> lst2; lst1.insert(p); lst2.insert(p); // ... Islist_iter<name> iter1(lst1); const name* p; while (p=iter1()) { list_iter<name> iter2(lst1); const name* q; while (q=iter2()) { if (p == q) cout << "najden" << *p << '\n'; } } } Est' neskol'ko sposobov zadat' iterator dlya kontejnernogo klassa. Razrabotchik programmy ili biblioteki dolzhen vybrat' odin iz nih i priderzhivat'sya ego. Privedennyj sposob mozhet pokazat'sya slishkom hitrym. V bolee prostom variante mozhno bylo prosto pereimenovat' operator()() kak next(). V oboih variantah predpolagaetsya vzaimosvyaz' mezhdu kontejnernym klassom i iteratorom dlya nego, tak chto mozhno pri vypolnenii iteratora obrabotat' sluchai, kogda elementy dobavlyayutsya ili udalyayutsya iz kontejnera. |tot i nekotorye drugie sposoby zadaniya iteratorov byli by nevozmozhny, esli by iterator zavisel ot funkcii pol'zovatelya, v kotoroj est' ukazateli na elementy iz kontejnera. Kak pravilo, kontejner ili ego iteratory realizuyut ponyatie "ustanovit' iteraciyu na nachalo" i ponyatie "tekushchego elementa". Esli ponyatie tekushchego elementa predostavlyaet ne iterator, a sam kontejner, iteraciya proishodit v prinuditel'nom poryadke po otnosheniyu k kontejneru analogichno tomu, kak polya svyazi prinuditel'no hranyatsya v ob容ktah iz kontejnera. Znachit trudno odnovremenno vesti dve iteracii dlya odnogo kontejnera, no rashody na pamyat' i vremya pri takoj organizacii iteracii blizki k optimal'nym. Privedem primer: class slist_base { // ... slink* last; // last->next golova spiska slink* current; // tekushchij element public: // ... slink* head() { return last?last->next:0; } slink* current() { return current; } void set_current(slink* p) { current = p; } slink* first() { set_current(head()); return current; } slink* next(); slink* prev(); }; Podobno tomu, kak v celyah effektivnosti i kompaktnosti programmy mozhno ispol'zovat' dlya odnogo ob容kta kak spisok s prinuditel'noj svyaz'yu, tak i spisok bez nee, dlya odnogo kontejnera mozhno ispol'zovat' prinuditel'nuyu i neprinuditel'nuyu iteraciyu: void f(Islist<name>& ilst) // medlennyj poisk imen-dublikatov { list_iter<name> slow(ilst); // ispol'zuetsya iterator name* p; while (p = slow()) { ilst.set_current(p); // rasschityvaem na tekushchij element name* q; while (q = ilst.next()) if (strcmp(p->string,q->string) == 0) cout << "dublikat" << p << '\n'; } } Eshche odin vid iteratorov pokazan v $$8.8. 8.4 SHablony tipa dlya funkcij Ispol'zovanie shablonnyh klassov oznachaet nalichie shablonnyh funkcij-chlenov. Pomimo etogo, mozhno opredelit' global'nye shablonnye funkcii, t.e. shablony tipa dlya funkcij, ne yavlyayushchihsya chlenami klassa. SHablon tipa dlya funkcij porozhdaet semejstvo funkcij tochno takzhe, kak shablon tipa dlya klassa porozhdaet semejstvo klassov. |tu vozmozhnost' my obsudim na posledovatel'nosti primerov, v kotoryh privodyatsya varianty funkcii sortirovki sort(). Kazhdyj iz variantov v posleduyushchih razdelah budet illyustrirovat' obshchij metod. Kak obychno my sosredotochimsya na organizacii programmy, a ne na razrabotke ee algoritma, poetomu ispol'zovat'sya budet trivial'nyj algoritm. Vse varianty shablona tipa dlya sort() nuzhny dlya togo, chtoby pokazat' vozmozhnosti yazyka m poleznye priemy programmirovaniya. Varianty ne uporyadocheny v sootvetstvii s tem, naskol'ko oni horoshi. Krome togo, mozhno obsudit' i tradicionnye varianty bez shablonov tipa, v chastnosti, peredachu ukazatelya na funkciyu, proizvodyashchuyu sravnenie. 8.4.1 Prostoj shablon tipa dlya global'noj funkcii Nachnem s prostejshego shablona dlya sort(): template<class T> void sort(Vector<T>&); void f(Vector<int>& vi, Vector<String>& vc, Vector<int>& vi2, Vector<char*>& vs) { sort(vi); // sort(Vector<int>& v); sort(vc); // sort(Vector<String>& v); sort(vi2); // sort(Vector<int>& v); sort(vs); // sort(Vector<char*>& v); } Kakaya imenno funkciya sort() budet vyzyvat'sya opredelyaetsya fakticheskim parametrom. Programmist daet opredelenie shablona tipa dlya funkcii, a zadacha sistemy programmirovaniya obespechit' sozdanie pravil'nyh variantov funkcii po shablonu i vyzov sootvetstvuyushchego varianta. Naprimer, prostoj shablon s algoritmom puzyr'kovoj sortirovki mozhno opredelit' tak: template<class T> void sort(Vector<T>& v) /* Sortirovka elementov v poryadke vozrastaniya Ispol'zuetsya sortirovka po metodu puzyr'ka */ { unsigned n = v.size(); for (int i=0; i<n-1; i++) for (int j=n-1; i<j; j--) if (v[j] < v[j-1]) { // menyaem mestami v[j] i v[j-1] T temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } } Sovetuem sravnit' eto opredelenie s funkciej sortirovki s tem zhe algoritmom iz $$4.6.9. Sushchestvennoe otlichie etogo varianta v tom, chto vsya neobhodimaya informaciya peredaetsya v edinstvennom parametre v. Poskol'ku tip sortiruemyh elementov izvesten (iz tipa fakticheskogo parametra, mozhno neposredstvenno sravnivat' elementy, a ne peredavat' ukazatel' na proizvodyashchuyu sravnenie funkciyu. Krome togo, net nuzhdy vozit'sya s operaciej sizeof. Takoe reshenie kazhetsya bolee krasivym i k tomu zhe ono bolee effektivno, chem obychnoe. Vse zhe ono stalkivaetsya s trudnost'yu. Dlya nekotoryh tipov operaciya < ne opredelena, a dlya drugih, naprimer char*, ee opredelenie protivorechit tomu, chto trebuetsya v privedennom opredelenii shablonnoj funkcii. (Dejstvitel'no, nam nuzhno sravnivat' ne ukazateli na stroki, a sami stroki). V pervom sluchae popytka sozdat' variant sort() dlya takih tipov zakonchitsya neudachej (na chto i sleduet nadeyat'sya) , a vo vtorom poyavit'sya funkciya, proizvodyashchaya neozhidannyj rezul'tat. CHtoby pravil'no sortirovat' vektor iz elementov char* my mozhem prosto zadat' samostoyatel'no podhodyashchee opredelenie funkcii sort(Vector<char*>&): void sort(Vector<char*>& v) { unsigned n = v.size(); for (int i=0; i<n-1; i++) for ( int j=n-1; i<j; j--) if (strcmp(v[j],v[j-1])<0) { // menyaem mestami v[j] i v[j-1] char* temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } } Poskol'ku dlya vektorov iz ukazatelej na stroki pol'zovatel' dal svoe osoboe opredelenie funkcii sort(), ono i budet ispol'zovat'sya, a sozdavat' dlya nee opredelenie po shablonu s parametrom tipa Vector<char*>& ne nuzhno. Vozmozhnost' dat' dlya osobo vazhnyh ili "neobychnyh" tipov svoe opredelenie shablonnoj funkcii daet cennoe kachestvo gibkosti v programmirovanii i mozhet byt' vazhnym sredstvom dovedeniya programmy do optimal'nyh harakteristik. 8.4.2 Proizvodnye klassy pozvolyayut vvesti novye operacii V predydushchem razdele funkciya sravneniya byla "vstroennoj" v tele sort() (prosto ispol'zovalas' operaciya <). Vozmozhno drugoe reshenie, kogda ee predostavlyaet sam shablonnyj klass Vector. Odnako, takoe reshenie imeet smysl tol'ko pri uslovii, chto dlya tipov elementov vozmozhno osmyslennoe ponyatie sravneniya. Obychno v takoj situacii funkciyu sort() opredelyayut tol'ko dlya vektorov, na kotoryh opredelena operaciya < : template<class T> void sort(SortableVector<T>& v) { unsigned n = v.size(); for (int i=0; i<n-1; i++) for (int j=n-1; i<j; j--) if (v.lessthan(v[j],v[j-1])) { // menyaem mestami v[j] i v[j-1] T temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } } Klass SortableVector (sortiruemyj vektor) mozhno opredelit' tak: template<class T> class SortableVector : public Vector<T>, public Comparator<T> { public: SortableVector(int s) : Vector<T>(s) { } }; CHtoby eto opredelenie imelo smysl eshche nado opredelit' shablonnyj klass Comparator (sravnivatel'): template<class T> class Comparator { public: inline static lessthan(T& a, T& b) // funkciya "men'she" { return strcmp(a,b)<0; } // ... }; CHtoby ustranit' tot effekt, chto v nashem sluchae operaciya < daet ne tot rezul'tat dlya tipa char*, my opredelim special'nyj variant klassa sravnivatelya: class Comparator<char*> { public: inline static lessthan(const char* a, const char* b) // funkciya "men'she" { return strcmp(a,b)<0; } // ... }; Opisanie special'nogo varianta shablonnogo klassa dlya char* polnost'yu podobno tomu, kak v predydushchem razdele my opredelili special'nyj variant shablonnoj funkcii dlya etoj zhe celi. CHtoby opisanie special'nogo varianta shablonnogo klassa srabotalo, translyator dolzhen obnaruzhit' ego do ispol'zovaniya. Inache budet ispol'zovat'sya sozdavaemyj po shablonu klass. Poskol'ku klass dolzhen imet' v tochnosti odno opredelenie v programme, ispol'zovat' i special'nyj variant klassa, i variant, sozdavaemyj po shablonu, budet oshibkoj. Poskol'ku u nas uzhe special'nyj variant klassa Comparator dlya char*, special'nyj variant klassa SortableVector dlya char* ne nuzhen, i mozhem, nakonec, poprobovat' sortirovku: void f(SortableVector<int>& vi, SortableVector<String>& vc, SortableVector<int>& vi2, SortableVector<char*>& vs) { sort(vi); sort(vc); sort(vi2); sort(vs); } Vozmozhno imet' dva vida vektorov i ne ochen' horosho, no, po krajnej mere, SortableVector yavlyaetsya proizvodnym ot Vector. Znachit esli v funkcii ne nuzhna sortirovka, to v nej i ne nado znat' o klasse SortableVector, a tam, gde nuzhno, srabotaet neyavnoe preobrazovanie ssylki na proizvodnyj klass v ssylku na obshchij bazovyj klass. My vveli proizvodnyj ot Vector i Comparator klass SortableVector (vmesto togo, chtoby dobavit' funkcii k klassu, proizvodnomu ot odnogo Vector) prosto potomu, chto klass Comparator uzhe naprashivalsya v predydushchim primere. Takoj podhod tipichen pri sozdanii bol'shih bibliotek. Klass Comparator estestvennyj kandidat dlya biblioteki, poskol'ku v nem mozhno ukazat' razlichnye trebovaniya k operaciyam sravneniya dlya raznyh tipov. 8.4.3 Peredacha operacij kak parametrov funkcij Mozhno ne zadavat' funkciyu sravneniya kak chast' tipa Vector, a peredavat' ee kak vtoroj parametr funkcii sort(). |tot parametr yavlyaetsya ob容ktom klassa, v kotorom opredelena realizaciya operacii sravneniya: template<class T> void sort(Vector<T>& v, Comparator<T>& cmp) { unsigned n = v.size(); for (int i = 0; i<n-1; i++) for ( int j = n-1; i<j; j--) if (cmp.lessthan(v[j],v[j-1])) { // menyaem mestami v[j] i v[j-1] T temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } } |tot variant mozhno rassmatrivat' kak obobshchenie tradicionnogo priema, kogda operaciya sravneniya peredaetsya kak ukazatel' na funkciyu. Vospol'zovat'sya etim mozhno tak: void f(Vector<int>& vi, Vector<String>& vc, Vector<int>& vi2, Vector<char*>& vs) { Comparator<int> ci; Comparator<char*> cs; Comparator<String> cc; sort(vi,ci); // sort(Vector<int>&); sort(vc,cc); // sort(Vector<String>&); sort(vi2,ci); // sort(Vector<int>&); sort(vs,cs); // sort(Vector<char*>&); } Otmetim, chto vklyuchenie v shablon klassa Comparator kak parametra garantiruet, chto funkciya lessthan budet realizovyvat'sya podstanovkoj. V chastnosti, eto polezno, esli v shablonnoj funkcii ispol'zuetsya neskol'ko funkcij, a ne odna operaciya sravneniya, i osobenno eto polezno, kogda eti funkcii zavisyat ot hranyashchihsya v tom zhe ob容kte dannyh. 8.4.4 Neyavnaya peredacha operacij V primere iz predydushchego razdela ob容kty Comparator na samom dele nikak ne ispol'zovalis' v vychisleniyah. |to prosto "iskusstvennye" parametry, nuzhnye dlya pravil'nogo kontrolya tipov. Vvedenie takih parametrov dostatochno obshchij i poleznyj priem, hotya i ne slishkom krasivyj. Odnako, esli ob容kt ispol'zuetsya tol'ko dlya peredachi operacii (kak i bylo v nashem sluchae), t.e. v vyzyvaemoj funkcii ne ispol'zuetsya ni znachenie, ni adres ob容kta, to mozhno vmesto etogo peredavat' operaciyu neyavno: template<class T> void sort(Vector<T>& v) { unsigned n = v.size(); for (int i=0; i<n-1; i++) for (int j=n-1; i<j; j--) if (Comparator<T>::lessthan(v[j],v[j-1])) { // menyaem mestami v[j] i v[j-1] T temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } } V rezul'tate my prihodim k pervonachal'nomu variantu ispol'zovaniya sort(): void f(Vector<int>& vi, Vector<String>& vc, Vector<int>& vi2, Vector<char*>& vs) { sort(vi); // sort(Vector<int>&); sort(vc); // sort(Vector<String>&); sort(vi2); // sort(Vector<int>&); sort(vs); // sort(Vector<char*>&); } Osnovnoe preimushchestvo etogo varianta, kak i dvuh predydushchih, po sravneniyu s ishodnym variantom v tom, chto chast' programmy, zanyataya sobstvenno sortirovkoj, otdelena ot chastej, v kotoryh nahodyatsya takie operacii, rabotayushchie s elementami, kak, naprimer lessthan. Neobhodimost' podobnogo razdeleniya rastet s rostom programmy, i osobennyj interes eto razdelenie predstavlyaet pri proektirovanii bibliotek. Zdes' sozdatel' biblioteki ne mozhet znat' tipy parametrov shablona, a pol'zovateli ne znayut (ili ne hotyat znat') specifiku ispol'zuemyh v shablone algoritmov. V chastnosti, esli by v funkcii sort() ispol'zovalsya bolee slozhnyj, optimizirovannyj i rasschitannyj na kommercheskoe primenenie algoritm, pol'zovatel' ne ochen' by stremilsya napisat' svoyu osobuyu versiyu dlya tipa char*, kak eto bylo sdelano v $$8.4.1. Hotya realizaciya klassa Comparator dlya special'nogo sluchaya char* trivial'na i mozhet ispol'zovat'sya i v drugih situaciyah. 8.4.5 Vvedenie operacij s pomoshch'yu parametrov shablonnogo klassa Vozmozhny situacii, kogda neyavnost' svyazi mezhdu shablonnoj funkciej sort() i shablonnym klassom Comparator sozdaet trudnosti. Neyavnuyu svyaz' legko upustit' iz vidu i v to zhe vremya razobrat'sya v nej mozhet byt' neprosto. Krome togo, poskol'ku eta svyaz' "vstroena" v funkciyu sort(), nevozmozhno ispol'zovat' etu funkciyu dlya sortirovki vektorov odnogo tipa, esli operaciya sravneniya rasschitana na drugoj tip (sm. uprazhnenie 3 v $$8.9). Pomestiv funkciyu sort() v klass, my mozhem yavno zadavat' svyaz' s klassom Comparator: template<class T, class Comp> class Sort { public: static void sort(Vector<T>&); }; Ne hochetsya povtoryat' tip elementa, i eto mozhno ne delat', esli ispol'zovat' typedef v shablone Comparator: template<class T> class Comparator { public: typedef T T; // opredelenie Comparator<T>::T static int lessthan(T& a, T& b) { return a < b; } // ... }; V special'nom variante dlya ukazatelej na stroki eto opredelenie vyglyadit tak: class Comparator<char*> { public: typedef char* T; static int lessthan(T a, T b) { return strcmp(a,b) < 0; } // ... }; Posle etih izmenenij mozhno ubrat' parametr, zadayushchij tip elementa, iz klassa Sort: template<class T, class Comp> class Sort { public: static void sort(Vector<T>&); }; Teper' mozhno ispol'zovat' sortirovku tak: void f(Vector<int>& vi, Vector<String>& vc, Vector<int>& vi2, Vector<char*>& vs) { Sort< int,Comparator<int> >::sort(vi); Sort< String,Comparator<String> >:sort(vc); Sort< int,Comparator<int> >::sort(vi2); Sort< char*,Comparator<char*> >::sort(vs); } i opredelit' funkciyu sort() sleduyushchim obrazom: template<class T, class Comp> void Sort<T,Comp>::sort(Vector<T>& v) { for (int i=0; i<n-1; i++) for (int j=n-1; i<j; j--) if (Comp::lessthan(v[j],v[j-1])) { T temp = v[j]; v[j] = v[j-1]; v[j-1] = temp; } } Poslednij variant yarko demonstriruet kak mozhno soedinyat' v odnu programmu otdel'nye ee chasti. |tot primer mozhno eshche bol'she uprostit', esli ispol'zovat' klass sravnitelya (Comp) v kachestve edinstvennogo parametra shablona. V etom sluchae v opredeleniyah klassa Sort i funkcii Sort::sort() tip elementa budet oboznachat'sya kak Comp::T. 8.5 Razreshenie peregruzki dlya shablonnoj funkcii K parametram shablonnoj funkcii nel'zya primenyat' nikakih preobrazovanij tipa. Vmesto etogo pri neobhodimosti sozdayutsya novye varianty funkcii: template<class T> T sqrt(t); void f(int i, double d, complex z) { complex z1 = sqrt(i); // sqrt(int) complex z2 = sqrt(d); // sqrt(double) complex z3 = sqrt(z); // sqrt(complex) // ... } Zdes' dlya vseh treh tipov parametrov budet sozdavat'sya po shablonu svoya funkciya sqrt. Esli pol'zovatel' zahochet chego-nibud' inogo, naprimer vyzvat' sqrt(double), zadavaya parametr int, nuzhno ispol'zovat' yavnoe preobrazovanie tipa: template<class T> T sqrt(T); void f(int i, double d, complex z) { complex z1 = sqrt(double(i)); // sqrt(double) complex z2 = sqrt(d); // sqrt(double) complex z3 = sqrt(z); // sqrt(complex) // ... } V etom primere po shablonu budut sozdavat'sya opredeleniya tol'ko dlya sqrt(double) i sqrt(complex). SHablonnaya funkciya mozhet peregruzhat'sya kak prostoj, tak i shablonnoj funkciej togo zhe imeni. Razreshenie peregruzki kak shablonnyh, tak i obychnyh funkcij s odinakovymi imenami proishodit za tri shagaX: X |ti pravila slishkom strogie, i, po vsej vidimosti budut oslableny, chtoby razreshit' preobrazovaniya ssylok i ukazatelej, a, vozmozhno, i drugie standartnye preobrazovaniya. Kak obychno, pri takih preobrazovaniyah budet dejstvovat' kontrol' odnoznachnosti. [1] Najti funkciyu s tochnym sopostavleniem parametrov ($$R.13.2); esli takaya est', vyzvat' ee. [2] Najti shablon tipa, po kotoromu mozhno sozdat' vyzyvaemuyu funkciyu s tochnym sopostavleniem parametrov; esli takaya est', vyzvat' ee. [3] Poprobovat' pravila razresheniya dlya obychnyh funkcij ($$r13.2); esli funkciya najdena po etim pravilam, vyzvat' ee, inache vyzov yavlyaetsya oshibkoj. V lyubom sluchae, esli na pervom shage najdeno bolee odnoj funkcii, vyzov schitaetsya neodnoznachnym i yavlyaetsya oshibkoj. Naprimer: template<class T> T max(T a, T b) { return a>b?a:b; }; void f(int a, int b, char c, char d) { int m1 = max(a,b); // max(int,int) char m2 = max(c,d); // max(char,char) int m3 = max(a,c); // oshibka: nevozmozhno // sozdat' max(int,char) } Poskol'ku do generacii funkcii po shablonu ne primenyaetsya nikakih preobrazovanij tipa (pravilo [2]), poslednij vyzov v etom primere nel'zya razreshit' kak max(a,int(c)). |to mozhet sdelat' sam pol'zovatel', yavno opisav funkciyu max(int,int). Togda vstupaet v silu pravilo [3]: template<class T> T max(T a, T b) { return a>b?a:b; } int max(int,int); void f(int a, int b, char c, char d) { int m1 = max(a,b); // max(int,int) char m2 = max(c,d); // max(char,char) int m3 = max(a,c); // max(int,int) } Programmistu ne nuzhno davat' opredelenie funkcii max(int,int), ono po umolchaniyu budet sozdano po shablonu. Mozhno opredelit' shablon max tak, chtoby srabotal pervonachal'nyj variant nashego primera: template<class T1, class T2> T1 max(T1 a, T2 b) { return a>b?a:b; }; void f(int a, int b, char c, char d) { int m1 = max(a,b); // int max(int,int) char m2 = max(c,d); // char max(char,char) int m3 = max(a,c); // max(int,char) } Odnako, v S i S++ pravila dlya vstroennyh tipov i operacij nad nimi takovy, chto ispol'zovat' podobnyj shablon s dvumya parametrami mozhet byt' sovsem neprosto. Tak, mozhet okazat'sya neverno zadavat' tip rezul'tata funkcii kak pervyj parametr (T1), ili, po krajnej mere, eto mozhet privesti k neozhidannomu rezul'tatu, naprimer dlya vyzova max(c,i); // char max(char,int) Esli v shablone dlya funkcii, kotoraya mozhet imet' mnozhestvo parametrov s razlichnymi arifmeticheskimi tipami, ispol'zuyutsya dva parametra, to v rezul'tate po shablonu budet porozhdat'sya slishkom bol'shoe chislo opredelenij raznyh funkcij. Bolee razumno dobivat'sya preobrazovaniya tipa, yavno opisav funkciyu s nuzhnymi tipami. 8.6 Parametry shablona tipa Parametr shablona tipa ne obyazatel'no dolzhen byt' imenem tipa (sm. $$R.14.2). Pomimo imen tipov mozhno zadavat' stroki, imena funkcij i vyrazheniya-konstanty. Inogda byvaet nuzhno zadat' kak parametr celoe: template<class T, int sz> class buffer { T v[sz]; // bufer ob容ktov proizvol'nogo tipa // ... }; void f() { buffer<char,128> buf1; buffer<complex,20> buf2; // ... } My sdelali sz parametrom shablona buffer, a ne ego ob容ktov, i eto oznachaet, chto razmer bufera dolzhen byt' izvesten na stadii translyacii, chtoby ego ob容kty bylo mozhno razmeshchat', ne ispol'zuya svobodnuyu pamyat'. Blagodarya etomu svojstvu takie shablony kak buffer polezny dlya realizacii kontejnernyh klassov, poskol'ku dlya poslednih pervostepennym faktorom, opredelyayushchim ih effektivnost', yavlyaetsya vozmozhnost' razmeshchat' ih vne svobodnoj pamyati. Naprimer, esli v realizacii klassa string korotkie stroki razmeshchayutsya v steke, eto daet sushchestvennyj vyigrysh dlya programmy, poskol'ku v bol'shinstve zadach prakticheski vse stroki ochen' korotkie. Dlya realizacii takih tipov kak raz i mozhet prigodit'sya shablon buffer. Kazhdyj parametr shablona tipa dlya funkcii dolzhen vliyat' na tip funkcii, i eto vliyanie vyrazhaetsya v tom, chto on uchastvuet po krajnej mere v odnom iz tipov formal'nyh parametrov funkcij, sozdavaemyh po shablonu. |to nuzhno dlya togo, chtoby funkcii mozhno bylo vybirat' i sozdavat', osnovyvayas' tol'ko na ih parametrah: template<class T> void f1(T); // normal'no template<class T> void f2(T*); // normal'no template<class T> T f3(int); // oshibka template<int i> void f4(int[][i]); // oshibka template<int i> void f5(int = i); // oshibka template<class T, class C> void f6(T); // oshibka template<class T> void f7(const T&, complex); // normal'no template<class T> void f8(Vector< List<T> >); // normal'no Zdes' vse oshibki vyzvany tem, chto parametr-tip shablona nikak ne vliyaet na formal'nye parametry funkcij. Podobnogo ogranicheniya net v shablonah tipa dlya klassov. Delo v tom, chto parametr dlya takogo shablona nuzhno ukazyvat' vsyakij raz, kogda opisyvaetsya ob容kt shablonnogo klassa. S drugoj storony, dlya shablonnyh klassov voznikaet vopros: kogda dva sozdannyh po shablonu tipa mozhno schitat' odinakovymi? Dva imeni shablonnogo klassa oboznachayut odin i tot zhe klass, esli sovpadayut imena ih shablonov, a ispol'zuemye v etih imenah parametry imeyut odinakovye znacheniya (s uchetom vozmozhnyh opredelenij typedef, vychisleniya vyrazhenij-konstant i t.d.). Vernemsya k shablonu buffer: template<class T, int sz> class buffer { T v[sz]; // ... }; void f() { buffer<char,20> buf1; buffer<complex,20> buf2; buffer<char,20> buf3; buffer<char,100> buf4; buf1 = buf2; // oshibka: nesootvetstvie tipov buf1 = buf3; // normal'no buf1 = buf4; // oshibka: nesootvetstvie tipov // ... } Esli v shablone tipa dlya klassa ispol'zuyutsya parametry, zadayushchie ne tipy, vozmozhno poyavlenie konstrukcij, vyglyadyashchih dvusmyslenno: template<int i> class X { /* ... */ }; void f(int a, int b) { X < a > b>; // Kak eto ponimat': X<a> b i potom // nedopustimaya leksema, ili X< (a>b) >; ? } |tot primer sintaksicheski oshibochen, poskol'ku pervaya uglovaya skobka > zavershaet parametr shablona. V maloveroyatnom sluchae, kogda vam ponadobitsya parametr shablona, yavlyayushchijsya vyrazheniem "bol'she chem", ispol'zujte skobki: X< (a>b)>. 8.7 SHablony tipa i proizvodnye klassy My uzhe videli, chto sochetanie proizvodnyh klassov (nasledovanie) i shablonov tipa mozhet byt' moshchnym sredstvom. SHablon tipa vyrazhaet obshchnost' mezhdu vsemi tipami, kotorye ispol'zuyutsya kak ego parametry, a bazovyj klass vyrazhaet obshchnost' mezhdu vsemi predstavleniyami (ob容ktami) i nazyvaetsya interfejsom. Zdes' vozmozhny nekotorye prostye nedorazumeniya, kotoryh nado izbegat'. Dva sozdannyh po odnomu shablonu tipa budut razlichny i mezhdu nimi nevozmozhno otnoshenie nasledovaniya krome edinstvennogo sluchaya, kogda u etih tipov identichny parametry shablona. Naprimer: template<class T> class Vector { /* ... */ } Vector<int> v1; Vector<short> v2; Vector<int> v3; Zdes' v1 i v3 odnogo tipa, a v2 imeet sovershenno drugoj tip. Iz togo fakta, chto short neyavno preobrazuetsya v int, ne sleduet, chto est' neyavnoe preobrazovanie Vector<short> v Vector<int>: v2 = v3; // nesootvetstvie tipov No etogo i sledovalo ozhidat', poskol'ku net vstroennogo preobrazovaniya int[] v short[]. Analogichnyj primer: class circle: public shape { /* ... */ }; Vector<circle*> v4; Vector<shape*> v5; Vector<circle*> v6; Zdes' v4 i v6 odnogo tipa, a v5 imeet sovershenno drugoj tip. Iz togo fakta, chto sushchestvuet neyavnoe preobrazovanie circle v shape i circle* v shape*, ne sleduet, chto est' neyavnye preobrazovaniya Vector<circle*> v Vector<shape*> ili Vector<circle*>* v Vector<shape*>* : v5 = v6; // nesootvetstvie tipov Delo v tom, chto v obshchem sluchae struktura (predstavlenie) klassa, sozdannogo po shablonu tipa, takova, chto dlya nee ne predpolagayutsya otnosheniya nasledovaniya. Tak, sozdannyj po shablonu klass mozhet soderzhat' ob容kt tipa, zadannogo v shablone kak parametr, a ne prosto ukazatel' na nego. Krome togo, dopushchenie podobnyh preobrazovanij privodit k narusheniyu kontrolya tipov: void f(Vector<circle>* pc) { Vector<shape>* ps = pc; // oshibka: nesootvetstvie tipov (*ps)[2] = new square; // krugluyu nozhku suem v kvadratnoe // otverstie (pamyat' vydelena dlya // square, a ispol'zuetsya dlya circle } Na primerah shablonov Islist, Tlink, Slist, Splist, Islist_iter, Slist_iter i SortableVector my videli, chto shablony tipa dayut udobnoe sredstvo dlya sozdaniya celyh semejstv klassov. Bez shablonov sozdanie takih semejstv tol'ko s pomoshch'yu proizvodnyh klassov mozhet byt' utomitel'nym zanyatiem, a znachit, vedushchim k oshibkam. S drugoj storony, esli otkazat'sya ot proizvodnyh klassov i ispol'zovat' tol'ko shablony, to poyavlyaetsya mnozhestvo kopij funkcij-chlenov shablonnyh klassov, mnozhestvo kopij opisatel'noj chasti shablonnyh klassov i vo mnozhestve povtoryayutsya funkcii, ispol'zuyushchie shablony tipa. 8.7.1 Zadanie realizacii s pomoshch'yu parametrov shablona V kontejnernyh klassah chasto prihoditsya vydelyat' pamyat'. Inogda byvaet neobhodimo (ili prosto udobno) dat' pol'zovatelyu vozmozhnost' vybirat' iz neskol'kih variantov vydeleniya pamyati, a takzhe pozvolit' emu zadavat' svoj variant. |to mozhno sdelat' neskol'kimi sposobami. Odin iz sposobov sostoit v tom, chto opredelyaetsya shablon tipa dlya sozdaniya novogo klassa, v interfejs kotorogo vhodit opisanie sootvetstvuyushchego kontejnera i klassa, proizvodyashchego vydelenie pamyati po sposobu, opisannomu v $$6.7.2: template<class T, class A> class Controlled_container : public Container<T>, private A { // ... void some_function() { // ... T* p = new(A::operator new(sizeof(T))) T; // ... } // ... }; SHablon tipa zdes' neobhodim, poskol'ku my sozdaem kontejnernyj klass. Nasledovanie ot Container<T> nuzhno, chtoby klass Controlled_container mozhno bylo ispol'zovat' kak kontejnernyj klass. SHablon tipa s parametrom A pozvolit nam ispol'zovat' razlichnye funkcii razmeshcheniya: class Shared : public Arena { /* ... */ }; class Fast_allocator { /* ... */ }; Controlled_container<Process_descriptor,Shared> ptbl; Controlled_container<Node,Fast_allocator> tree; Controlled_container<Personell_record,Persistent> payroll; |to universal'nyj sposob predostavlyat' proizvodnym klassam soderzhatel'nuyu informaciyu o realizacii. Ego polozhitel'nymi kachestvami yavlyayutsya sistematichnost' i vozmozhnost' ispol'zovat' funkcii-podstanovki. Dlya etogo sposoba harakterny neobychno dlinnye imena. Vprochem, kak obychno, typedef pozvolyaet zadat' sinonimy dlya slishkom dlinnyh imen tipov: typedef Controlled_container<Personell_record,Persistent> pp_record; pp_record payroll; Obychno shablon tipa dlya sozdaniya takogo klassa kak pp_record ispol'zuyut tol'ko v tom sluchae, kogda dobavlyaemaya informaciya po realizacii dostatochno sushchestvenna, chtoby ne vnosit' ee v proizvodnyj klass ruchnym programmirovaniem. Primerom takogo shablona mozhet byt' obshchij (vozmozhno, dlya nekotoryh bibliotek standartnyj) shablonnyj klass Comparator ($$8.4.2), a takzhe netrivial'nye (vozmozhno, standartnye dlya nekotoryh bibliotek) klassy Allocator (klassy dlya vydeleniya pamyati). Otmetim, chto postroenie proizvodnyh klassov v takih primerah idet po "osnovnomu prospektu", kotoryj opredelyaet interfejs s pol'zovatelem (v nashem primere eto Container). No est' i "bokovye ulicy", zadayushchie detali realizacii. 8.8 Associativnyj massiv Iz vseh universal'nyh nevstroennyh tipov samym poleznym, po vsej vidimosti, yavlyaetsya associativnyj massiv. Ego chasto nazyvayut tablicej (map), a inogda slovarem, i on hranit pary znachenij. Imeya odno iz znachenij, nazyvaemoe klyuchom, mozhno poluchit' dostup k drugomu, nazyvaemomu prosto znacheniem. Associativnyj massiv mozhno predstavlyat' kak massiv, v kotorom indeks ne obyazan byt' celym: template<class K, class V> class Map { // ... public: V& operator[](const K&); // najti V, sootvetstvuyushchee K // i vernut' ssylku na nego // ... }; Zdes' klyuch tipa K oboznachaet znachenie tipa V. Predpolagaetsya, chto klyuchi mozhno sravnivat' s pomoshch'yu operacij == i <, tak chto massiv mozhno hranit' v uporyadochennom vide. Otmetim, chto klass Map otlichaetsya ot tipa assoc iz $$7.8 tem, chto dlya nego nuzhna operaciya "men'she chem", a ne funkciya heshirovaniya. Privedem prostuyu programmu podscheta slov, v kotoroj ispol'zuyutsya shablon Map i tip String: #include <String.h> #include <iostream.h> #include "Map.h" int main() { Map<String,int> count; String word; while (cin >> word) count[word]++; for (Mapiter<String,int> p = count.first(); p; p++) cout << p.value() << '\t' << p.key() << '\n'; return 0; } My ispol'zuem tip String dlya togo, chtoby ne bespokoit'sya o vydelenii pamyati i perepolnenii ee, o chem prihoditsya pomnit', ispol'zuya tip char*. Iterator Mapiter nuzhen dlya vybora po poryadku vseh znachenij massiva. Iteraciya v Mapiter zadaetsya kak imitaciya raboty s ukazatelyami. Esli vhodnoj potok imeet vid It was new. It was singular. It was simple. It must succeed. programma vydast 4 It 1 must 1 new. 1 simple. 1 singular. 1 succeed. 3 was. Konechno, opredelit' associativnyj massiv mozhno mnogimi sposobami, a, imeya opredelenie Map i svyazannogo s nim klassa iteratora, my mozhem predlozhit' mnogo sposobov dlya ih realizacii. Zdes' vybran trivial'nyj sposob realizacii. Ispol'zuetsya linejnyj poisk, kotoryj ne podhodit dlya bol'shih massivov. Estestvenno, rasschitannaya na kommercheskoe primenenie realizaciya budet sozdavat'sya, ishodya iz trebovanij bystrogo poiska i kompaktnosti predstavleniya (sm. uprazhnenie 4 iz $$8.9). My ispol'zuem spisok s dvojnoj svyaz'yu Link: template<class K, class V> class Map; template<class K, class V> class Mapiter; template<class K, class V> class Link { friend class Map<K,V>; friend class Mapiter<K,V>; private: const K key; V value; Link* pre; Link* suc; Link(const K& k, const V& v) : key(k), value(v) { } ~Link() { delete suc; } // rekursivnoe udalenie vseh // ob容ktov v spiske }; Kazhdyj ob容kt Link soderzhit paru (klyuch, znachenie). Klassy opisany v Link kak druz'ya, i eto garantiruet, chto ob容kty Link mozhno sozdavat', rabotat' s nimi i unichtozhat' tol'ko s pomoshch'yu sootvetstvuyushchih klassov iteratora i Map. Obratite vnimanie na predvaritel'nye opisaniya shablonnyh klassov Map i Mapiter. SHablon Map mozhno opredelit' tak: template<class K, class V> class Map { friend class Mapiter<K,V>; Link<K,V>* head; Link<K,V>* current; V def_val; K def_key; int sz; void find(const K&); void init() { sz = 0; head = 0; current = 0; } public: Map() { init(); } Map(const K& k, const V& d) : def_key(k), def_val(d) { init(); } ~Map() { delete head; } // rekursivnoe udalenie // vseh ob容ktov v spiske Map(const Map&); Map& operator= (const Map&); V& operator[] (const K&); int size() const { return sz; } void clear() { delete head; init(); } void remove(const K& k); // funkcii dlya iteracii Mapiter<K,V> element(const K& k) { (void) operator[](k); // sdelat' k tekushchim elementom return Mapiter<K,V>(this,current); } Mapiter<K,V> first(); Mapiter<K,V> last(); }; |lementy hranyatsya v uporyadochennom spiske s dojnoj svyaz'yu. Dlya prostoty nichego ne delaetsya dlya uskoreniya poiska (sm. uprazhnenie 4 iz $$8.9). Klyuchevoj zdes' yavlyaetsya funkciya operator[](): template<class K, class V> V& Map<K,V>::operator[] (const K& k) { if (head == 0) { current = head = new Link<K,V>(k,def_val); current->pre = current->suc = 0; return current->value; } Link<K,V>* p = head; for (;;) { if (p->key == k) { // najdeno current = p; return current->value; } if (k < p->key) { // vstavit' pered p (v nachalo)