ylok
                 srep() { n = 1; }
               };
               srep *p;

            public:
              string(const char *);   // string x = "abc"
              string();               // string x;
              string(const string &); // string x = string ...
              string& operator=(const char *);
              string& operator=(const string &);
              ~string();
              char& operator[](int i);

              friend ostream& operator<<(ostream&, const string&);
              friend istream& operator>>(istream&, string&);

              friend int operator==(const string &x, const char *s)
                { return strcmp(x.p->s,s) == 0; }

              friend int operator==(const string &x, const string &y)
                { return strcmp(x.p->s,y.p->s) == 0; }

              friend int operator!=(const string &x, const char *s)
                { return strcmp(x.p->s,s) != 0; }

              friend int operator!=(const string &x, const string &y)
                { return strcmp(x.p->s,y.p->s) != 0; }
           };

Konstruktory i destruktory trivial'ny:

           string::string()
           {
             p = new srep;
             p->s = 0;
           }

           string::string(const string& x)
           {
             x.p->n++;
             p = x.p;
           }

           string::string(const char* s)
           {
             p = new srep;
             p->s = new char[ strlen(s)+1 ];
             strcpy(p->s, s);
           }

           string::~string()
           {
             if (--p->n == 0) {
                delete[]  p->s;
                delete p;
             }
           }

 Kak i vsegda operacii prisvaivaniya pohozhi na konstruktory. V nih
 nuzhno pozabotit'sya ob udalenii pervogo operanda, zadayushchego levuyu
 chast' prisvaivaniya:

          string& string::operator=(const char* s)
          {
            if (p->n > 1) {  // otsoedinyaemsya ot staroj stroki
                p->n--;
                p = new srep;
            }
            else    // osvobozhdaem stroku so starym znacheniem
                delete[] p->s;

            p->s = new char[ strlen(s)+1 ];
            strcpy(p->s, s);
            return *this;
          }

          string& string::operator=(const string& x)
          {
            x.p->n++;  // zashchita ot sluchaya ``st = st''
            if (--p->n == 0) {
               delete[] p->s;
               delete p
            }
            p = x.p;
            return *this;
          }

 Operaciya vyvoda pokazyvaet kak ispol'zuetsya schetchik chisla ssylok.
 Ona soprovozhdaet kak eho kazhduyu vvedennuyu stroku (vvod proishodit
 s pomoshch'yu operacii << , privedennoj nizhe):

          ostream& operator<<(ostream& s, const string& x)
          {
             return s << x.p->s << " [" << x.p->n << "]\n";
          }

 Operaciya vvoda proishodit s pomoshch'yu standartnoj funkcii vvoda
 simvol'noj stroki ($$10.3.1):

          istream& operator>>(istream& s, string& x)
          {
             char buf[256];
             s >> buf;   // nenadezhno: vozmozhno perepolnenie buf
                         // pravil'noe reshenie sm. v $$10.3.1
             x = buf;
             cout << "echo: " << x << '\n';
             return s;
           }

      Operaciya indeksacii nuzhna dlya dostupa k otdel'nym simvolam.
 Indeks kontroliruetsya:

          void error(const char* p)
          {
            cerr << p << '\n';
            exit(1);
          }

         char& string::operator[](int i)
        {
         if (i<0 || strlen(p->s)<i) error("nedopustimoe znachenie indeksa");
           return p->s[i];
        }

    V osnovnoj programme prosto dany neskol'ko primerov primeneniya
 strokovyh operacij. Slova iz vhodnogo potoka chitayutsya v stroki,
 a zatem stroki pechatayutsya. |to prodolzhaetsya do teh por, poka ne
 budet obnaruzhena stroka done, ili zakonchatsya stroki dlya zapisi
 slov, ili zakonchitsya vhodnoj potok. Zatem pechatayutsya vse stroki
 v obratnom poryadke i programma zavershaetsya.

         int main()
         {
           string x[100];
           int n;

           cout << " zdes' nachalo \n";

           for ( n = 0; cin>>x[n]; n++) {
               if (n==100) {
                  error("slishkom mnogo slov");
                  return 99;
               }
               string y;
               cout << (y = x[n]);
               if (y == "done") break;

           }
           cout << "teper' my idem po slovam v obratnom poryadke \n";
           for (int i=n-1; 0<=i; i--) cout << x[i];
           return 0;
         }

        7.12 Druz'ya i chleny

 V zaklyuchenii mozhno obsudit', kogda pri obrashchenii v zakrytuyu chast'
 pol'zovatel'skogo tipa stoit ispol'zovat' funkcii-chleny, a kogda
 funkcii-druz'ya. Nekotorye funkcii, naprimer konstruktory, destruktory
 i virtual'nye funkcii ($$R.12), obyazany byt' chlenami, no dlya drugih
 est' vozmozhnost' vybora. Poskol'ku, opisyvaya funkciyu kak chlen, my
 ne vvodim novogo global'nogo imeni, pri otsutstvii drugih dovodov
 sleduet ispol'zovat' funkcii-chleny.
      Rassmotrim prostoj klass X:

          class X {
             // ...

            X(int);

            int m1();
            int m2() const;

            friend int f1(X&);
            friend int f2(const X&);
            friend int f3(X);
         };

 Vnachale ukazhem, chto chleny X::m1() i X::m2() mozhno vyzyvat' tol'ko
 dlya ob容ktov klassa X. Preobrazovanie X(int) ne budet primenyat'sya
 k ob容ktu, dlya kotorogo vyzvany X::m1() ili X::m2():

          void g()
          {
             1.m1();  // oshibka: X(1).m1() ne ispol'zuetsya
             1.m2();  // oshibka: X(1).m2() ne ispol'zuetsya
          }

 Global'naya funkciya f1() imeet to zhe svojstvo ($$4.6.3), poskol'ku
 ee parametr - ssylka bez specifikacii const. S funkciyami f2() i
 f3() situaciya inaya:

          void h()
          {
            f1(1);  // oshibka: f1(X(1)) ne ispol'zuetsya
            f2(1);  // normal'no: f2(X(1));
            f3(1);  // normal'no: f3(X(1));
          }

     Sledovatel'no operaciya, izmenyayushchaya sostoyanie ob容kta klassa,
 dolzhna byt' chlenom ili global'noj funkciej s parametrom-ssylkoj
 bez specifikacii const. Operacii nad osnovnymi tipami, kotorye
 trebuyut v kachestve operandov adresa (=, *, ++ i t.d.),
 dlya pol'zovatel'skih tipov estestvenno opredelyat' kak chleny.
     Obratno, esli trebuetsya neyavnoe preobrazovanie tipa dlya vseh
 operandov nekotoroj operacii, to realizuyushchaya ee funkciya dolzhna
 byt' ne chlenom, a global'noj funkciej i imet' parametr tipa ssylki
 so specifikaciej const ili nessylochnyj parametr. Tak obychno obstoit
 delo s funkciyami, realizuyushchimi operacii, kotorye dlya osnovnyh
 tipov ne trebuyut adresov v kachestve operandov (+, -, || i t.d.).
     Esli operacii preobrazovaniya tipa ne opredeleny, to net
 neoproverzhimyh dovodov v pol'zu funkcii-chlena pered funkciej-drugom
 s parametrom-ssylkoj i naoborot. Byvaet, chto programmistu prosto
 odna forma zapisi vyzova nravitsya bol'she, chem drugaya.
 Naprimer, mnogim dlya oboznacheniya funkcii obrashcheniya matricy m bol'she
 nravitsya zapis' inv(m), chem m.inv(). Konechno, esli funkciya
 inv() obrashchaet samu matricu m, a ne vozvrashchaet novuyu, obratnuyu m,
 matricu, to inv() dolzhna byt' chlenom.
     Pri vseh prochih ravnyh usloviyah luchshe vse-taki ostanovit'sya
 na funkcii-chlene. Mozhno privesti takie dovody. Nel'zya garantirovat',
 chto kogda-nibud' ne budet opredelena operaciya obrashcheniya. Nel'zya vo
 vseh sluchayah garantirovat', chto budushchie izmeneniya ne povlekut za
 soboj izmeneniya v sostoyanii ob容kta. Zapis' vyzova funkcii-chlena
 yasno pokazyvaet programmistu, chto ob容kt mozhet byt' izmenen, togda
 kak zapis' s parametrom-ssylkoj daleko ne stol' ochevidna. Dalee,
 vyrazheniya dopustimye v funkcii-chlene mogut byt' sushchestvenno
 koroche ekvivalentnyh vyrazhenij v global'noj funkcii. Global'naya
 funkciya dolzhna ispol'zovat' yavno zadannye parametry, a v
 funkcii-chlene mozhno neyavno ispol'zovat' ukazatel' this. Nakonec,
 poskol'ku imena chlenov ne yavlyayutsya global'nymi imenami, oni obychno
 okazyvayutsya koroche, chem imen global'nyh funkcij.

        7.13 Predosterezheniya

 Kak i vsyakoe drugoe yazykovoe sredstvo, peregruzka operacij mozhet
 ispol'zovat'sya razumno i nerazumno. V chastnosti, vozmozhnost'yu
 pridavat' novyj smysl obychnym operaciyam mozhno vospol'zovat'sya
 tak, chto programma budet sovershenno nepostizhimoj. Predstav'te,
 kakovo budet chitatelyu, esli v svoej programme vy pereopredelili
 operaciyu + tak, chtoby ona oboznachala vychitanie. Opisannyj zdes'
 mehanizm peregruzki budet zashchishchat' programmista i pol'zovatelya ot
 takih bezrassudstv. Poetomu programmist ne mozhet izmenit' ni
 smysl operacij nad osnovnymi tipami dannyh, takimi, kak int, ni
 sintaksis vyrazhenij i prioritety operacij dlya nih.
     Po vsej vidimosti peregruzku operacij imeet smysl ispol'zovat'
 dlya podrazhaniya tradicionnomu ispol'zovaniyu operacij. Zapis' s obychnym
 vyzovom funkcii mozhno ispol'zovat' v teh sluchayah, kogda tradicionnoj
 zapisi s bazovoj operaciej ne sushchestvuet, ili, kogda nabor operacij,
 kotorye dopuskayut peregruzku, ne dostatochen, chtoby zapisat' s ego
 pomoshch'yu nuzhnye dejstviya.

        7.14 Uprazhneniya

 1. (*2) Opredelite iterator dlya klassa string. Opredelite operaciyu
    konkatenacii + i operaciyu += , znachashchuyu "dobavit' v konec stroki".
    Kakie eshche operacii vy hoteli by i smogli opredelit' dlya etogo
    klassa?
 2. (*1.5) Opredelite dlya strokovogo klassa operaciyu vydeleniya podstroki
    s pomoshch'yu peregruzki ().
 3. (*3) Opredelite klass string takim obrazom, chtoby operaciyu
    vydeleniya podstroki mozhno bylo primenyat' k levoj chasti
    prisvaivaniya. Vnachale napishite variant, v kotorom stroku mozhno
    prisvaivat' podstroke toj zhe dliny, a zatem variant s razlichnymi
    dlinami strok.
 4. (*2) Razrabotajte klass string takim obrazom, chtoby ob容kty
    ego traktovalis' pri peredache parametrov i prisvaivanii kak
    znacheniya, t.e. chtoby v klasse string kopirovalis' sami predstavleniya
    strok, a ne tol'ko upravlyayushchie struktury.
 5. (*3) Izmenite klass string iz predydushchego uprazhneniya tak, chtoby
    stroki kopirovalis' tol'ko pri neobhodimosti. |to znachit, chto
    nuzhno hranit' odno obshchee predstavleniya dvuh odinakovyh strok do
    teh por, poka odna iz nih ne izmenitsya. Ne pytajtes' zadat' operaciyu
    vydeleniya podstroki, kotoruyu odnovremenno mozhno primenyat' i k
    levoj chasti prisvaivaniya.
 6. (*4) Opredelite klass string, obladayushchij perechislennymi v
    predydushchih uprazhneniyah svojstvami: ob容kty ego traktuyutsya kak
    znacheniya, kopirovanie yavlyaetsya otlozhennym (t.e. proishodit tol'ko
    pri neobhodimosti) i operaciyu vydeleniya podstroki mozhno primenyat'
    k levoj chasti prisvaivaniya.
 7. (*2) Kakie preobrazovaniya tipa ispol'zuyutsya v vyrazheniyah sleduyushchej
    programmy?

           struct X {
             int i;
             X(int);
             operator+(int);
           };

           struct Y {
             int i;
             Y(X);
             operator+(X);
             operator int();
           };

           extern X operator*(X,Y);
           extern int f(X);

           X x = 1;
           Y y = x;
           int i = 2;

           int main()
           {
             i + 10;     y + 10;    y + 10 * y;
             x + y + i;  x * X +i;  f(7);
             f(y);       y + y;     106 + y;
           }

    Opredelite X i Y kak celye tipy. Izmenite programmu tak, chtoby
    ee mozhno bylo vypolnit' i ona napechatala znacheniya vseh
    pravil'nyh vyrazhenij.
 8. (*2) Opredelite klass INT, kotoryj budet ekvivalenten tipu int.
    Podskazka: opredelite funkciyu INT::operator int().
 9. (*1) Opredelite klass RINT, kotoryj budet ekvivalenten tipu int,
    za isklyucheniem togo, chto dopustimymi budut tol'ko operacii:
    + (unarnyj i binarnyj), - (unarnyj i binarnyj), *, / i %.
    Podskazka: ne nado opredelyat' RINT::operator int().
 10. (*3) Opredelite klass LINT, ekvivalentnyj klassu RINT, no v
    nem dlya predstavleniya celogo dolzhno ispol'zovat'sya ne menee 64
    razryadov.
 11. (*4) Opredelite klass, realizuyushchij arifmetiku s proizvol'noj
    tochnost'yu. Podskazka: Pridetsya ispol'zovat' pamyat' tak, kak
    eto delaetsya v klasse string.
 12. (*2) Napishite programmu, v kotoroj blagodarya makrokomandam i
    peregruzke budet nevozmozhno razobrat'sya. Sovet: opredelite dlya
    tipa INT + kak -, i naoborot; s pomoshch'yu makroopredeleniya zadajte
    int kak INT. Krome togo, bol'shuyu putanicu mozhno sozdat',
    pereopredelyaya shiroko izvestnye funkcii, i ispol'zuya parametry
    tipa ssylki i zadavaya vvodyashchie v zabluzhdenie kommentarii.
 13. (*3) Obmenyajtes' resheniyami uprazhneniya [12] s vashim drugom.
    Poprobujte ponyat', chto delaet ego programma, ne zapuskaya ee. Esli
    vy sdelaete eto uprazhnenie, vam stanet yasno, chego nado izbegat'.
 14. (*2) Perepishite primery s klassami complex ($$7.3), tiny
    ($$7.3.2) i string ($$7.11), ne ispol'zuya druzhestvennye funkcii.
    Ispol'zujte tol'ko funkcii-chleny. Prover'te novye versii etih
    klassov. Sravnite ih s versiyami, v kotoryh ispol'zuyutsya
    druzhestvennye funkcii. Obratites' k uprazhneniyu 5.3.
 15. (*2) Opredelite tip vec4 kak vektor iz chetyreh chisel s plavayushchej
    tochkoj. Opredelite dlya nego funkciyu operator[]. Dlya kombinacij
    vektorov i chisel s plavayushchej tochkoj opredelite operacii:
    +, -, *, /, =, +=, -=, *= i /=.
 16. (*3) Opredelite klass mat4 kak vektor iz chetyreh elementov tipa
    vec4. Opredelite dlya nego funkciyu operator[], vozvrashchayushchuyu vec4.
    Opredelite dlya etogo tipa obychnye operacii s matricami. Opredelite
    v mat4 funkciyu, proizvodyashchuyu preobrazovanie Gaussa s matricej.
 17. (*2) Opredelite klass vector, analogichnyj klassu vec4, no zdes'
    razmer vektora dolzhen zadavat'sya kak parametr konstruktora
    vector::vector(int).
 18. (*3) Opredelite klass matrix, analogichnyj klassu mat4, no zdes'
    razmernosti matricy dolzhny zadavat'sya kak parametry konstruktora
    matrix::matrix(int,int).
 19. (*3) Zavershite opredelenie klassa CheckedPtrToT iz $$7.10 i
    prover'te ego. CHtoby opredelenie etogo klassa bylo polnym,
    neobhodimo opredelit', po krajnej mere, takie operacii: *, ->,
    =, ++ i --. Ne vydavajte dinamicheskuyu oshibku, poka dejstvitel'no
    ne proizojdet obrashchenie po ukazatelyu s neopredelennym znacheniem.
 20. (*1.5) Perepishite primer s programmoj podscheta slov iz $$7.7
    tak, chtoby v nej ne bylo zaranee zadannoj maksimal'noj dliny
    slova.




         * GLAVA 8. SHABLONY  TIPA

          Vot vasha citata
             - B'ern Straustrup

    V etoj glave vvoditsya ponyatie shablona tipa. S ego pomoshch'yu mozhno
    dostatochno prosto opredelit' i realizovat' bez poter' v
    effektivnosti vypolneniya programmy i, ne otkazyvayas' ot staticheskogo
    kontrolya tipov, takie kontejnernye klassy, kak spiski i associativnye
    massivy. Krome togo, shablony tipa pozvolyayut opredelit' srazu dlya
    celogo semejstva tipov obobshchennye (genericheskie) funkcii, naprimer,
    takie, kak sort (sortirovka). V kachestve primera shablona tipov i
    ego svyazi s drugimi konstrukciyami yazyka privoditsya semejstvo
    spisochnyh klassov. CHtoby pokazat' sposoby polucheniya programmy iz
    v znachitel'noj stepeni nezavisimyh chastej, privoditsya neskol'ko
    variantov shablonnoj funkcii sort(). V konce opredelyaetsya prostoj
    shablon tipa dlya associativnogo massiva i pokazyvaetsya na dvuh
    nebol'shih demonstracionnyh programmah, kak im pol'zovat'sya.

        8.1 Vvedenie

 Odnim iz samyh poleznyh vidov klassov yavlyaetsya kontejnernyj klass,
 t.e. takoj klass, kotoryj hranit ob容kty kakih-to drugih tipov.
 Spiski, massivy, associativnye massivy i mnozhestva - vse eto
 kontejnernye klassy. S pomoshch'yu opisannyh v glavah 5 i 7 sredstv
 mozhno opredelit' klass, kak kontejner ob容ktov edinstvennogo,
 izvestnogo tipa. Naprimer, v $$5.3.2 opredelyaetsya mnozhestvo celyh.
 No kontejnernye klassy obladayut tem interesnym svojstvom, chto tip
 soderzhashchihsya v nih ob容ktov ne imeet osobogo znacheniya dlya
 sozdatelya kontejnera, no dlya pol'zovatelya konkretnogo kontejnera
 etot tip yavlyaetsya sushchestvennym. Sledovatel'no, tip soderzhashchihsya
 ob容ktov dolzhen parametrom kontejnernogo klassa, i sozdatel' takogo
 klassa budet opredelyat' ego s pomoshch'yu tipa-parametra. Dlya kazhdogo
 konkretnogo kontejnera (t.e. ob容kta kontejnernogo klassa) pol'zovatel'
 budet ukazyvat' kakim dolzhen byt' tip soderzhashchihsya v nem ob容ktov.
 Primerom takogo kontejnernogo klassa byl shablon tipa Vector iz
 $$1.4.3.
      V etoj glave issleduetsya prostoj shablon tipa stack (stek) i
 v rezul'tate vvoditsya ponyatie shablonnogo klassa. Zatem rassmatrivayutsya
 bolee polnye i pravdopodobnye primery neskol'kih rodstvennyh shablonov
 tipa dlya spiska. Vvodyatsya shablonnye funkcii i formuliruyutsya pravila,
 chto mozhet byt' parametrom takih funkcij. V konce privoditsya shablon
 tipa dlya associativnogo massiva.

        8.2 Prostoj shablon tipa

 SHablon tipa dlya klassa zadaet sposob postroeniya otdel'nyh klassov,
 podobno tomu, kak opisanie klassa zadaet sposob postroeniya ego
 otdel'nyh ob容ktov. Mozhno opredelit' stek, soderzhashchij elementy
 proizvol'nogo tipa:

            template<class T>
            class stack {
               T* v;
               T* p;
               int sz;

            public:
               stack(int s) { v = p = new T[sz=s]; }
               ~stack() { delete[] v; }

               void push(T a) { *p++ = a; }
               T pop() { return *--p; }

               int size() const { return p-v; }
            };

 Dlya prostoty ne uchityvalsya kontrol' dinamicheskih oshibok. Ne schitaya
 etogo, primer polnyj i vpolne pravdopodobnyj.
     Prefiks template<class T> ukazyvaet, chto opisyvaetsya shablon
 tipa s parametrom T, oboznachayushchim tip, i chto eto oboznachenie
 budet ispol'zovat'sya v posleduyushchem opisanii. Posle togo, kak
 identifikator T ukazan v prefikse, ego mozhno ispol'zovat' kak lyuboe
 drugoe imya tipa. Oblast' vidimosti T prodolzhaetsya do konca opisaniya,
 nachavshegosya prefiksom template<class T>. Otmetim, chto v prefikse T
 ob座avlyaetsya tipom, i ono ne obyazano byt' imenem klassa. Tak, nizhe
 v opisanii ob容kta sc tip T okazyvaetsya prosto char.
     Imya shablonnogo klassa, za kotorym sleduet tip, zaklyuchennyj v
 uglovye skobki <>, yavlyaetsya imenem klassa (opredelyaemym shablonom
 tipa), i ego mozhno ispol'zovat' kak vse imena klassa. Naprimer, nizhe
 opredelyaetsya ob容kt sc klassa stack<char>:

          stack<char> sc(100);   // stek simvolov

     Esli ne schitat' osobuyu formu zapisi imeni, klass stack<char>
 polnost'yu ekvivalenten klassu opredelennomu tak:

          class stack_char {
             char* v;
             char* p;
             int sz;
          public:
             stack_char(int s) { v = p = new char[sz=s]; }
             ~stack_char() { delete[] v; }

             void push(char a) { *p++ = a; }
             char pop() { return *--p; }

             int size() const { return p-v; }
          };

 Mozhno podumat', chto shablon tipa - eto hitroe makroopredelenie,
 podchinyayushcheesya pravilam imenovaniya, tipov i oblastej vidimosti,
 prinyatym v S++. |to, konechno, uproshchenie, no eto takoe uproshchenie,
 kotoroe pomogaet izbezhat' bol'shih nedorazumenij. V chastnosti,
 primenenie shablona tipa ne predpolagaet kakih-libo sredstv
 dinamicheskoj podderzhki pomimo teh, kotorye ispol'zuyutsya dlya obychnyh
 "ruchnyh" klassov. Ne sleduet tak zhe dumat', chto ono privodit k
 sokrashcheniyu programmy.
       Obychno imeet smysl vnachale otladit' konkretnyj klass, takoj,
 naprimer, kak stack_char, prezhde, chem stroit' na ego osnove shablon tipa
 stack<T>. S drugoj storony, dlya ponimaniya shablona tipa polezno
 predstavit' sebe ego dejstvie na konkretnom tipe, naprimer int ili
 shape*, prezhde, chem pytat'sya predstavit' ego vo vsej obshchnosti.
      Imeya opredelenie shablonnogo klassa stack, mozhno sleduyushchim
 obrazom opredelyat' i ispol'zovat' razlichnye steki:

            stack<shape*> ssp(200);  // stek ukazatelej na figury
            stack<Point> sp(400);    // stek struktur Point

            void f(stack<complex>& sc)  // parametr tipa `ssylka na
                                        // complex'
            {
              sc.push(complex(1,2));
              complex z = 2.5*sc.pop();

              stack<int>*p = 0;         // ukazatel' na stek celyh
              p = new stack<int>(800);  // stek celyh razmeshchaetsya
                                        // v svobodnoj pamyati
              for ( int i = 0; i<400; i++) {
                  p->push(i);
                  sp.push(Point(i,i+400));
              }

              // ...
           }

 Poskol'ku vse funkcii-chleny klassa stack yavlyayutsya podstanovkami,
 i v etom primere translyator sozdaet vyzovy funkcij tol'ko dlya
 razmeshcheniya v svobodnoj pamyati i osvobozhdeniya.
      Funkcii v shablone tipa mogut i ne byt' podstanovkami, shablonnyj
 klass stack s polnym pravom mozhno opredelit' i tak:


            template<class T> class stack {
               T* v;
               T* p;
               int sz;
            public:
               stack(int);
               ~stack();

               void push(T);
               T pop();

               int size() const;
            };

 V etom sluchae opredelenie funkcii-chlena stack dolzhno byt' dano
 gde-to v drugom meste, kak eto i bylo dlya funkcij- chlenov
 obychnyh, neshablonnyh klassov.  Podobnye funkcii tak zhe
 parametriziruyutsya tipom, sluzhashchim parametrom dlya ih shablonnogo
 klassa, poetomu opredelyayutsya oni s pomoshch'yu shablona tipa dlya
 funkcii. Esli eto proishodit vne shablonnogo klassa, eto nado delat'
 yavno:

            template<class T> void stack<T>::push(T a)
            {
               *p++ = a;
            }

            template<class T> stack<T>::stack(int s)
            {
               v = p = new T[sz=s];
            }

 Otmetim, chto v predelah oblasti vidimosti imeni stack<T> utochnenie
 <T> yavlyaetsya izbytochnym, i stack<T>::stack - imya konstruktora.
     Zadacha sistemy programmirovaniya, a vovse ne programmista,
 predostavlyat' versii shablonnyh funkcij dlya kazhdogo fakticheskogo
 parametra shablona tipa. Poetomu dlya privodivshegosya vyshe primera
 sistema programmirovaniya dolzhna sozdat' opredeleniya konstruktorov dlya
 klassov stack<shape*>, stack<Point> i stack<int>, destruktorov dlya
 stack<shape*> i stack<Point>, versii funkcij push() dlya stack<complex>,
 stack<int> i stack<Point> i versiyu funkcii pop() dlya stack<complex>.
 Takie sozdavaemye funkcii budut sovershenno obychnymi funkciyami-chlenami,
 naprimer:

            void stack<complex>::push(complex a) { *p++ = a; }

 Zdes' otlichie ot obychnoj funkcii-chlena tol'ko v forme imeni klassa.
 Tochno tak zhe, kak v programme mozhet byt' tol'ko odno opredelenie
 funkcii-chlena klassa, vozmozhno tol'ko odno opredelenie shablona
 tipa dlya funkcii-chlena shablonnogo klassa. Esli trebuetsya opredelenie
 funkcii-chlena shablonnogo klassa dlya konkretnogo tipa, to zadacha sistemy
 programmirovaniya najti shablon tipa dlya etoj funkcii-chlena i sozdat'
 nuzhnuyu versiyu funkcii. V obshchem sluchae sistema programmirovaniya
 mozhet rasschityvat' na ukazaniya ot programmista, kotorye pomogut
 najti nuzhnyj shablon tipa.
      Vazhno sostavlyat' opredelenie shablona tipa takim obrazom, chtoby
 ego zavisimost' ot global'nyh dannyh byla minimal'noj. Delo v tom,
 shablon tipa budet ispol'zovat'sya dlya porozhdeniya funkcij i klassov
 na osnove zaranee neizvestnogo tipa i v neizvestnyh kontekstah.
 Prakticheski lyubaya, dazhe slabaya zavisimost' ot konteksta mozhet
 proyavit'sya kak problema pri otladke programmy pol'zovatelem, kotoryj,
 veroyatnee vsego, ne byl sozdatelem shablona tipa. K sovetu izbegat',
 naskol'ko eto vozmozhno, ispol'zovanij global'nyh imen, sleduet
 otnosit'sya osobenno ser'ezno pri razrabotke shablona tipa.

        8.3 SHablony tipa dlya spiska

 Na praktike pri razrabotke klassa, sluzhashchego kollekciej ob容ktov,
 chasto prihoditsya uchityvat' vzaimootnosheniya ispol'zuyushchihsya v realizacii
 klassov, upravlenie pamyat'yu i neobhodimost' opredelit' iterator po
 soderzhimomu kollekcii. CHasto byvaet tak, chto neskol'ko rodstvennyh
 klassov razrabatyvayutsya sovmestno ($$12.2). V kachestve primera my
 predlozhim semejstvo klassov, predstavlyayushchih odnosvyaznye spiski i
 shablony tipa dlya nih.

        8.3.1 Spisok s prinuditel'noj svyaz'yu

 Vnachale opredelim prostoj spisok, v kotorom predpolagaetsya, chto
 v kazhdom zanosimom v spisok ob容kte est' pole svyazi. Potom etot
 spisok budet ispol'zovat'sya kak stroitel'nyj material dlya sozdaniya
 bolee obshchih spiskov, v kotoryh ob容kt ne obyazan imet' pole svyazi.
 Sperva v opisaniyah klassov budet privedena tol'ko obshchaya chast',
 a realizaciya budet dana v sleduyushchem razdele. |to delaetsya za tem,
 chtoby voprosy proektirovaniya klassov ne zatemnyalis' detalyami ih
 realizacii.
    Nachnem s tipa slink, opredelyayushchego pole svyazi v odnosvyaznom spiske:

             struct slink {
               slink* next;
               slink() { next = 0; }
               slink(slink* p) { next = p; }
            };

 Teper' mozhno opredelit' klass, kotoryj mozhet soderzhat' ob容kty
 lyubogo, proizvodnogo ot slink, klassa:

            class slist_base {
               // ...
            public:
               int insert(slink*); // dobavit' v nachalo spiska
               int append(slink*); // dobavit' k koncu spiska
               slink* get();       // udalit' i vozvratit' nachalo spiska
               // ...
            };

 Takoj klass mozhno nazvat' spiskom s prinuditel'noj svyaz'yu, poskol'ku
 ego mozhno ispol'zovat' tol'ko v tom sluchae, kogda vse elementy imeyut
 pole slink, kotoroe ispol'zuetsya kak ukazatel' na slist_base.
 Samo imya slist_base (bazovyj odnosvyaznyj spisok) govorit, chto etot
 klass budet ispol'zovat'sya kak bazovyj dlya odnosvyaznyh spisochnyh
 klassov. Kak obychno, pri razrabotke semejstva rodstvennyh klassov
 voznikaet vopros, kak vybirat' imena dlya razlichnyh chlenov semejstva.
 Poskol'ku imena klassov ne mogut peregruzhat'sya, kak eto delaetsya
 dlya imen funkcij, dlya obuzdaniya razmnozheniya imen peregruzka nam ne
 pomozhet.
      Klass slist_base mozhno ispol'zovat' tak:

            void f()
            {
              slist_base slb;
              slb.insert(new slink);
              // ...
              slink* p = slb.get();
              // ...
              delete p;
            }

 No poskol'ku struktura slink ne mozhet soderzhat' nikakoj informacii
 pomimo svyazi, etot primer ne slishkom interesen. CHtoby vospol'zovat'sya
 slist_base, nado opredelit' poleznyj, proizvodnyj ot slink, klass.
 Naprimer, v translyatore ispol'zuyutsya uzly dereva programmy name
 (imya), kotorye prihoditsya svyazyvat' v spisok:

           class name : public slink {
              // ...
           };

           void f(const char* s)
           {
             slist_base slb;
             slb.insert(new name(s));
             // ...
             name* p = (name*)slb.get();
             // ...
             delete p;
           }

 Zdes' vse normal'no, no poskol'ku opredelenie klassa slist_base
 dano cherez strukturu slink, prihoditsya ispol'zovat' yavnoe privedenie
 tipa dlya preobrazovaniya znacheniya tipa slink*, vozvrashchaemogo
 funkciej slist_base::get(), v name*. |to nekrasivo. Dlya bol'shoj
 programmy, v kotoroj mnogo spiskov i proizvodnyh ot slink klassov,
 eto k tomu zhe chrevato oshibkami. Nam prigodilas' by nadezhnaya po
 tipu versiya klassa slist_base:

           template<class T>
           class Islist : private slist_base {
           public:
             void insert(T* a) { slist_base::insert(a); }
             T* get() { return (T*) slist_base::get(); }
             // ...
           };

 Privedenie v funkcii Islist::get() sovershenno opravdano i nadezhno,
 poskol'ku v klasse Islist garantiruetsya, chto kazhdyj ob容kt v spiske
 dejstvitel'no imeet tip T ili tip proizvodnogo ot T klassa. Otmetim,
 chto slist_base yavlyaetsya chastnym bazovym klassom Islist. My net hotim,
 chtoby pol'zovatel' sluchajno natolknulsya na nenadezhnye detali
 realizacii.
       Imya Islist (intrusive  singly linked list) oboznachaet
 odnosvyaznyj spisok s prinuditel'noj svyaz'yu. |tot shablon tipa
 mozhno ispol'zovat' tak:

           void f(const char* s)
           {
             Islist<name> ilst;
             ilst.insert(new name(s));
             // ...
             name* p = ilst.get();
             // ...
             delete p
           }

 Popytki nekorrektnogo ispol'zovaniya budet vyyavleny na stadii
 translyacii:

           class expr : public slink {
              // ...
           };

           void g(expr* e)
           {
             Islist<name> ilst;
             ilst.insert(e);  // oshibka: Islist<name>::insert(),
                              // a nuzhno name*
             // ...
           }

 Nuzhno otmetit' neskol'ko vazhnyh momentov otnositel'no nashego primera.
 Vo-pervyh, reshenie nadezhno v smysle tipov (pregrada trivial'nym
 oshibkam stavitsya v ochen' ogranichennoj chasti programmy, a imenno,
 v funkciyah dostupa iz Islist). Vo-vtoryh, nadezhnost' tipov
 dostigaetsya bez uvelicheniya zatrat vremeni i pamyati, poskol'ku
 funkcii dostupa iz Islist trivial'ny i realizuyutsya podstanovkoj.
 V-tret'ih, poskol'ku vsya nastoyashchaya rabota so spiskom delaetsya v
 realizacii klassa slist_base (poka eshche ne predstavlennoj), nikakogo
 dublirovaniya funkcij ne proishodit, a ishodnyj tekst realizacii,
 t.e. funkcii slist_base, voobshche ne dolzhen byt' dostupen pol'zovatelyu.
 |to mozhet byt' sushchestvenno v kommercheskom ispol'zovanii sluzhebnyh
 programm dlya spiskov. Krome togo, dostigaetsya razdelenie mezhdu
 interfejsom i ego realizaciej, i stanovitsya vozmozhnoj smena realizacii
 bez peretranslyacii programm pol'zovatelya. Nakonec, prostoj spisok
 s prinuditel'noj svyaz'yu blizok po ispol'zovaniyu pamyati i vremeni
 k optimal'nomu resheniyu. Inymi slovami, takoj podhod blizok k
 optimal'nomu po vremeni, pamyati, upryatyvaniyu dannyh i kontrolyu
 tipov i v tozhe vremya on obespechivaet bol'shuyu gibkost' i kompaktnost'
 vyrazhenij.
       K sozhaleniyu, ob容kt mozhet popast' v Islist tol'ko, esli on
 yavlyaetsya proizvodnym ot slink. Znachit nel'zya imet' spisok Islist
 iz znachenij tipa int, nel'zya sostavit' spisok iz znachenij kakogo-to
 ranee opredelennogo tipa, ne yavlyayushchegosya proizvodnym ot slink.
 Krome togo, pridetsya postarat'sya, chtoby vklyuchit' ob容kt v dva spiska
 Islist ($$6.5.1).

        8.3.2 Spisok bez prinuditel'noj svyazi

 Posle "ekskursa" v voprosy postroeniya i ispol'zovaniya spiska s
 prinuditel'noj svyaz'yu perejdem k postroeniyu spiskov bez prinuditel'noj
 svyazi. |to znachit, chto elementy spiska ne obyazany soderzhat'
 dopolnitel'nuyu informaciyu, pomogayushchuyu v realizacii spisochnogo klassa.
 Poskol'ku my bol'she ne mozhem rasschityvat', chto ob容kt v spiske
 imeet pole svyazi, takuyu svyaz' nado predusmotret' v realizacii:

              template<class T>
              struct Tlink : public slink {
                 T info;
                 Tlink(const T& a) : info(a) { }
              };

 Klass Tlink<T> hranit kopiyu ob容ktov tipa T pomimo polya svyazi, kotoroe
 idet ot ego bazovogo klassa slink. Otmetim, chto ispol'zuetsya
 inicializator v vide info(a), a ne prisvaivanie info=a. |to
 sushchestvenno dlya effektivnosti operacii v sluchae tipov, imeyushchih
 netrivial'nye konstruktory kopirovaniya i operacii prisvaivaniya
 ($$7.11). Dlya takih tipov (naprimer, dlya String) opredeliv konstruktor
 kak

             Tlink(const T& a) { info = a; }

 my poluchim, chto budet stroit'sya standartnyj ob容kt String, a uzhe
 zatem emu budet prisvaivat'sya znachenie.
      Imeya klass, opredelyayushchij svyaz', i klass Islist, poluchit'
 opredelenie spiska bez prinuditel'noj svyazi sovsem prosto:

             template<class T>
             class Slist : private slist_base {
             public:
               void insert(const T& a)
                 { slist_base::insert(new Tlink<T>(a)); }
               void append(const T& a)
                 { slist_base::append(new Tlink<T>(a)); }
               T get();
               // ...
            };

            template<class T>
            T Slist<T>::get()
            {
              Tlink<T>* lnk = (Tlink<T>*) slist_base::get();
              T i = lnk->info;
              delete lnk;
              return i;
            }

 Rabotat' so spiskom Slist tak zhe prosto, kak i so spiskom Ilist.
 Razlichie v tom, chto mozhno vklyuchat' v Slist ob容kt, klass kotorogo ne
 yavlyaetsya proizvodnym ot slink, a takzhe mozhno vklyuchat' odin ob容kt
 v dva spiska:

           void f(int i)
           {
             Slist<int> lst1;
             Slist<int> lst2;

             lst1.insert(i);
             lst2.insert(i);
             // ...

             int i1 = lst1.get();
             int i2 = lst2.get();
             // ...
           }

 Odnako, spisok s prinuditel'noj svyaz'yu, naprimer Islist, pozvolyal
 sozdavat' sushchestvenno bolee effektivnuyu programmu i daval bolee
 kompaktnoe predstavlenie. Dejstvitel'no, pri kazhdom vklyuchenii
 ob容kta v spisok Slist nuzhno razmestit' ob容kt Tlink, a pri kazhdom
 udalenii ob容kta iz Slist nuzhno udalit' ob容kt Tlink, prichem
 kazhdyj raz kopiruetsya ob容kt tipa T. Kogda voznikaet takaya problema
 dopolnitel'nyh rashodov, mogut pomoch' dva priema. Vo-pervyh,
 Tlink yavlyaetsya pryamym kandidatom dlya razmeshcheniya s pomoshch'yu prakticheski
 optimal'noj funkcii razmeshcheniya special'nogo naznacheniya (sm. $$5.5.6).
 Togda dopolnitel'nye rashody pri vypolnenii programmy sokratyatsya
 do obychno priemlemogo urovnya. Vo-vtoryh, poleznym okazyvaetsya takoj
 priem, kogda ob容kty hranyatsya v "pervichnom" spiske, imeyushchim
 prinuditel'nuyu svyaz', a spiski bez prinuditel'noj svyazi ispol'zuyutsya
 tol'ko, kogda trebuetsya vklyuchenie ob容kta v neskol'ko spiskov:

            void f(name* p)
            {
              Islist<name> lst1;
              Slist<name*> lst2;

              lst1.insert(p);   // svyaz' cherez ob容kt `*p'
              lst2.insert(p);   // dlya hraneniya `p' ispol'zuetsya
                                // otdel'nyj ob容kt tipa spisok
              // ...
            }

 Konechno, podobnye tryuki mozhno delat' tol'ko v otdel'nom komponente
 programmy, chtoby ne dopustit' putanicy spisochnyh tipov v
 interfejsah razlichnyh komponent. No eto imenno tot sluchaj, kogda
 radi effektivnosti i kompaktnosti programmy na nih stoit idti.
     Poskol'ku konstruktor Slist kopiruet parametr dlya insert(),
 spisok Slist prigoden tol'ko dlya takih nebol'shih ob容ktov, kak
 celye, kompleksnye chisla ili ukazateli.  Esli dlya ob容ktov kopirovanie
 slishkom nakladno ili nepriemlemo po smyslovym prichinam, obychno
 vyhod byvaet v tom, chtoby vmesto ob容ktov pomeshchat' v spisok
 ukazateli na nih. |to sdelano v privedennoj vyshe funkcii f() dlya
 lst2.
     Otmetim, chto raz parametr dlya Slist::insert() kopiruetsya, peredacha
 ob容kta proizvodnogo klassa funkcii insert(), ozhidayushchej ob容kt
 bazovogo klassa, ne projdet gladko, kak mozhno bylo (po naivnosti)
 podumat':

           class smiley : public circle { /* ... */ };

           void g1(Slist<circle>& olist, const smiley& grin)
           {
             olist.insert(grin);  // lovushka!
           }

 V spisok budet vklyuchena tol'ko chast' circle ob容kta tipa smiley.
 Otmetim, chto eta nepriyatnost' budet obnaruzhena translyatorom v tom
 sluchae, kotoryj mozhno schitat' naibolee veroyatnym. Tak, esli by
 rassmatrivaemyj bazovyj klass byl abstraktnym, translyator zapretil
 by "urezanie" ob容kta proizvodnogo klassa:

          void g2(Slist<shape>& olist, const circle& c)
          {
            olist.insert(c);  // oshibka: popytka sozdat' ob容kt
                              // abstraktnogo klassa
          }

 CHtoby izbezhat' "urezaniya" ob容kta nuzhno ispol'zovat' ukazateli:

         void g3(Slist<shape*>& plist, const smiley& grin)
         {
           olist.insert(&grin);  // prekrasno
         }

 Ne nuzhno ispol'zovat' parametr-ssylku dlya shablonnogo klassa:

         void g4(Slist<shape&>& rlist, const smiley& grin)
         {
           rlist.insert(grin); // oshibka: budet sozdany komandy,
                               // soderzhashchie ssylku na ssylku (shape&&)
         }

 Pri generacii po shablonu tipa ssylki, ispol'zuemye podobnym obrazom,
 privedut oshibkam v tipah. Generaciya po shablonu tipa dlya funkcii

         Slist::insert(T&);

 privedet k poyavleniyu nedopustimoj funkcii

         Slist::insert(shape&&);

 Ssylka ne yavlyaetsya ob容ktom, poetomu nel'zya imet' ssylku na ssylku.
    Poskol'ku spisok ukazatelej yavlyaetsya poleznoj konstrukciej,
 imeet smysl dat' emu special'noe imya:

         template<class T>
         class Splist : private Slist<void*> {
         public:
           void insert(T* p) { Slist<void*>::insert(p); }
           void append(T* p) { Slist<void*>::append(p); }
           T* get() { return (T*) Slist<void*>::get(); }
        };

        class Isplist : private slist_base {
        public:
          void insert(T* p) { slist_base::insert(p); }
          void append(T* p) { slist_base::append(p); }
          T* get() { return (T*) slist_base::get(); }
       };

 |ti opredeleniya k tomu zhe uluchshayut kontrol' tipov i eshche bol'she
 sokrashchayut neobhodimost' dublirovat' funkcii.
    CHasto byvaet polezno, chtoby tip elementa, ukazyvaemyj v shablone
 tipa, sam byl shablonnym klassom. Naprimer, razrezhennuyu matricu,
 soderzhashchuyu daty, mozhno opredelit' tak:

       typedef Slist< Slist<date> > dates;

 Obratite vnimanie na nalichie probelov v etom opredelenii. Esli mezhdu
 pervoj i vtoroj uglovoj skobkoj > net probelov, vozniknet
 sintaksicheskaya oshibka, poskol'ku >> v opredelenii

       typedef Slist<Slist<date>> dates;

 budet traktovat'sya kak operaciya sdviga vpravo. Kak obychno, vvodimoe
 v typedef imya sluzhit sinonimom oboznachaemogo im tipa, a ne yavlyaetsya
 novym tipom. Konstrukciya typedef polezna dlya imenovaniya dlya
 dlinnyh imen shablonnyh klassov takzhe, kak ona polezna dlya lyubyh
 drugih dlinnyh imen tipov.
     Otmetim, chto parametr shablona tipa, kotoryj mozhet po raznomu
 ispol'zovat'sya v ego opredelenii, dolzhen vse ravno ukazyvat'sya sredi
 spiska parametrov shablona odin raz. Poetomu shablon tipa, v kotorom
 ispol'zuetsya ob容kt T i spisok elementov T, nado opredelyat' tak:

         template<class T> class mytemplate {
            T ob;
            Slist<T> slst;
            // ...
         };

 a vovse ne tak:

         template<class T, class Slist<t> > class mytemplate {
           T obj;
           Slist<T> slst;
           // ...
         };

 V $$8.6 i $$R.14.2 dany pravila, chto mozhet byt' parametrom shablona
 tipa.

        8.3.3 Realizaciya spiska

 Realizaciya funkcij slist_base ochevidna. Edinstvennaya trudnost'
 svyazana s obrabotkoj oshibok. Naprimer, chto delat' esli pol'zovatel'
 s pomoshch'yu funkcii get() pytaetsya vzyat' element iz pustogo spiska.
 Podobnye situacii razbirayutsya v funkcii obrabotki oshibok
 slist_handler(). Bolee razvityj metod, rasschitannyj na osobye
 situacii, budet obsuzhdat'sya v glave 9.
     Privedem polnoe opisanie klassa slist_base:

          class slist_base {
             slink* last;  // last->next yavlyaetsya nachalom spiska
          public:
             void insert(slink* a);  // dobavit' v nachalo spiska
             void append(slink* a);  // dobavit' v konec spiska
             slink* get();           // udalit' i vozvratit'
                                     // nachalo spiska
             void clear() { last = 0; }

             slist_base() { last = 0; }
             slist_base(slink* a) { last = a->next = a; }

             friend class slist_base_iter;
           };

 CHtoby uprostit' realizaciyu obeih funkcij insert i append, hranitsya
 ukazatel' na poslednij element zamknutogo spiska:

           void slist_base_insert(slink* a) // dobavit' v nachalo spiska
           {
             if (last)
                a->next = last->next;
             else
                last = a;
             last->next = a;
           }

 Zamet'te, chto last->next - pervyj element spiska.

           void slist_base::append(slink* a) // dobavit' v konec spiska
           {
             if (last) {
                a->next = last->next;
                last = last->next = a;
             }
             else
                last = a->next = a;
           }

          slist* slist_base::get() // udalit' i vozvratit' nachalo spiska
          {
            if (last == 0)
               slist_handler("nel'zya vzyat' iz pustogo spiska");
            slink* f = last->next;
            if (f== last)
               last = 0;
            else
               last->next = f->next;
            return f;
          }

 Vozmozhno bolee gibkoe reshenie, kogda slist_handler - ukazatel' na
 funkciyu, a ne sama funkciya. Togda vyzov

          slist_handler("nel'zya vzyat' iz pustogo spiska");

 budet zadavat'sya tak

          (*slist_handler)(" nel'zya vzyat' iz pustogo spiska");

 Kak my uzhe delali dlya funkcii new_handler ($$3.2.6), polezno
 zavesti funkciyu, kotoraya pomozhet pol'zovatelyu sozdavat' svoi
 obrabotchiki oshibok:

          typedef void (*PFV)(const c