
                  8

              

              
               -  

       ⮩   ⨥ 蠡 ⨯.    
      筮  ।  ॠ   
      䥪⨢ 믮 ணࠬ ,  ⪠뢠  ᪮
      ஫ ⨯, ⠪ ⥩ ,  ᯨ᪨  樠⨢
      ᨢ. ஬ ⮣, 蠡 ⨯  । ࠧ 
      楫 ᥬ⢠ ⨯ 饭 (᪨) 㭪樨, ਬ,
      ⠪,  sort (஢).  ⢥ ਬ 蠡 ⨯ 
       裡  㣨 ﬨ 몠 ਢ ᥬ⢮
      ᯨ ᮢ. ⮡  ᯮᮡ 祭 ணࠬ 
       ⥫쭮 ⥯ ᨬ ⥩, ਢ ᪮쪮
      ਠ⮢ 蠡 㭪樨 sort().   । ⮩
      蠡 ⨯  樠⨢ ᨢ  뢠  
       樮 ணࠬ,   짮.

   8.1 

     ᠬ   ᮢ  ⥩ ,
   .. ⠪ ,  ࠭ ꥪ - 㣨 ⨯.
   ᪨, ᨢ, 樠⨢ ᨢ  ⢠ -  
   ⥩ .   ᠭ   5  7 ।
    । ,  ⥩ ꥪ⮢ ⢥,
   ⭮ ⨯. ਬ,  $$5.3.2 । ⢮ 楫.
    ⥩   ⥬  ᢮⢮,  ⨯
   ᮤঠ   ꥪ⮢   ᮡ 祭 
   ᮧ⥫ ⥩,   짮⥫ ⭮ ⥩
    ⨯  ⢥. ⥫쭮, ⨯ ᮤঠ
   ꥪ⮢  ࠬ஬ ⥩୮ ,  ᮧ⥫ ⠪
    㤥 ।    ⨯-ࠬ.  
   ⭮ ⥩ (.. ꥪ ⥩୮ ) 짮⥫
   㤥 㪠뢠    ⨯ ᮤঠ   ꥪ⮢.
   ਬ஬ ⠪ ⥩୮   蠡 ⨯ Vector 
   $$1.4.3.
         ⮩  ᫥ ⮩ 蠡 ⨯ stack (⥪) 
    १  ⨥ 蠡 . ⥬ ᬠਢ
      ࠢ ਬ ᪮쪨 த⢥ 蠡
   ⨯  ᯨ᪠.  蠡 㭪樨  㫨 ࠢ,
      ࠬ஬ ⠪ 㭪権.   ਢ 蠡
   ⨯  樠⨢ ᨢ.

   8.2 ⮩ 蠡 ⨯

    ⨯    ᯮᮡ ஥ ⤥ ᮢ,
    ⮬,  ᠭ   ᯮᮡ ஥ 
   ⤥ ꥪ⮢.  । ⥪, ᮤঠ騩 
   ந쭮 ⨯:

              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; }
              };

      뢠 ஫ ᪨ 訡.  
   ⮣, ਬ    ࠢ.
       䨪 template<class T> 㪠뢠,  뢠 蠡
   ⨯  ࠬ஬ T, 騬 ⨯,    祭
   㤥 ᯮ짮  ᫥饬 ᠭ. ᫥ ⮣, 
   䨪 T 㪠  䨪,   ᯮ짮  
   㣮  ⨯.   T த   ᠭ,
   砢襣 䨪ᮬ template<class T>. ⬥⨬,   䨪 T
    ⨯,    易   . , 
    ᠭ ꥪ sc ⨯ T 뢠  char.
        蠡 ,   ᫥ ⨯, 祭 
   㣫 ᪮ <>,    (।塞 蠡
   ⨯),    ᯮ짮    . ਬ, 
   । ꥪ sc  stack<char>:

            stack<char> sc(100);   // ⥪ ᨬ

       ᫨   ᮡ   ,  stack<char>
    ⥭  । ⠪:

            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; }
            };

    㬠,  蠡 ⨯ -  ஥ ம।,
   稭饥 ࠢ , ⨯  ⥩ ,
   ਭ  ++. , 筮, 饭,   ⠪ 饭,
   ஥    ࠧ㬥.  ⭮,
   ਬ 蠡 ⨯  । - ।
   ᪮ প  ,  ᯮ  
   "" ᮢ.  ᫥ ⠪  㬠,   ਢ 
   ᮪饭 ணࠬ.
         筮   砫 ⫠  , ⠪,
   ਬ,  stack_char, ०, 祬 ந   ᭮ 蠡 ⨯
   stack<T>.  㣮 ஭,   蠡 ⨯ 
   ।⠢ ᥡ  ⢨  ⭮ ⨯, ਬ int 
   shape*, ०, 祬  ।⠢   ᥩ 魮.
         । 蠡  stack,  ᫥騬
   ࠧ ।  ᯮ짮 ࠧ ⥪:

              stack<shape*> ssp(200);  // ⥪ 㪠⥫  䨣
              stack<Point> sp(400);    // ⥪  Point

              void f(stack<complex>& sc)  // ࠬ ⨯ `뫪 
                                          // complex'
              {
                sc.push(complex(1,2));
                complex z = 2.5*sc.pop();

                stack<int>*p = 0;         // 㪠⥫  ⥪ 楫
                p = new stack<int>(800);  // ⥪ 楫 ࠧ頥
                                          //  ᢮ 
                for ( int i = 0; i<400; i++) {
                    p->push(i);
                    sp.push(Point(i,i+400));
                }

                // ...
             }

   ᪮  㭪樨-童  stack  ⠭,
     ⮬ ਬ ࠭ ᮧ 맮 㭪権 ⮫쪮 
   ࠧ饭  ᢮   ᢮.
        㭪樨  蠡 ⨯     ⠭, 蠡
    stack   ࠢ  ।  ⠪:


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

                 void push(T);
                 T pop();

                 int size() const;
              };

    ⮬ 砥 । 㭪樨-童 stack   
   -  㣮 ,    뫮  㭪権- 童
   , 蠡 ᮢ.   㭪樨 ⠪ 
   ࠬਧ ⨯, 㦠騬 ࠬ஬   蠡
   , ⮬ ।    蠡 ⨯ 
   㭪樨. ᫨  ந室  蠡 ,   
   :

              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];
              }

   ⬥⨬,   ।    stack<T> 筥
   <T>  ,  stack<T>::stack -  .
        ⥬ ணࠬ஢,    ணࠬ,
   ।⠢ ᨨ 蠡 㭪権   䠪᪮
   ࠬ 蠡 ⨯. ⮬  ਢ襣  ਬ
   ⥬ ணࠬ஢  ᮧ । ஢ 
   ᮢ stack<shape*>, stack<Point>  stack<int>, ஢ 
   stack<shape*>  stack<Point>, ᨨ 㭪権 push()  stack<complex>,
   stack<int>  stack<Point>   㭪樨 pop()  stack<complex>.
    ᮧ 㭪樨  ᮢ襭 묨 㭪ﬨ-童,
   ਬ:

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

    ⫨稥  筮 㭪樨-童 ⮫쪮  ଥ  .
   筮 ⠪ ,   ணࠬ   ⮫쪮  ।
   㭪樨-童 ,  ⮫쪮  । 蠡
   ⨯  㭪樨-童 蠡 . ᫨ ॡ ।
   㭪樨-童 蠡   ⭮ ⨯,   ⥬
   ணࠬ஢  蠡 ⨯  ⮩ 㭪樨-童  ᮧ
   㦭  㭪樨.  饬 砥 ⥬ ணࠬ஢
    뢠  㪠  ணࠬ,  
    㦭 蠡 ⨯.
         ⠢ । 蠡 ⨯ ⠪ ࠧ, ⮡
    ᨬ    뫠 쭮.   ⮬,
   蠡 ⨯ 㤥 ᯮ짮  ஦ 㭪権  ᮢ
    ᭮ ࠭ ⭮ ⨯    ⥪.
   ࠪ᪨ ,  ᫠ ᨬ  ⥪ 
     ஡  ⫠ ணࠬ 짮⥫, ,
   ⭥ ᥣ,   ᮧ⥫ 蠡 ⨯.  ᮢ ,
   ᪮쪮  , ᯮ짮  , ᫥
   ⭮ ᮡ 쥧  ࠧࠡ⪥ 蠡 ⨯.

   8.3  ⨯  ᯨ᪠

    ࠪ⨪  ࠧࠡ⪥ , 㦠饣 樥 ꥪ⮢,
    室 뢠 ⭮襭 ᯮ  ॠ樨
   ᮢ, ࠢ   室 ।  
   ᮤন 樨.  뢠 ⠪,  ᪮쪮 த⢥
   ᮢ ࠧࠡ뢠 ᮢ⭮ ($$12.2).  ⢥ ਬ 
   । ᥬ⢮ ᮢ, ।⠢ 吝 ᯨ᪨ 
   蠡 ⨯  .

   8.3.1 ᮪  ਭ㤨⥫쭮 

   砫 । ⮩ ᯨ᮪,  ஬ ।, 
     ᨬ  ᯨ᮪ ꥪ   裡. ⮬ 
   ᯨ᮪ 㤥 ᯮ짮  ந⥫ ਠ  ᮧ
     ᯨ᪮,   ꥪ  易   裡.
   ࢠ  ᠭ ᮢ 㤥 ਢ ⮫쪮  ,
    ॠ 㤥   ᫥饬 ࠧ.    ⥬,
   ⮡  ஥஢ ᮢ  ⥬﫨 ⠫ﬨ 
   ॠ樨.
      筥  ⨯ slink, ।饣  裡  吝 ᯨ᪥:

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

     । ,   ᮤঠ ꥪ
   , ந  slink, :

              class slist_base {
                 // ...
              public:
                 int insert(slink*); //   砫 ᯨ᪠
                 int append(slink*); //    ᯨ᪠
                 slink* get();       // 㤠   砫 ᯨ᪠
                 // ...
              };

       ᯨ᪮  ਭ㤨⥫쭮 , ᪮
     ᯮ짮 ⮫쪮  ⮬ 砥,    
    slink, ஥ ᯮ  㪠⥫  slist_base.
     slist_base ( 吝 ᯨ᮪) ,  
    㤥 ᯮ짮    吝 ᯨ
   ᮢ.  筮,  ࠧࠡ⪥ ᥬ⢠ த⢥ ᮢ
    ,  롨   ࠧ 童 ᥬ⢠.
   ᪮  ᮢ   ॣ㦠,   
     㭪権,  㧤 ࠧ  ॣ㧪  
   .
         slist_base  ᯮ짮 ⠪:

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

    ᪮  slink   ᮤঠ  ଠ樨
    裡,  ਬ  ᫨誮 ᥭ. ⮡ ᯮ짮
   slist_base,  । , ந  slink, .
   ਬ,  ࠭ ᯮ 㧫 ॢ ணࠬ name
   (),  室 뢠  ᯨ᮪:

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

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

     ଠ쭮,  ᪮ ।  slist_base
    १  slink, 室 ᯮ짮  ਢ
   ⨯  ८ࠧ 祭 ⨯ slink*, 頥
   㭪樥 slist_base::get(),  name*.  ᨢ.  让
   ணࠬ,  ன  ᯨ᪮  ந  slink ᮢ,
     ⮬  ॢ 訡.  ਣ   
   ⨯   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(); }
               // ...
             };

   ਢ  㭪樨 Islist::get() ᮢ襭 ࠢ  ,
   ᪮   Islist ࠭,   ꥪ  ᯨ᪥
   ⢨⥫쭮  ⨯ T  ⨯ ந  T . ⬥⨬,
    slist_base    ᮬ Islist.   ⨬,
   ⮡ 짮⥫ 砩 ⮫   ⠫
   ॠ樨.
          Islist (intrusive  singly linked list) 砥
   吝 ᯨ᮪  ਭ㤨⥫쭮 .  蠡 ⨯
    ᯮ짮 ⠪:

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

   ⪨ ४⭮ ᯮ짮 㤥   ⠤
   ࠭樨:

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

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

   㦭 ⬥ ᪮쪮  ⮢ ⭮⥫쭮 襣 ਬ.
   -, 襭   ᫥ ⨯ (ॣࠤ ਢ
   訡 ⠢  祭 ࠭祭  ணࠬ,  ,
    㭪 㯠  Islist). -,  ⨯
   ⨣  㢥祭  ६  , ᪮
   㭪樨 㯠  Islist ਢ  ॠ ⠭.
   -, ᪮   ࠡ  ᯨ᪮  
   ॠ樨  slist_base (   ।⠢), 
   㡫஢ 㭪権  ந室,  室 ⥪ ॠ樨,
   .. 㭪樨 slist_base,     㯥 짮⥫.
      ⢥  ᪮ ᯮ짮 㦥
   ணࠬ  ᯨ᪮. ஬ ⮣, ⨣ ࠧ 
   䥩ᮬ   ॠ樥,  ⠭  ᬥ ॠ樨
    ࠭樨 ணࠬ 짮⥫. , ⮩ ᯨ᮪
    ਭ㤨⥫쭮    ᯮ짮   ६
    ⨬쭮 襭. 묨 ᫮, ⠪ 室  
   ⨬쭮  ६, , 뢠   ஫
   ⨯   ⮦ ६  ᯥ稢    ⭮
   ࠦ.
          ᮦ, ꥪ    Islist ⮫쪮, ᫨ 
    ந  slink.    ᯨ᮪ Islist
    祭 ⨯ int,  ⠢ ᯨ᮪  祭 -
   ࠭ । ⨯,  饣 ந  slink.
   ஬ ⮣, ਤ , ⮡  ꥪ   ᯨ᪠
   Islist ($$6.5.1).

   8.3.2 ᮪  ਭ㤨⥫쭮 裡

   ᫥ ""   ஥  ᯮ짮 ᯨ᪠ 
   ਭ㤨⥫쭮  ३  ஥ ᯨ᪮  ਭ㤨⥫쭮
   裡.  ,   ᯨ᪠  易 ᮤঠ
   ⥫ ଠ,   ॠ樨 ᯨ筮 .
   ᪮     뢠,  ꥪ  ᯨ᪥
     裡, ⠪   ।ᬮ  ॠ樨:

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

    Tlink<T> ࠭  ꥪ⮢ ⨯ T   裡, ஥
        slink. ⬥⨬,  ᯮ
   樠   info(a),   ᢠ info=a. 
   ⢥  䥪⨢ 樨  砥 ⨯, 
   ਢ  ஢  樨 ᢠ
   ($$7.11).  ⠪ ⨯ (ਬ,  String) । 
   

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

    稬,  㤥 ந ⠭ ꥪ String,  㦥
   ⥬  㤥 ᢠ 祭.
         , ।騩 ,   Islist, 
   । ᯨ᪠  ਭ㤨⥫쭮 裡 ᮢᥬ :

               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;
              }

     ᯨ᪮ Slist ⠪  ,    ᯨ᪮ Ilist.
   稥  ⮬,     Slist ꥪ,  ண 
    ந  slink,  ⠪    ꥪ
     ᯨ᪠:

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

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

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

   , ᯨ᮪  ਭ㤨⥫쭮 , ਬ Islist, 
   ᮧ ⢥  䥪⨢ ணࠬ   
   ⭮ ।⠢. ⢨⥫쭮,   祭
   ꥪ  ᯨ᮪ Slist 㦭 ࠧ ꥪ Tlink,   
   㤠 ꥪ  Slist 㦭 㤠 ꥪ Tlink, 祬
    ࠧ  ꥪ ⨯ T.   ⠪ ஡
   ⥫ 室,    ਥ. -,
   Tlink   ⮬  ࠧ饭   ࠪ᪨
   ⨬쭮 㭪樨 ࠧ饭 ᯥ樠쭮 祭 (. $$5.5.6).
    ⥫ 室  믮 ணࠬ ᮪
    筮 ਥ ஢. -,  뢠 ⠪
   ਥ,  ꥪ ࠭  "ࢨ筮" ᯨ᪥, 騬
   ਭ㤨⥫ ,  ᯨ᪨  ਭ㤨⥫쭮 裡 ᯮ
   ⮫쪮,  ॡ 祭 ꥪ  ᪮쪮 ᯨ᪮:

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

                lst1.insert(p);   //  १ ꥪ `*p'
                lst2.insert(p);   //  ࠭ `p' ᯮ
                                  // ⤥ ꥪ ⨯ ᯨ᮪
                // ...
              }

   筮,     ⮫쪮  ⤥쭮 
   ணࠬ, ⮡   ⠭ ᯨ ⨯ 
   䥩 ࠧ .     砩, 
   ࠤ 䥪⨢  ⭮ ணࠬ   ⮨ .
       ᪮  Slist  ࠬ  insert(),
   ᯨ᮪ Slist ਣ ⮫쪮  ⠪  ꥪ⮢, 
   楫,  ᫠  㪠⥫.  ᫨  ꥪ⮢ ஢
   ᫨誮   ਥ  ᫮ 稭, 筮
   室 뢠  ⮬, ⮡  ꥪ⮢   ᯨ᮪
   㪠⥫  .  ᤥ  ਢ  㭪樨 f() 
   lst2.
       ⬥⨬,  ࠧ ࠬ  Slist::insert() , ।
   ꥪ ந  㭪樨 insert(), 饩 ꥪ
    ,  ன ,   뫮 ( )
   㬠:

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

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

    ᯨ᮪ 㤥 祭 ⮫쪮  circle ꥪ ⨯ smiley.
   ⬥⨬,   ⭮ 㤥 㦥 ࠭஬  ⮬
   砥,     . , ᫨ 
   ᬠਢ    ࠪ, ࠭ ⨫
    "१" ꥪ ந :

            void g2(Slist<shape>& olist, const circle& c)
            {
              olist.insert(c);  // 訡: ⪠ ᮧ ꥪ
                                // ࠪ⭮ 
            }

   ⮡  "१" ꥪ 㦭 ᯮ짮 㪠⥫:

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

    㦭 ᯮ짮 ࠬ-뫪  蠡 :

           void g4(Slist<shape&>& rlist, const smiley& grin)
           {
             rlist.insert(grin); // 訡: 㤥 ᮧ ,
                                 // ᮤঠ騥 뫪  뫪 (shape&&)
           }

    樨  蠡 ⨯ 뫪, ᯮ㥬  ࠧ,
   ਢ 訡  ⨯.   蠡 ⨯  㭪樨

           Slist::insert(T&);

   ਢ   ⨬ 㭪樨

           Slist::insert(shape&&);

   뫪   ꥪ⮬, ⮬   뫪  뫪.
      ᪮ ᯨ᮪ 㪠⥫   樥,
       ᯥ樠쭮 :

           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(); }
         };

    ।  ⮬   ஫ ⨯   
   ᮪ 室 㡫஢ 㭪樨.
       뢠 , ⮡ ⨯ , 㪠뢠  蠡
   ⨯, ᠬ  蠡 ᮬ. ਬ, ࠧ० ,
   ᮤঠ ,  । ⠪:

         typedef Slist< Slist<date> > dates;

      稥 ஡  ⮬ ।. ᫨ 
   ࢮ  ன 㣫 ᪮ >  ஡, 
   ᨭ⠪᪠ 訡, ᪮ >>  ।

         typedef Slist<Slist<date>> dates;

   㤥 ࠪ⮢   ᤢ ࠢ.  筮, 
    typedef  㦨 ᨭ 砥  ⨯,   
    ⨯.  typedef    
     蠡 ᮢ ⠪,     
   㣨   ⨯.
       ⬥⨬,  ࠬ 蠡 ⨯,    ࠧ
   ᯮ짮   ।,   ࠢ 㪠뢠 ।
   ᯨ᪠ ࠬ஢ 蠡  ࠧ. ⮬ 蠡 ⨯,  ஬
   ᯮ ꥪ T  ᯨ᮪ ⮢ T,  । ⠪:

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

      ⠪:

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

    $$8.6  $$R.14.2  ࠢ,    ࠬ஬ 蠡
   ⨯.

   8.3.3  ᯨ᪠

    㭪権 slist_base 祢. ⢥ 㤭
   易  ࠡ⪮ 訡. ਬ,   ᫨ 짮⥫
     㭪樨 get() ⠥    ⮣ ᯨ᪠.
    樨 ࠧ  㭪樨 ࠡ⪨ 訡
   slist_handler().  ࠧ ⮤, ⠭  ᮡ
   樨, 㤥 㦤   9.
       ਢ  ᠭ  slist_base:

            class slist_base {
               slink* last;  // last->next  砫 ᯨ᪠
            public:
               void insert(slink* a);  //   砫 ᯨ᪠
               void append(slink* a);  //    ᯨ᪠
               slink* get();           // 㤠  
                                       // 砫 ᯨ᪠
               void clear() { last = 0; }

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

               friend class slist_base_iter;
             };

   ⮡  ॠ  㭪権 insert  append, ࠭
   㪠⥫  ᫥  ⮣ ᯨ᪠:

             void slist_base_insert(slink* a) //   砫 ᯨ᪠
             {
               if (last)
                  a->next = last->next;
               else
                  last = a;
               last->next = a;
             }

   ,  last->next -   ᯨ᪠.

             void slist_base::append(slink* a) //    ᯨ᪠
             {
               if (last) {
                  a->next = last->next;
                  last = last->next = a;
               }
               else
                  last = a->next = a;
             }

            slist* slist_base::get() // 㤠   砫 ᯨ᪠
            {
              if (last == 0)
                 slist_handler("   ⮣ ᯨ᪠");
              slink* f = last->next;
              if (f== last)
                 last = 0;
              else
                 last->next = f->next;
              return f;
            }

      襭,  slist_handler - 㪠⥫ 
   㭪,   ᠬ 㭪.  맮

            slist_handler("   ⮣ ᯨ᪠");

   㤥  ⠪

            (*slist_handler)("    ⮣ ᯨ᪠");

     㦥   㭪樨 new_handler ($$3.2.6), 
    㭪,   짮⥫ ᮧ ᢮
   ࠡ稪 訡:

            typedef void (*PFV)(const char*);

            PFV set_slist_handler(PFV a)
            {
              PFV old = slist_handler;
              slist_handler = a;
              return old;
            }

            PFV slist_handler = &default_slist_handler;

   ᮡ 樨,  㦤   9,  ⮫쪮 
   ୠ⨢ ᯮᮡ ࠡ⪨ 訡,   ᯮᮡ ॠ樨
   slist_handler.

   8.3.4 

     slist_base  㭪権  ᬮ ᯨ᪠,  ⮫쪮
   ⠢  㤠 . ,   뢠  
    slist_base_iter, ⮬  । 室騩 
   ᯨ᪠ .    ,   ⮬ ⨫, 
      $$7.8:

             class slist_base_iter {
               slink* ce;      // ⥪騩 
               slist_base* cs; // ⥪騩 ᯨ᮪
             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()()
               // 頥 0,   砥
             {
               slink* ret = ce ? (ce=ce->next) : 0;
               if (ce == cs->last) ce = 0;
               return ret;
             }

   室   ।,     Slist 
   Islist. 砫  । 㦥⢥   ஢
    ᮮ⢥騬 ⥩ ᠬ:

              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>;
                // ...
              };

    ,   ஢   ।
    蠡 .  ᯮᮡ ।  ᫮ 
   ᨬ 蠡 ⨯.
          । ᠬ :

              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;
              }

   ,    ᯮ짮 ਥ,    
    ந ᥬ⢮ ந ᮢ ( , 蠡
   ).  ᯮ㥬 ᫥, ⮡ ࠧ 魮 ᮢ
     㦭 㡫஢ 㭪権. 㤭 ८業
   ६  㡫஢ 㭪権  ॠ樨 ⠪ 
     ᯮ㥬 ᮢ  ᯨ᪨  . 짮
   ⨬ ࠬ  ⠪:

              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 << "" << *p << '\n';
                   }
                }
              }

        ᪮쪮 ᯮᮡ    ⥩୮ .
   ࠡ稪 ணࠬ  ⥪     
    ਤন . ਢ ᯮᮡ   ᫨誮
   .   ⮬ ਠ  뫮  २
   operator()()  next().   ਠ । 
    ⥩ ᮬ  ஬  , ⠪  
    믮  ࠡ 砨,   
    㤠  ⥩.    㣨 ᯮᮡ 
   ஢ 뫨  , ᫨   ᥫ  㭪樨
   짮⥫,  ன  㪠⥫    ⥩.
    ࠢ, ⥩    ॠ ⨥ "⠭
     砫"  ⨥ "⥪饣 ".
       ᫨ ⨥ ⥪饣  ।⠢  ,  ᠬ
   ⥩,  ந室  ਭ㤨⥫쭮 浪  ⭮襭
    ⥩ 筮 ⮬,   裡 ਭ㤨⥫쭮 ࠭
    ꥪ  ⥩.  㤭 ६  
   樨   ⥩,  室    ६  ⠪
   ࣠樨 樨   ⨬. ਢ ਬ:

                 class slist_base {
                   // ...
                   slink* last;  // last->next  ᯨ᪠
                   slink* current;  // ⥪騩 
                 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();
                 };

    ⮬,   楫 䥪⨢  ⭮ ணࠬ
    ᯮ짮   ꥪ  ᯨ᮪  ਭ㤨⥫쭮
   , ⠪  ᯨ᮪  ,   ⥩ 
   ᯮ짮 ਭ㤨⥫  ਭ㤨⥫ :

                void f(Islist<name>& ilst)
                //   -㡫⮢
                {
                  list_iter<name> slow(ilst);  // ᯮ 
                  name* p;
                  while (p = slow()) {
                   ilst.set_current(p); // 뢠  ⥪騩 
                   name* q;
                   while (q = ilst.next())
                      if (strcmp(p->string,q->string) == 0)
                         cout << "㡫" << p << '\n';
                   }
                }

      ஢   $$8.8.

   8.4  ⨯  㭪権

   ᯮ짮 蠡 ᮢ 砥 稥 蠡
   㭪権-童.  ⮣,  ।  蠡
   㭪樨, .. 蠡 ⨯  㭪権,   童 .
    ⨯  㭪権 ஦ ᥬ⢮ 㭪権 筮 ⠪,
    蠡 ⨯   ஦ ᥬ⢮ ᮢ.  
    㤨  ᫥⥫쭮 ਬ஢,   ਢ
   ਠ 㭪樨 ஢ sort().   ਠ⮢  ᫥
   ࠧ 㤥 ஢ 騩 ⮤.
          筮  ।稬  ࣠樨 ணࠬ,   
   ࠧࠡ⪥  ⬠, ⮬ ᯮ짮 㤥 ਢ
   .  ਠ 蠡 ⨯  sort() 㦭  ⮣,
   ⮡   몠   ਥ ணࠬ஢.
   ਠ  㯮冷祭  ᮮ⢥⢨  ⥬, ᪮쪮  .
   ஬ ⮣,  㤨  ࠤ樮 ਠ  蠡 ⨯,
    ⭮, । 㪠⥫  㭪, ந ࠢ.

   8.4.1 ⮩ 蠡 ⨯  쭮 㭪樨

   筥  ⥩襣 蠡  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);
          }

     㭪 sort() 㤥 뢠 । 䠪᪨
   ࠬ஬. ணࠬ  । 蠡 ⨯  㭪樨,
     ⥬ ணࠬ஢ ᯥ ᮧ ࠢ
   ਠ⮢ 㭪樨  蠡  맮 ᮮ⢥饣 ਠ.
   ਬ, ⮩ 蠡  ⬮ 쪮 ஢ 
   । ⠪:

          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 (v[j] < v[j-1]) {  // 塞 ⠬ v[j]  v[j-1]
                      T temp = v[j];
                      v[j] = v[j-1];
                      v[j-1] = temp;
                   }
             }

   㥬 ࠢ  ।  㭪樥 ஢  ⥬ 
   ⬮  $$4.6.9. ⢥ ⫨稥 ⮣ ਠ  ⮬,
     室 ଠ ।  ⢥ ࠬ
   v. ᪮ ⨯ 㥬 ⮢ ⥭ ( ⨯ 䠪᪮
   ࠬ,  ।⢥ ࠢ ,   ।
   㪠⥫  ந ࠢ 㭪. ஬ ⮣,  㦤
     樥 sizeof.  襭   ᨢ
     ⮬    䥪⨢, 祬 筮.    ⠫
    㤭.   ⨯  <  ।,  
   㣨, ਬ char*,  । ⨢ ⮬, 
   ॡ  ਢ । 蠡 㭪樨. (⢨⥫쭮,
    㦭 ࠢ  㪠⥫  ப,  ᠬ ப).
    ࢮ 砥 ⪠ ᮧ ਠ sort()  ⠪ ⨯
    㤠祩 (   ᫥ ) ,   ஬
    㭪, ந  १.
      ⮡ ࠢ쭮 ஢   ⮢ char*  
     ᠬ⥫쭮 室饥 । 㭪樨
   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) {
                     // 塞 ⠬ v[j]  v[j-1]
                        char* temp = v[j];
                        v[j] = v[j-1];
                        v[j-1] = temp;
                     }
           }

   ᪮  ஢  㪠⥫  ப 짮⥫ 
   ᢮ ᮡ । 㭪樨 sort(),   㤥 ᯮ짮,
    ᮧ   ।  蠡  ࠬ஬ ⨯
   Vector<char*>&  㦭.    ᮡ  
   "" ⨯ ᢮ । 蠡 㭪樨  業
   ⢮   ணࠬ஢     ।⢮
    ணࠬ  ⨬ ࠪ⨪.

   8.4.2 ந     樨

    ।饬 ࠧ 㭪 ࠢ 뫠 "஥"  ⥫
   sort() ( ᯮ짮  <).  㣮 襭,
     ।⠢ ᠬ 蠡  Vector. , ⠪
   襭   ⮫쪮  ᫮,   ⨯ ⮢
    ᫥ ⨥ ࠢ. 筮  ⠪ 樨
   㭪 sort() । ⮫쪮  ஢,   ।
    < :

             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])) {
                       // 塞 ⠬ v[j]  v[j-1]
                          T temp = v[j];
                          v[j] = v[j-1];
                          v[j-1] = temp;
                       }
            }

    SortableVector (㥬 )  । ⠪:

           template<class T> class SortableVector
              : public Vector<T>, public Comparator<T> {
           public:
               SortableVector(int s) : Vector<T>(s) { }
           };

   ⮡  ।     । 蠡
    Comparator (ࠢ⥫):

          template<class T> class Comparator {
          public:
             inline static lessthan(T& a, T& b)  // 㭪 ""
                { return strcmp(a,b)<0; }
             // ...
         };

   ⮡ ࠭  䥪,   襬 砥  < 
     १  ⨯ char*,  । ᯥ樠 ਠ
    ࠢ⥫:

         class Comparator<char*> {
         public:
           inline static lessthan(const char* a, const char* b)
           // 㭪 ""
              { return strcmp(a,b)<0; }
           // ...
        };

   ᠭ ᯥ樠쭮 ਠ 蠡   char* 
    ⮬,   ।饬 ࠧ  । ᯥ樠
   ਠ 蠡 㭪樨  ⮩  楫. ⮡ ᠭ ᯥ樠쭮
   ਠ 蠡  ࠡ⠫, ࠭  㦨
     ᯮ짮.  㤥 ᯮ짮 ᮧ 
   蠡 . ᪮     筮 
   ।  ணࠬ, ᯮ짮  ᯥ樠 ਠ ,
    ਠ, ᮧ  蠡, 㤥 訡.
      ᪮   㦥 ᯥ樠 ਠ  Comparator 
   char*, ᯥ樠 ਠ  SortableVector  char* 
   㦥,  , , ஡ ஢:

           void f(SortableVector<int>& vi,
                  SortableVector<String>& vc,
                  SortableVector<int>& vi2,
                  SortableVector<char*>& vs)
           {
             sort(vi);
             sort(vc);
             sort(vi2);
             sort(vs);
           }

          ஢   祭 , ,  ࠩ
   , SortableVector  ந  Vector.  ᫨
    㭪樨  㦭 ஢,         
   SortableVector,  ⠬,  㦭, ࠡ⠥  ८ࠧ
   뫪  ந   뫪  騩  . 
    ந  Vector  Comparator  SortableVector
   ( ⮣, ⮡  㭪樨  , ந  
    Vector)  ⮬,   Comparator 㦥 訢 
   ।騬 ਬ.  室 ⨯祭  ᮧ 
   ⥪.  Comparator ⢥   ⥪,
   ᪮    㪠 ࠧ ॡ  
   ࠢ  ࠧ ⨯.


   8.4.3 । 権  ࠬ஢ 㭪権

      㭪 ࠢ   ⨯
   Vector,  ।   ன ࠬ 㭪樨 sort().
    ࠬ  ꥪ⮬ ,  ஬ ।
   ॠ 樨 ࠢ:

           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])) {
                     // 塞 ⠬ v[j]  v[j-1]
                        T temp = v[j];
                        v[j] = v[j-1];
                        v[j-1] = temp;
                     }
           }

    ਠ  ᬠਢ  饭 ࠤ樮 ਥ,
     ࠢ ।  㪠⥫  㭪.
   ᯮ짮 ⨬  ⠪:

           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*>&);
           }

   ⬥⨬,  祭  蠡  Comparator  ࠬ
   ࠭,  㭪 lessthan 㤥 ॠ뢠 ⠭.
    ⭮,  , ᫨  蠡 㭪樨 ᯮ
   ᪮쪮 㭪権,     ࠢ,  ᮡ 
   ,   㭪樨   ࠭  ⮬  ꥪ
   .

   8.4.4  । 権

    ਬ  ।饣 ࠧ ꥪ Comparator  ᠬ 
     ᯮ짮  ᫥.   "⢥"
   ࠬ, 㦭  ࠢ쭮 ஫ ⨯.  ⠪
   ࠬ஢ 筮 騩   ਥ,    ᫨誮
   ᨢ. , ᫨ ꥪ ᯮ ⮫쪮  ।
   樨 (  뫮  襬 砥), ..  뢠 㭪樨
    ᯮ  祭,   ꥪ,    ⮣
   ।  :

          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])) {
                    // 塞 ⠬ v[j]  v[j-1]
                       T temp = v[j];
                       v[j] = v[j-1];
                       v[j-1] = temp;
                    }
         }

    १  室  ࢮ砫쭮 ਠ ᯮ짮
   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*>&);
        }

   ᭮ २⢮ ⮣ ਠ,    ।, 
   ࠢ  室 ਠ⮬  ⮬,   ணࠬ, 
   ᮡ⢥ ஢, ⤥  ⥩,   室
   ⠪ 樨, ࠡ騥  ⠬, , ਬ lessthan.
   室  ࠧ   ⮬ ணࠬ, 
   ᮡ   ࠧ ।⠢  ஥஢
   ⥪.  ᮧ⥫ ⥪    ⨯ ࠬ஢
   蠡,  짮⥫   (   ) ᯥ䨪
   ᯮ㥬  蠡 ⬮.  ⭮, ᫨   㭪樨
   sort() ᯮ짮  ᫮, ⨬஢  ⠭
    ᪮ ਬ , 짮⥫  祭 
   ६  ᢮ ᮡ   ⨯ char*,   뫮
   ᤥ  $$8.4.1.  ॠ  Comparator  ᯥ樠쭮
    char* ਢ쭠   ᯮ짮   㣨 .

   8.4.5  権   ࠬ஢ 蠡 

    樨,   裡  蠡 㭪樥
   sort()  蠡 ᮬ Comparator ᮧ 㤭. 
            ६ ࠧ  
     . ஬ ⮣, ᪮   "஥"
    㭪 sort(),  ᯮ짮  㭪 
   ஢ ஢  ⨯, ᫨  ࠢ ⠭
    㣮 ⨯ (. ࠦ 3  $$8.9). ⨢ 㭪 sort()
    ,       ᮬ Comparator:

              template<class T, class Comp> class Sort {
              public:
                 static void sort(Vector<T>&);
              };

         ⨯ ,     , ᫨
   ᯮ짮 typedef  蠡 Comparator:

              template<class T> class Comparator {
              public:
                 typedef T T;  // । Comparator<T>::T
                 static int lessthan(T& a, T& b) {
                   return a < b;
                 }
                 // ...
              };

    ᯥ樠쭮 ਠ  㪠⥫  ப  ।
   룫廊 ⠪:

              class Comparator<char*> {
              public:
                typedef char* T;
                static int lessthan(T a, T b) {
                  return strcmp(a,b) < 0;
                }
                // ...
              };

   ᫥     ࠬ, 騩 ⨯ ,
     Sort:

              template<class T, class Comp> class Sort {
              public:
                 static void sort(Vector<T>&);
              };

     ᯮ짮 ஢ ⠪:

             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);
             }

    । 㭪 sort() ᫥騬 ࠧ:

             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;
                        }
             }

   ᫥ ਠ મ    ᮥ  
   ணࠬ ⤥  .  ਬ   
   , ᫨ ᯮ짮  ࠢ⥫ (Comp)  ⢥
   ⢥ ࠬ 蠡.  ⮬ 砥  । 
   Sort  㭪樨 Sort::sort() ⨯  㤥   Comp::T.

   8.5 襭 ॣ㧪  蠡 㭪樨

    ࠬࠬ 蠡 㭪樨  ਬ  ८ࠧ
   ⨯.  ⮣  室 ᮧ  ਠ
   㭪樨:

              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)
                // ...
              }

       ⨯ ࠬ஢ 㤥 ᮧ  蠡
   ᢮ 㭪 sqrt. ᫨ 짮⥫  祣- ,
   ਬ 맢 sqrt(double),  ࠬ int, 㦭
   ᯮ짮  ८ࠧ ⨯:

             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)
               // ...
             }

    ⮬ ਬ  蠡  ᮧ । ⮫쪮 
   sqrt(double)  sqrt(complex).
        㭪  ॣ㦠  ⮩, ⠪  蠡
   㭪樥 ⮣  . 襭 ॣ㧪  蠡, ⠪ 
    㭪権  묨  ந室   蠣:

     ࠢ ᫨誮 ண, ,  ᥩ   ᫠,
   ⮡ ࠧ ८ࠧ 뫮  㪠⥫, , ,
    㣨 ⠭ ८ࠧ.  筮,  ⠪
   ८ࠧ 㤥 ⢮ ஫ 筮.

        [1]  㭪   ᮯ⠢ ࠬ஢ ($$R.13.2);
            ᫨ ⠪ , 맢 .
        [2]  蠡 ⨯,  ஬  ᮧ 뢠
            㭪   ᮯ⠢ ࠬ஢; ᫨ ⠪ ,
            맢 .
        [3] ஡ ࠢ ࠧ襭   㭪権 ($$r13.2);
            ᫨ 㭪   ⨬ ࠢ, 맢 , 
            맮  訡.
     砥, ᫨  ࢮ 蠣    㭪樨,
   맮 ⠥    訡. ਬ:

            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);  // 訡: 
                                  // ᮧ max(int,char)
            }

   ᪮  樨 㭪樨  蠡  ਬ 
   ८ࠧ ⨯ (ࠢ [2]), ᫥ 맮  ⮬
   ਬ  ࠧ  max(a,int(c)).   ᤥ ᠬ
   짮⥫,  ᠢ 㭪 max(int,int).  㯠
    ᨫ ࠢ [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)
            }

   ணࠬ  㦭  । 㭪樨 max(int,int),
     㬮砭 㤥 ᮧ  蠡.
         । 蠡 max ⠪, ⮡ ࠡ⠫ ࢮ砫
   ਠ 襣 ਬ:

            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)
            }

   ,    ++ ࠢ  ஥ ⨯  権  
   ⠪,  ᯮ짮  蠡   ࠬࠬ
     ᮢᥬ . ,   ୮ 
   ⨯ १ 㭪樨   ࠬ (T1), ,  ࠩ
   ,   ਢ   १, ਬ 
   맮

            max(c,i);  // char max(char,int)

   ᫨  蠡  㭪樨, 
     ⢮ ࠬ஢  ࠧ묨 䬥᪨
   ⨯, ᯮ  ࠬ,   १  蠡 㤥
   ஦ ᫨誮 讥 ᫮ । ࠧ 㭪権.
    ࠧ㬭  ८ࠧ ⨯,  ᠢ 㭪
    㦭묨 ⨯.

   8.6 ࠬ 蠡 ⨯

   ࠬ 蠡 ⨯  易⥫쭮    ⨯
   (. $$R.14.2).   ⨯   ப, 
   㭪権  ࠦ-⠭.  뢠 㦭 
    ࠬ 楫:

            template<class T, int sz> class buffer {
               T v[sz];   //  ꥪ⮢ ந쭮 ⨯
               // ...
            };

            void f()
            {
              buffer<char,128> buf1;
              buffer<complex,20> buf2;
              // ...
            }

    ᤥ sz ࠬ஬ 蠡 buffer,    ꥪ⮢,  
   砥,  ࠧ    ⥭  ⠤
   ࠭樨, ⮡  ꥪ 뫮  ࠧ,  ᯮ
   ᢮ .  ⮬ ᢮ ⠪ 蠡  buffer
     ॠ樨 ⥩ ᮢ, ᪮  ᫥
   ࢮ⥯ 䠪஬, ।騬  䥪⨢, 
    ࠧ   ᢮ . ਬ, ᫨ 
   ॠ樨  string ⪨ ப ࠧ  ⥪,  
   ⢥ 먣  ணࠬ, ᪮  設⢥ 
   ࠪ᪨  ப 祭 ⪨.  ॠ樨 ⠪ ⨯ 
   ࠧ   ਣ 蠡 buffer.
        ࠬ 蠡 ⨯  㭪樨    ⨯
   㭪樨,   ﭨ ࠦ  ⮬,    
   ࠩ     ⨯ ଠ ࠬ஢ 㭪権,
   ᮧ  蠡.  㦭  ⮣, ⮡ 㭪樨  뫮
   롨  ᮧ, ᭮뢠 ⮫쪮   ࠬ:

            template<class T> void f1(T);     // ଠ쭮
            template<class T> void f2(T*);    // ଠ쭮
            template<class T> T f3(int);      // 訡
            template<int i> void f4(int[][i]);   // 訡
            template<int i> void f5(int = i);    // 訡
            template<class T, class C> void f6(T);  // 訡
            template<class T> void f7(const T&, complex);  // ଠ쭮
            template<class T> void f8(Vector< List<T> >);  // ଠ쭮

     訡 맢 ⥬,  ࠬ-⨯ 蠡  
     ଠ ࠬ 㭪権.
       ࠭祭   蠡 ⨯  ᮢ.   ⮬,
    ࠬ  ⠪ 蠡 㦭 㪠뢠 直 ࠧ, 
   뢠 ꥪ 蠡 .  㣮 ஭,  蠡
   ᮢ  :   ᮧ  蠡 ⨯ 
    묨?   蠡    
     , ᫨ ᮢ   蠡,  ᯮ㥬  
    ࠬ   祭 ( ⮬ 
   । typedef, ᫥ ࠦ-⠭  ..). ୥
    蠡 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;  // 訡: ᮮ⢥⢨ ⨯
             buf1 = buf3;  // ଠ쭮
             buf1 = buf4;  // 訡: ᮮ⢥⢨ ⨯
             // ...
           }

       ᫨  蠡 ⨯   ᯮ ࠬ, 騥
    ⨯,   権, 룫 ᫥:

          template<int i>
          class X { /* ... */ };

          void f(int a, int b)
          {
            X < a > b>;  //   : X<a> b  ⮬
                         // ⨬ ᥬ,  X< (a>b) >; ?
          }

    ਬ ᨭ⠪᪨ 訡祭, ᪮ ࢠ 㣫 ᪮
   > 蠥 ࠬ 蠡.  ⭮ 砥,  
    ࠬ 蠡, 騩 ࠦ " 祬",
   ᯮ ᪮: X< (a>b)>.

   8.7  ⨯  ந 

    㦥 ,  ⠭ ந ᮢ (᫥) 
   蠡 ⨯    ।⢮.  ⨯ ࠦ
   魮  ᥬ ⨯,  ᯮ   ࠬ,
      ࠦ 魮  ᥬ ।⠢ﬨ
   (ꥪ⠬)  뢠 䥩ᮬ.   
    ࠧ㬥,   .
         ᮧ   蠡 ⨯  ࠧ   
    ⭮襭 ᫥ ஬ ⢥ , 
     ⨯  ࠬ 蠡. ਬ:

            template<class T>
            class Vector { /* ... */ }

            Vector<int> v1;
            Vector<short> v2;
            Vector<int> v3;

    v1  v3  ⨯,  v2  ᮢ襭 㣮 ⨯.  ⮣
   䠪,  short  ८ࠧ  int,  ᫥,  
    ८ࠧ Vector<short>  Vector<int>:

           v2 = v3;  // ᮮ⢥⢨ ⨯

    ⮣  ᫥ , ᪮  ஥ ८ࠧ
   int[]  short[].
       ਬ:

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

           Vector<circle*> v4;
           Vector<shape*> v5;
           Vector<circle*> v6;

    v4  v6  ⨯,  v5  ᮢ襭 㣮 ⨯.  ⮣
   䠪,    ८ࠧ circle  shape 
   circle*  shape*,  ᫥,    ८ࠧ
   Vector<circle*>  Vector<shape*>  Vector<circle*>* 
   Vector<shape*>* :

           v5 = v6;  // ᮮ⢥⢨ ⨯

     ⮬,   饬 砥  (।⠢) ,
   ᮧ  蠡 ⨯, ⠪,     ।
   ⭮襭 ᫥. , ᮧ  蠡  
   ᮤঠ ꥪ ⨯,   蠡  ࠬ,   
   㪠⥫  . ஬ ⮣, 饭  ८ࠧ
   ਢ  襭 ஫ ⨯:

          void f(Vector<circle>* pc)
          {
            Vector<shape>* ps = pc;  // 訡: ᮮ⢥⢨ ⨯
            (*ps)[2] = new square;   // 㣫  㥬  ⭮
                                     // ⢥⨥ ( 뤥 
                                     // square,  ᯮ  circle
         }

       ਬ 蠡 Islist, Tlink, Slist, Splist, Islist_iter,
   Slist_iter   SortableVector  ,  蠡 ⨯ 
   㤮 ।⢮  ᮧ 楫 ᥬ ᮢ.  蠡
   ᮧ ⠪ ᥬ ⮫쪮   ந ᮢ
     ⮬⥫ ⨥,  , 騬  訡.
    㣮 ஭, ᫨ ⪠  ந ᮢ  ᯮ짮
   ⮫쪮 蠡,   ⢮  㭪権-童 蠡
   ᮢ, ⢮  ⥫쭮  蠡 ᮢ  
   ⢥  㭪樨, ᯮ騥 蠡 ⨯.

   8.7.1  ॠ樨   ࠬ஢ 蠡

    ⥩   室 뤥 . 
   뢠 室 (  㤮)  짮⥫ 
   롨  ᪮쪨 ਠ⮢ 뤥 ,  ⠪ 
     ᢮ ਠ.   ᤥ ᪮쪨 ᯮᮡ.
     ᯮᮡ ⮨  ⮬,  । 蠡 ⨯ 
   ᮧ  ,  䥩 ண 室 ᠭ
   ᮮ⢥饣 ⥩  , ந饣 뤥 
    ᯮᮡ, ᠭ  $$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;
                // ...
              }
              // ...
         };

    ⨯  室, ᪮  ᮧ ⥩ .
   ᫥  Container<T> 㦭, ⮡  Controlled_container
    뫮 ᯮ짮  ⥩ .  ⨯ 
   ࠬ஬ A   ᯮ짮 ࠧ 㭪樨 ࠧ饭:

        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;

    㭨ᠫ ᯮᮡ ।⠢ ந ᠬ
   ᮤঠ⥫ ଠ  ॠ樨.  ⥫묨 ⢠
    ⥬筮   ᯮ짮 㭪樨-⠭.
    ⮣ ᯮᮡ ࠪ 筮  . 祬, 
   筮, typedef   ᨭ  ᫨誮  
   ⨯:

         typedef
         Controlled_container<Personell_record,Persistent> pp_record;

         pp_record payroll;

   筮 蠡 ⨯  ᮧ ⠪   pp_record ᯮ
   ⮫쪮  ⮬ 砥,  塞 ଠ  ॠ樨
   筮 ⢥, ⮡     ந  
   ணࠬ஢. ਬ஬ ⠪ 蠡   騩
   (,   ⥪ ⠭) 蠡 
   Comparator ($$8.4.2),  ⠪ ਢ (, ⠭
     ⥪)  Allocator (  뤥 ).
   ⬥⨬,  ஥ ந ᮢ  ⠪ ਬ
     "᭮ ᯥ",  । 䥩 
   짮⥫ ( 襬 ਬ  Container).    "
   㫨", 騥 ⠫ ॠ樨.

   8.8 樠⨢ ᨢ

     㭨ᠫ ஥ ⨯ ᠬ ,  ᥩ
   ,  樠⨢ ᨢ.   뢠
   ⠡楩 (map),   ᫮६,   ࠭  祭.
      祭, 뢠 箬,   
    㣮, 뢠  祭. 樠⨢ ᨢ
    ।⠢  ᨢ,  ஬   易 
   楫:

             template<class K, class V> class Map {
                // ...
             public:
                V& operator[](const K&); //  V, ᮮ⢥饥 K
                                         //   뫪  
                // ...
             };

     ⨯ K 砥 祭 ⨯ V. ।, 
     ࠢ   権 ==  <, ⠪  ᨢ
    ࠭  㯮冷祭 . ⬥⨬,   Map
   ⫨砥  ⨯ assoc  $$7.8 ⥬,    㦭 
   " 祬",   㭪 ஢.
        ਢ  ணࠬ  ᫮,  ன ᯮ
   蠡 Map  ⨯ 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;
             }

    ᯮ㥬 ⨯ String  ⮣, ⮡  ᯮ  뤥
     ९ ,  祬 室 , ᯮ ⨯
   char*.  Mapiter 㦥  롮  浪  祭
   ᨢ.   Mapiter    ࠡ
    㪠⥫ﬨ. ᫨ 室 ⮪  

         It was new. It was singular. It was simple. It must succeed.

   ணࠬ 뤠

         4         It
         1         must
         1         new.
         1         simple.
         1         singular.
         1         succeed.
         3         was.

   筮, । 樠⨢ ᨢ   ᯮᮡ, ,
    । Map  易    ,  
   ।  ᯮᮡ   ॠ樨.  ࠭
   ਢ ᯮᮡ ॠ樨. ᯮ  , 
    室   ᨢ. ⢥, ⠭ 
   ᪮ ਬ ॠ 㤥 ᮧ, 室 
   ॡ ண ᪠  ⭮ ।⠢
   (. ࠦ 4  $$8.9).
          ᯮ㥬 ᯨ᮪    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; } // ४ᨢ 㤠 
                                      // ꥪ⮢  ᯨ᪥
            };

    ꥪ Link ᮤন  (, 祭).  ᠭ
    Link  ,   ࠭,  ꥪ Link 
   ᮧ, ࠡ    㭨⮦ ⮫쪮  
   ᮮ⢥ ᮢ   Map.   
   ।⥫ ᠭ 蠡 ᮢ Map  Mapiter.
         Map  । ⠪:

           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; }  // ४ᨢ 㤠
                                       //  ꥪ⮢  ᯨ᪥
              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);

                  // 㭪樨  樨

              Mapiter<K,V> element(const K& k)
              {
                (void) operator[](k);  // ᤥ k ⥪騬 ⮬
                return Mapiter<K,V>(this,current);
              }
              Mapiter<K,V> first();
              Mapiter<K,V> last();
            };

    ࠭  㯮冷祭 ᯨ᪥   . 
    祣    ᪮७ ᪠
   (. ࠦ 4  $$8.9). 祢   㭪
   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) { // 
                    current = p;
                    return current->value;
                 }

             if (k < p->key) { // ⠢ । p ( 砫)
                current = new Link<K,V>(k,def_val);
                current->pre = p->pre;
                current->suc = p;
                if (p == head)  // ⥪騩  ⠭ 砫
                   head = current;
                else
                   p->pre->suc = current;
                p->pre = current;
                return current->value;
              }

              Link<K,V>* s = p->suc;
              if (s == 0) {  // ⠢ ᫥ p ( )
                 current = new Link<K,V>(k,def_val);
                 current->pre = p;
                 current->suc = 0;
                 p->suc = current;
                 return current->value;
              }
              p = s;
            }
          }

    樨 頥 뫪  祭, ஥
   ᮮ⢥   ࠬ . ᫨ ⠪ 祭
    , 頥    ⠭ 祭.
     ᯮ짮  樨   
   ᢠ. ⠭ 祭  祩  祭
   ⠭ ࠬ Map.  樨 樨 ।
   祭 current, ᯮ㥬 ࠬ.
        ⠫ 㭪権-童 ⠢  ⢥
   ࠦ:

           template<class K, class V>
           void  Map<K,V>::remove(const K& k)
           {
              // . ࠦ 2  $$8.10
           }

           template<class K, class V>
           Map<K,V>::Map(const Map<K,V>& m)
           {
              // ஢ ⠡ Map    ⮢
           }

           template<class K, class V>
           Map& Map<K,V>::operator=(const Map<K,V>& m)
           {
              // ஢ ⠡ Map    ⮢
           }

        ⠫ ⮫쪮 । .   Map
    㭪樨-童 first(), last()  element(const K&), 
    , ⠭ ᮮ⢥⢥  , ᫥
     箬-ࠬ஬ .   , ᪮
    ࠭  㯮冷祭  砬 .
       Mapiter  Map । ⠪:

           template<class K, class V> class Mapiter {
             friend class Map<K,V>;

             Map<K,V>* m;
             Link<K,V>* p;

             Mapiter(Map<K,V>* mm, Link<K,V>* pp)
                 { m = mm; p = pp; }
           public:
             Mapiter() { m = 0; p = 0; }
             Mapiter(Map<K,V>& mm);

             operator void*() { return p; }

             const K& key();
             V& value();

             Mapiter& operator--();  // 䨪᭠
             void operator--(int);   // 䨪᭠
             Mapiter& operator++();  // 䨪᭠
             void operator++(int);   // 䨪᭠
           };

   ᫥ 樮஢  㭪樨 key()  value()  Mapiter
   뤠   祭 ⮣ ,   ⠭
   .

          template<class K, class V> const K& Mapiter<K,V>::key()
          {
            if (p) return p->key; else return m->def_key;
          }

          template<class K, class V> V& Mapiter<K,V>::value()
          {
            if (p) return p->value; else return m->def_val;
          }

      㪠⥫ﬨ । 樨 ++  --  த
    ⠬ Map ।  :

        Mapiter<K,V>& Mapiter<K,V>::operator--() //䨪 ६
        {
          if (p) p = p->pre;
          return *this;
        }

        void Mapiter<K,V>::operator--(int)  // 䨪 ६
        {
          if (p) p = p->pre;
        }

        Mapiter<K,V>& Mapiter<K,V>::operator++() // 䨪 ६
        {
          if (p) p = p->suc;
          return *this;
        }

        void Mapiter<K,V>::operator++(int)   // 䨪 ६
        {
          if (p) p = p->suc;
        }

   䨪 樨 । ⠪,     
   祭.   ⮬,    ᮧ  । 
   ꥪ Mapiter   蠣 樨 ⥫,  짠 
    㤥  .
       ꥪ Mapiter  樠஢ ⠪, ⮡  
   ⠭  砫 Map:

        template<class K, class V> Mapiter<K,V>::Mapiter(Map<K,V>& mm)
        {
            m == &mm; p = m->head;
         }

        ८ࠧ operator void*() 頥 , ᫨
     ⠭   Map,  㫥 祭 .
     ஢  iter, ਬ, ⠪:

           void f(Mapiter<const char*, Shape*>& iter)
           {
             // ...
             if (iter) {
              // ⠭   ⠡
             }
             else {
              //  ⠭   ⠡
             }

             // ...
           }

    ਥ ᯮ  ஫ ⮪ 権
   -뢮  $$10.3.2.
       ᫨   ⠭   ⠡,  㭪樨
   key()  value()  뫪  ⠭ ꥪ.
       ᫨ ᫥   ।  뫨  祭, 
   ਢ    ணࠬ, ᯮ ⠡ Map.
    室 ⮪  ᯨ᪮  祭 ᫥饣 :

             hammer       2
             nail         100
             saw          3
             saw          4
             hammer       7
             nail         1000
             nail         250

   㦭 ஢ ᯨ᮪ ⠪, ⮡ 祭, ᮮ⢥騥 
   ।, ᪫뢠,   稢訩 ᯨ᮪  
   ⮣ 祭:

             hammer        9
             nail          1350
             saw           7
             -------------------
             total         1366

   砫 襬 㭪,  ⠥ 室 ப  
   ।   ⢮  ⠡. 箬  ⮩ ⠡ 
   ࢮ ᫮ ப:

             template<class K, class V>
                void readlines(Map<K,V>&key)
                {
                  K word;
                  while (cin >> word) {
                    V val  = 0;
                    if (cin >> val)
                       key[word] +=val;
                    else
                       return;
                  }
                }

       ணࠬ, 뢠 㭪
   readlines()   稢 ⠡:

              main()
              {
                Map<String,int> tbl("nil",0);
                readlines(tbl);

                int total = 0;
                for (Mapiter<String,int> p(tbl); p; ++p) {
                    int val = p.value();
                    total +=val;
                    cout << p.key() << '\t' << val << '\n';
                }

                cout << "--------------------\n";
                cout << "total\t" << total << '\n';
              }

   8.9 ࠦ

   1. (*2) । ᥬ⢮ ᯨ᪮   , 
        ᯨ᪮   , ।  $$8.3.
   2. (*3) । 蠡 ⨯ String, ࠬ஬ ண 
      ⨯ ᨬ.     ᯮ짮  ⮫쪮 
       ᨬ,    ᪮  lchar, 
      ।⠢ ᨬ   ᪮ 䠢  ७
       ᨬ. 㦭  ⠪ । String, ⮡
      짮⥫  ⨫ 襭 ࠪ⨪ ணࠬ 
        ६   㤮⢥  ࠢ   ப
      ᮬ.
   3. (*1.5) ।  Record ()   童-묨:
      count (⢮)   price (業). 冷   ⠪
      ᥩ    童.  ⮬   㭪
      ஢  蠡 Vector.
   4. (*2)  । 蠡  Map, ᠢ
      騥 㭪樨-童.
   5. (*2)   ॠ Map  $$8.8, ᯮ ᯨ
         .
   6. (*2.5)   ॠ Map  $$8.8, ᯮ
      ᡠ஢ ॢ.  ॢ ᠭ  $$6.2.3 
      .  "⢮ ணࠬ஢  " .1, "", 1978 [K].
   7. (*2) ࠢ ⢮  ॠ権 Map.  ࢮ ᯮ
       Link  ᢮ ᮡ⢥ 㭪樥 ࠧ饭,   ன
      -  .
   8. (*3) ࠢ ந⥫쭮 ணࠬ  ᫮ 
      $$8.8   ⠪  ணࠬ,  ᯮ饩  Map. 樨
      -뢮   ᯮ짮   ணࠬ.
      ࠢ ᪮쪮 ⠪ ணࠬ, ᯮ ࠧ ਠ
       Map,  ⮬ ᫥    襩 ⥪, ᫨  ⠬
      .
   9. (*2.5)    Map ॠ ⮯ ஢.
       ᠭ  [K] .1, . 323-332. (. ࠦ 6).
   10. (*2)  ணࠬ  $$8.8 ⠪, ⮡  ࠡ⠫
      ࠢ쭮      , ᮤঠ ஡
      (ਬ, "thumb back").
   11. (*2) । 蠡 ⨯  ⥭ ࠧ  ப,
      ਬ, ⠪ (।, ⢮, 業).
   12. (*2) ।  Sort  $$8.4.5, ᯮ騩 ஢
       ⮤ .     ⮤ ஢
        ࠬ 蠡.  ஢ ᠭ  [K]
      .3, $$5.2.1 (. ࠦ 6).
   13. (*1)  । Map  Mapiter ⠪, ⮡ 䨪
      樨 ++  -- 頫 ꥪ Mapiter.
   14. (*1.5) ᯮ 蠡 ⨯  ⨫ 쭮
      ணࠬ஢,   뫮   $$8.4.5  
      㭪 ஢, ⠭ ࠧ  Vector<T>  T[].

