                                                                  ++   784
                                16.  

      ,      .
      ,     
   .     , 
  ,      . ..),    
       .    
          . 
           C++.
    16     .   
,    ,      
   .  ,       
 : -,  -   .   
 ,      .   
,            
    .  ,     
        .      
,    :      
         .    
     .

                         16.1.   

   ,     ,   .
        ;   
 ,     .    
FIFO   ,  . (    C++
,  ,    6.17.     
      .)
   ,    Queue   :

       :
    void add( item );
       :
    item remove();

                                                            ++   785

   ,   :
    bool is_empty();
   ,   :
    bool is_full();

    Queue    :

   class Queue {
   public:
      Queue();
      ~Queue();
      Type& remove();
      void add( const Type & );
      bool is_empty();
      bool is_full();
   private:
      // ...
   };

     ,     Type? ,   
  Queue,  Type  int.  Queue  
   int.       
 ,        int,    ,
    :

   Queue qObj;
   string str( "vivisection" );
   qObj.add( 3.14159 ); // :     3
   qObj.add( str ); // :    string  int

          int,   C++ ,  
      int,  ,   
.  ,         int.  
 Queue       double, char,
   ,    
.
   ,    ,    Queue    
double,      ,     ..  
   ,      :
IntQueue, DoubleQueue, ComplexQueue, StringQueue.    
    ,   .
        .    
 Queue   .   
:        
 .        
          
.

                                                                ++   786

    ,   C++     .
      Queue    
.         :

   template <class Type>
   class Queue {
   public:
      Queue();
      ~Queue();
      Type& remove();
      void add( const Type & );
      bool is_empty();
      bool is_full();
   private:
      // ...
  };

      Queue,    ,   
,   :

   Queue<int> qi;
   Queue< complex<double> > qc;
   Queue<string> qs;

    Queue       
    .    
 :

      Queue     
      : front  back.      ;
     QueueItem      Queue.
            QueueItem,
       : value  next.  value    
      Queue,  next       
    QueueItem .

           , ,
    .     QueueItem:

   template <class T>
   class QueueItem;

    ,         
template.          ,
 .    .     -,
  ,  -,  
 .

                                              ++   787

   -      class  typename ( 
  ),    . ( 
typename   ,     C++.
  10.1  ,       .) 
  ,       
   . ,    
 QueueItem   - T.   
 T       , ,  int,
double, char*, complex  string.
         -:

   template <class T1, class T2, class T3>
   class Container;

      class  typename   .
     :

   // :   <typename T, class U> 
   // <typename T, typename U>
   template <typename T, U>
   class collection;

    -      
      ,    
      . , -
       -,  
  ..
           . 
,         ,  
    . ,   Buffer  
-,   ,   ,  -
,   :

   template <class Type, int size>
   class Buffer;

           . 
  ,   ,    :

                                                           ++   788

   template <class Type>
   class QueueItem {
   public:
      // ...
   private:
      // Type   
      Type item;
      QueueItem *next;
   };

      Type      item.  
   Type      
  .    
 .
              
  .        
  ,    ,     .  
  item   double,   :

   typedef double Type;

   template <class Type>
   class QueueItem {
   public:
      // ...
   private:
      //  Item -  double
      Type item;
      QueueItem *next;
   };

             :
template <class Type>

   class QueueItem {
   public:
      // ...
   private:
      // :       ,  
      //   Type
      typedef double Type;
      Type item;
      QueueItem *next;
   };

            . 
     :

                                                            ++   789

   // :      Type
   template <class Type, class Type>
   class container;

            
:

   // :    Type   
   template <class Type>
      class QueueItem;

   template <class Type>
      class Queue;

            
     . ,    QueueItem
    :

   //    QueueItem
   //        
   //  
   template <class T> class QueueItem;
   template <class U> class QueueItem;

   //   
   template <class Type>
   class QueueItem { ... };

          (    -
,    -)    ,    
,        .  
      ,   
. ,      Buffer  
 ,     1024:

   template <class Type, size = 1024>
   class Buffer;

            
.     ,      
,         ,   
 (      ):

   template <class Type, size = 1024>
   class Buffer;

                                                    ++   790

   // :       
   template <class Type=string, int size>
   class Buffer;

   (,          
,     C++.    
,     12,   
,     .)
             ,
     .    
  QueueItem:

   template <class Type>
   class QueueItem {
   public:
      QueueItem( const Type & );
   private:
      Type item;
      QueueItem *next;
   };

    ,     QueueItem    
   

   QueueItem<Type>

           QueueItem
(,      ,    ,  
   ).  QueueItem     
 -  ,     
.         
 display.      QueueItem   ,
.. QueueItem<Type>.

   template <class Type>

   void display( QueueItem<Type> &qi )
   {
      QueueItem<Type> *pqi = &qi;
      // ...
   }

             16.1.1.    Queue  QueueItem

        Queue.    
 Queue.h     QueueItem:

                                                     ++   791

   #ifndef QUEUE_H
   #define QUEUE_H

   //  QueueItem
   template <class T> class QueueItem;

   template <class Type>
   class Queue {
   public:
      Queue() : front( 0 ), back ( 0 ) { }
      ~Queue();
      Type& remove();
      void add( const Type & );
      bool is_empty() const {
         return front == 0;
      }
   private:
      QueueItem<Type> *front;
      QueueItem<Type> *back;
   };

   #endif

      Queue     Queue 
 <Type>  .     
QueueItem    Queue . ,   front
 :

   template <class Type>
   class Queue {
   public:
      // ...
   private:
      // :    QueueItem 
      QueueItem<Type> *front;
   };


                                    16.1

      (  )  :

   (a) template <class Type>
       class Container1;
       template <class Type, int size>

   (b) template <class T, U, class V>
       class Container1;
       class Container2;

                                                             ++   792

   (c) template <class C1, typename C2>
   (d) template <typename myT, class myT>

   (e) template <class Type, int *pi>
       class Container3 {};
       class Container4 {};

   (f) template <class Type, int val = 0>
       class Container6;
       template <class T = complex<double>, int v>
       class Container5;
       class Container6;

                                      16.2

      List .   ?

   template <class elemenType>
   class ListItem;

   template <class elemType>
   class List {
   public:
      List<elemType>()
         : _at_front( 0 ), _at_end( 0 ), _current( 0 ), _size( 0 )
      {}
      List<elemType>( const List<elemType> & );
      List<elemType>& operator=( const List<elemType> & );

      ~List();

      void insert( ListItem *ptr, elemType value );
      int remove( elemType value );

      ListItem *find( elemType value );

      void display( ostream &os = cout );
      int size() { return _size; }
   private:
      ListItem *_at_front;
      ListItem *_at_end;
      ListItem *_current;
      int _size

                                                              ++   793

   };

                          16.2.   

      ,     , 
       .   Queue
    Queue    .
,  :

   Queue<int> qi;

        Queue 
  int.
          
 .    Queue    int 
  Type      int,  
  Queue  :

   template <class int>
   class Queue {
   public:
      Queue() : front( 0 ), back ( 0 ) { }
      ~Queue();
      int& remove();
      void add( const int & );
      bool is_empty() const {
         return front == 0;
      }
   private:
      QueueItem<int> *front;
      QueueItem<int> *back;
};

      Queue    string,  :

   Queue<string> qs;

       Type       string.
 qi  qs     .
            
     . ,  Queue   int   
         string.
          Queue<int>
 Queue<string>.  <int>  <string>,    Queue, 
  .        
    .       
  .      ,   
     :

                                                              ++   794

   Queue qs; // :   ?

      Queue     , 
    :

   //        
   //   Queue
   extern Queue< complex<double> >
      foo( Queue< complex<double> > &, Queue< complex<double> > & );

   //   - ,    Queue
   bool (Queue<double>::*pmf)() = 0;

   //   0     Queue
   Queue<char*> *pqc = static_cast< Queue<char*>* > ( 0 );

     ,    Queue,  
  ,    :

   extern Queue<double> eqd;
   Queue<int> *pqi = new Queue<int>;
   Queue<int> aqi[1024];

   int main() {
      int ix;
      if ( ! pqi->is_empty() )
         ix = pqi->remove();
      // ...
      for ( ix = 0; ix < 1024; ++ix )
         eqd[ ix ].add( ix );
      // ...
}

             ,   
   :

   //   
   template <class Type>
   void bar( Queue<Type> &,  //    
             Queue<double> & //    
   )

          .
,         
 Queue:

   void foo( Queue<int> &qi )
   {
      Queue<int> *pq = &qi;
      // ...

                                                             ++   795

   }

       ,    
  ,    .   
   . ,      
   :

   class Matrix;
   Matrix *pm; // :   Matrix  
   void inverse( Matrix & ); //  

            
   . (,    ,  
  C++,      
    .) ,   foo() 
    Queue<int>,       Queue:


   // Queue<int>       foo()
   void foo( Queue<int> &qi )
   {
      Queue<int> *pqi = &qi;
      // ...
}

      ,     . 
   obj1 :     ,
     Matrix:

   class Matrix;
   Matrix obj1; // :  Matrix  
   class Matrix { ... };
   Matrix obj2; // 

    ,   ,    ,
   .      qi
    Queue<int>:

   Queue<int> qi; //  Queue<int>

    Queue<int>       , 
    .
          ,  
      ,    . 
   foo()  Queue<int>   
:    pqi,   qi  

                                                                  ++   796

      pqi  qi    
  -  :

   void foo( Queue<int> &qi )
   {
      Queue<int> *pqi = &qi;
      // Queue<int>     -
      pqi->add( 255 );
      // ...
   }

    Queue<int>       -
 add()  foo().
   ,      Queue     
QueueItem:

   template <class Type>
   class Queue {
   public:
      // ...
   private:
     QueueItem<Type> *front;
     QueueItem<Type> *back;
};

     Queue  int  front  back   
QueueItem<int>. ,   Queue<int> 
  QueueItem,   int.  
   ,  QueueItem<int> 
      -  Queue<int>.
     QueueItem       Queue
       . 
      Queue.
  QueueItem      
 Queue   . (     
  .)
      ,    ,  
    . , , 
   QueueItem     
?

   template <class Type>
   class QueueItem {
   public:
      QueueItem( Type ); //   
      // ...
};

                                                           ++   797

         .  , 
QueueItem    (, QueueItem<int>).  
      (, Matrix),  
,      , 
. (  7.3   ,  
      .)   
     :

   QueueItem( const Type & );

     ,   ,   
QueueItem,   :

   template <class Type>
   class QueueItem {
      // ...
   public:
      //  
      QueueItem( const Type &t ) {
         item = t; next = 0;
      }
   };

           (, string), 
item  !    string  
 item     QueueItem.  
  item   .   
    item     
  QueueItem:

   template <class Type>
   class QueueItem {
      // ...
   public:
      // item      
      QueueItem( const Type &t )
         : item(t) { next = 0; }
   };

(          
14.5.)

           16.2.1.    -

          .  ,  
 ,   .    
   Screen (.  13)  , 
  :

                                                             ++   798

   template <int hi, int wid>
   class Screen {
   public:
      Screen() : _height( hi ), _width( wid ), _cursor ( 0 ),
                 _screen( hi * wid, '#' )
               { }
      // ...
   private:
      string _screen;
      string::size_type _cursor;
      short _height;
      short _width;
   };

   typedef Screen<24,80> termScreen;
   termScreen hp2621;
   Screen<8,24> ancientScreen;

   ,    ,   ,  
, ..    .    typedef
termScreen     Screen<24,80>,    
hi  24,   wid  80.        .
      BufPtr    ,   
,     new(),    
 :

   template <int *ptr> class BufPtr { ... };
   // :       
   BufPtr< new int[24] > bp;

          .  
     - .  
      ,     
,    (   const
),         -
.       sizeof:

   template <int size> Buf { ... };
   template <int *ptr> class BufPtr { ... };

   int size_val = 1024;
   const int c_size_val = 1024;

   Buf< 1024 > buf0; // 
   Buf< c_size_val > buf1; // 
   Buf< sizeof(size_val) > buf2; // : sizeof(int)
   BufPtr< &size_val > bp0; // 
   // :     
   Buf< size_val > buf3;

                                                    ++   799

      ,   - 
     ,    
     :

   template < class Type, int size >
   class FixedArray {
   public:
      FixedArray( Type *ar ) : count( size )
      {
         for ( int ix = 0; ix < size; ++ix )
            array[ ix ] = ar[ ix ];
      }
   private:
      Type array[ size ];
      int count;
   };

   int ia[4] = { 0, 1, 2, 3 };
   FixedArray< int, sizeof( is ) / sizeof( int ) > iA{ ia );

          
- . ,    Screen     
     Screen<24,80>:

   const int width = 24;
   const int height = 80;

   //   Screen< 24, 80 >
   Screen< 2*12, 40*2 > scr0;
   Screen< 6+6+6+6, 20*2 + 40 > scr1;
   Screen< width, height > scr2;

         -  
.     , 
  :

    l-,   l-  r-
    ,       :

   template <int *ptr> class BufPtr { ... };
   int array[10];

   BufPtr< array > bpObj; //    

    :

   template <const int *ptr> class Ptr { ... };
   int iObj;

                                                     ++   800

   Ptr< &iObj > pObj; //   int*  const int*

    :

   template <int hi, int wid> class Screen { ... };
   const short shi = 40;
   const short swi = 132;
   Screen< shi, swi > bpObj2; //   short  int

     :

   template <unsigned int size> Buf{ ... };
   Buf< 1024 > bpObj; //   int  unsigned int

(      9.3.)

     :

   extern void foo( char * );
   extern void bar( void * );
   typedef void (*PFV)( void * );
   const unsigned int x = 1024;

   template <class Type,
             unsigned int size,
             PFV handler> class Array { ... };

   Array<int, 1024U, bar> a0; // :   
   Array<int, 1024U, foo> a1; // : foo != PFV

   Array<int, 1024, bar> a2; // : 1024   unsigned int
   Array<int, 1024, bar> a3; // : foo != PFV

   Array<int, x, bar> a4; // :   
   Array<int, x, foo> a5; // : foo != PFV

    a0  a4  Array  ,     
  .  a2   ,  
 1024  int    unsigned int - size 
   .  a1, a3  a5 ,   
      .
     0      :

                                                         ++   801

   template <int *ptr>
   class BufPtr { ... };

   // : 0   int
   //       
   BufPtr< 0 > nil;


                                  16.3

   ,        
:

   template < class Type >
      class Stack { };

   void f1( Stack< char > ); // (a)

   class Exercise {
      // ...
      Stack< double > &rsd; // (b)
      Stack< int > si; // (c)
   };

   int main() {
      Stack< char > *sc; // (d)
      f1( *sc ); // (e)
      int iObj = sizeof( Stack< string > ); // (f)
   }


                                     16.4

        ? ?

   template < int *ptr > class Ptr ( ... };
   template < class Type, int size > class Fixed_Array { ... };
   template < int hi, int wid > class Screen { ... };

   (a) const int size = 1024;
       Ptr< &size > bp1;

   (b) int arr[10];
       Ptr< arr > bp2;

   (c) Ptr < 0 > bp3;

                                             ++   802

   (d) const int hi = 40;
       const int wi = 80;
       Screen< hi, wi+32 > sObj;

   (e) const int size_val = 1024;
       Fixed_Array< string, size_val > fa1;

   (f) unsigned int fasize = 255;
       Fixed_Array< int, fasize > fa2;


   (g) const double db = 3.1415;
       Fixed_Array< double, db > fa3;


                         16.3. -  

       , -      
   (   ),   .  
   -    Queue.
,  Queue  ,    
  :

   template <class Type>
   class Queue {
      // ...
   public:
      //  
      Queue() : front( 0 ), back( 0 ) { }
      // ...
   };

     -      
     ,    
 .  -    
template,     . ,  Queue 
  :

                                                             ++   803

   template <class Type>
   class Queue {
   public:
      Queue();
   private:
      // ...
   };

   template <class Type>
   inline Queue<Type>::Queue( ) { front = back = 0; }

      Queue (  ::)   ,
,     -.  
Queue    (  ::)   -, 
     ,    . 
    ;.        
Type ,         .
   -     .  C++ , 
         . ( 
       
  .)   -   
,    :

   Queue<string> qs;

    qs   Queue<string>.     
  Queue<string>.    , 
 - (),  string.
   -       
 (..      ).  ,    
 -,       (. 
16.11)     (.  16.9).
    qs   Queue<string>.     
  Queue<string>.    , 
 - (),  string.
   -       
 (..      ).  ,    
 -,       (. 
16.11)     (.  16.9).

              16.3.1. -  Queue  QueueItem

    ,     -  ,
   Queue  QueueItem:

                                                         ++   804

   template <class Type>
   class Queue {
   public:
      Queue() : front( 0 ), back ( 0 ) { }
      ~Queue();
      Type& remove();
      void add( const Type & );
      bool is_empty() const {
         return front == 0;
      }
   private:
      QueueItem<Type> *front;
      QueueItem<Type> *back;
   };

   ,   - remove()  add()     , 
 .  Queue  :

   template <class Type>
   Queue<Type>::~Queue()
   {
      while (! is_empty() )
      remove();
   }

   - Queue<Type>::add()      :

   template <class Type>
   void Queue<Type>::add( const Type &val )
   {
      //    QueueItem
      QueueItem<Type> *pt =
         new QueueItem<Type>( val );
      if ( is_empty() )
         front = back = pt;
      else
      {
         back->next = pt;
         back = pt;
      }
   }

   - Queue<Type>::remove()   ,  
 ,    .

                                                                ++   805

   #include <iostream>
   #include <cstdlib>

   template <class Type>
   Type Queue<Type>::remove()
   {
      if ( is_empty() )
      {
         cerr << "remove()    \n";
         exit( -1 );
      }
      QueueItem<Type> *pt = front;
      front = front->next;
      Type retval = pt->item;
      delete pt;
      return retval;
   }

      -    Queue.h,  
  ,    . (  , 
    ,    ,
    16.8.)
          -
 Queue:

   #include <iostream>
   #include "Queue.h"

   int main()
   {
      //   Queue<int>
      //  new ,  Queue<int>  
      Queue<int> *p_qi = new Queue<int>;

      int ival;
      for ( ival = 0; ival < 10; ++ival )
        //  - add()
        p_qi->add( ival );

      int err_cnt = 0;
      for ( ival = 0; ival < 10; ++ival ) {
        //  - remove()
        int qval = p_qi->remove();
        if ( ival != qval ) err_cnt++;
      }

      if ( !err_cnt )
         cout << "!! queue executed ok\n";
      else cerr << "?? queue errors: " << err_cnt << endl;

      return 0;
   }

          :

                                                            ++   806

   !! queue executed ok


                               16.5
 
      Screen,    16.2,  -
 Screen (.  13.3, 13.4  13.6)   - .

                       16.4.     

                                                              ++   807

    ( )     . 
       foo(), - bar()   foobar
         QueueItem:

   class Foo {
      void bar();
   };

   template <class T>
   class QueueItem {
      friend class foobar;
      friend void foo();
      friend void Foo::bar();
      // ...

   };

      foobar,   foo()      
           
    QueueItem.
          -    Foo,
      . ,       
          . QueueItem 
       Foo::bar(),      Foo;

        .   
         ,
       QueueItem,     
     .   ,  
     QueueItem,   foobar, foo() 
    Queue::bar()  .

   template <class Type>
   class foobar { ... };

   template <class Type>
   void foo( QueueItem<Type> );

   template <class Type>
   class Queue {
      void bar();
      // ...
   };

   template <class Type>
   class QueueItem {
      friend class foobar<Type>;
      friend void foo<Type>( QueueItem<Type> );
      friend void Queue<Type>::bar();
      // ...
   };

                                                            ++   808

              , 
          .     
     foobar  Queue,     foo()    , 
         QueueItem.
       ,    foo() ,  
     :

   friend void foo<Type>( QueueItem<Type> );

            : foo<Type>.
       ,     
        foo().     
      :

   friend void foo( QueueItem<Type> );

             
      (   ),        
     QueueItem.     10.6,    
        ,    
         QueueItem   
          .  ,   
     ,       
      ;

        .  
       --   
     QueueItem   .     QueueItem 
     foobar, foo()  Queue<T>::bar()  :

    template <class Type>
    class QueueItem {
       template <class T>
          friend class foobar;

       template <class T>
          friend void foo( QueueItem<T> );

       template <class T>
          friend class Queue<T>::bar();

       // ...

   };

    ,         
 ,     C++.

              16.4.1.     Queue  QueueItem

    QueueItem      
 ,        

                                                              ++   809

 .   Queue    QueueItem, 
      .
         .    ,
    Queue    QueueItem:

   template <class Type>
   class QueueItem {
      //   Queue  
      //   QueueItem
      template <class T> friend class Queue;
   };

      , ,  Queue,  
string,  QueueItem,   complex<double>.
Queue<string>       QueueItem<string>. 
,        Queue 
QueueItem,   .   ,
    :

   template <class Type>
   class QueueItem {
      //    QueueItem  
      //       Queue
      friend class Queue<Type>;
      // ...
   };

       ,     QueueItem 
  Queue,    ,  . ,
 Queue,   int,    QueueItem,
   int.    QueueItem,
  complex<double>  string,   Queue
  .
            
 Queue.      
 .        Queue,  
      .     ?

   //     Queue?
   ostream& operator<<( ostream &, ??? );

    Queue    ,     
     :

   ostream& operator<<( ostream &, const Queue<int> & );

                                                             ++   810

         ,    Queue
 int.  ,  Queue      string?

   ostream& operator<<( ostream &, const Queue<string> & );

             ,
    ,     
 Queue. :

   ostream& operator<<( ostream &, const Queue<Type> & );

            :

   template <class Type> ostream& operator<<( ostream &, const Queue<Type> & );

     ,   ostream   
Queue,     .    
      :

   template <class Type>
   ostream& operator<<( ostream &os, const Queue<Type> &q )
   {
      os << "< ";
      QueueItem<Type> *p;
      for ( p = q.front; p; p = p->next )
         os << *p << " ";

      os << " >";
      return os;
   }

       int   3, 5, 8, 13,   
     

   < 3 5 8 13 >

    ,        front 
Queue.      Queue:

   template <class Type>
   class Queue {
      friend ostream& operator<<( ostream &, const Queue<Type> & );
      // ...
   };

   ,         Queue,  
    Queue   operator<<().

                                                           ++   811

     Queue    operator<<() 
QueueItem:

   os << *p;

            ;  
 ,        :

   template <class Type>
   ostream& operator<<( ostream &os, const QueueItem<Type> &qi )
   {
      os << qi.item;
      return os;
   }

          item  QueueItem, 
    QueueItem.    :

   template <class Type>
   class QueueItem {
      friend class Queue<Type>;
      friend ostream& operator<<( ostream &, const QueueItem<Type> & );
      // ...
   };

      QueueItem   ,  item   :

   os << qi.item;

          Queue. 
     Queue ,   
,    .    , 
          
 Queue.        ,  
  ,     
 ,    ,   
 ,     .  Queue 
 ,    ,   ,   
   .
         -
  Queue  QueueItem:

                                                             ++   812

   #include <iostream>
   #include "Queue.h"

   int main() {
      Queue<int> qi;
      //   
      // ostream& operator<<(ostream &os, const Queue<int> &)
      // ostream& operator<<(ostream &os, const QueueItem<int> &)
      cout << qi << endl;

      int ival;
      for ( ival = 0; ival < 10; ++ival )
         qi.add( ival );
      cout << qi << endl;

      int err_cnt = 0;
      for ( ival = 0; ival < 10; ++ival ) {
         int qval = qi.remove();
         if ( ival != qval ) err_cnt++;
      }
      cout << qi << endl;

      if ( !err_cnt )
         cout << "!! queue executed ok\n";
      else cout << "?? queue errors: " << err_cnt << endl;

      return 0;
   }

         :

   < >
   < 0 1 2 3 4 5 6 7 8 9 >
   < >
   !! queue executed ok


                                     16.6

      Screen,    16.5, 
    (.  15.6   15.2)   .
,    ,        Screen,
   .

                   16.5.    

          -. 
      . 
 new()  delete()   QueueItem.   QueueItem 
   :

   static QueueItem<Type> *free_list;
   static const unsigned QueueItem_chunk;

      QueueItem  :

                                                            ++   813

   #include <cstddef>

   template <class Type>
   class QueueItem {
      // ...
   private:
      void *operator new( size_t );
      void operator delete( void *, size_t );
      // ...
      static QueueItem *free_list;
      static const unsigned QueueItem_chunk;
      // ...
   };

    new()  delete()  ,   
  QueueItem  :     
 QueueItem ( ,  Queue).
    new()    :

   template <class Type> void*
   QueueItem<Type>::operator new( size_t size )
   {
      QueueItem<Type> *p;
      if ( ! free_list )
      {
         size_t chunk = QueueItem_chunk * size;
         free_list = p =
         reinterpret_cast< QueueItem<Type>* >( new char[chunk] );

         for ( ; p != &free_list[ QueueItem_chunk - 1 ]; ++p )
            p->next = p + 1;
            p->next = 0;
      }
      p = free_list;
      free_list = free_list->next;
      return p;
   }

      delete()  :

   template <class Type>
   void QueueItem<Type>::
   operator delete( void *p, size_t )
   {
      static_cast< QueueItem<Type>* >( p )->next = free_list;
      free_list = static_cast< QueueItem<Type>* > ( p );
   }

        free_list  QueueItem_chunk.
     -:

                                                              ++   814

   /*    QueueItem 
    *  free_list    
    */
   template <class T>
      QueueItem<T> *QueueItem<T>::free_list = 0;

   /*    QueueItem 
    *  QueueItem_chunk     24
    */
   template <class T>
      const unsigned int
      QueueItem<T>::QueueItem_chunk = 24;

            
  ,      template  
  <class T>.     
QueueItem<T>::, ,      
QueueItem.        Queue.h 
    ,    . (  16.8
 ,     ,    ,
   .)
           ,  
  .      . 
       :    
   .   
   .  ,   
       
:

   // : QueueItem -     
   int ival0 = QueueItem::QueueItem_chunk;

   int ival1 = QueueItem<string>::QueueItem_chunk; // 
   int ival2 = QueueItem<int>::QueueItem_chunk; // 


                                   16.7

       15.8  new()  delete()   
   screenChunk  freeStore    Screen,
   16.6.

                     16.6.    

     QueueItem      
 Queue.     ,   QueueItem
  ,     
 -  Queue,   QueueItem. 
 QueueItem    ,     
        - Queue.

                                                                  ++   815

         ,   
  QueueItem     Queue.  QueueItem
   ,    
,          Queue   
(,  ).     QueueItem , 
 Queue  QueueItem  .
        ,    
QueueItem  Queue   .
        Queue    
  QueueItem,      .  
    ,     
  :

   template <class Type>
   class Queue:
      // ...
   private:
      class QueueItem {
      public:
         QueueItem( Type val ) : item( val ), next( 0 ) { ... }
         Type item;
         QueueItem *next;
      };

      //  QueueItem -  ,
      //   ,   Queue,
      //    <Type>  QueueItem  
      QueueItem *front, *back;
      // ...
   };

      Queue    QueueItem  
  Type.    QueueItem  Queue 
  .
           ,   
 ,     .   16.2  , 
   Queue  int   
   QueueItem<int>.  front  back    
QueueItem<int>,        , 
    ,  QueueItem  
  Queue. QueueItem<int>   ,  
front  back   -  Queue<int>.
             (
 typedef):

                                                                 ++   816

   template <class Type, int size>
   class Buffer:
   public:
      enum Buf_vals { last = size-1, Buf_size };
      typedef Type BufType;
      BufType array[ size ];
      // ...

    };

         Buf_size,    Buffer 
   ,    
. , 

   Buffer<int, 512> small_buf;

 Buf_size  512,  last   511. 

   Buffer<int, 1024> medium_buf;

 Buf_size  1024,  last   1023.
           
.        
   (   ).   
       
:

   // :   Buffer?
   Buffer::Buf_vals bfv0;

   Buffer<int,512>::Buf_vals bfv1; // 

       ,       
 :

                                                               ++   817

   template <class T> class Q {
   public:
      enum QA { empty, full }; //    
      QA status;
      // ...
   };

   #include <iostream>

   int main() {
      Q<double> qd;
      Q<int> qi;

      qd.status = Q::empty; // :   Q?
      qd.status = Q<double>::empty; // 

      int val1 = Q<double>::empty;
      int val2 = Q<int>::empty;
      if ( val1 != val2 )
        cerr << " !" << endl;
      return 0;
   }

      Q  empty ,     empty
 ,    Q  .

                                16.8

     List     ListItem   13.10  .
      .

                               16.7. -

              .
 -    :  
  template,     :

                                                              ++   818

   template <class T>
   class Queue {
   private:
      //  -
      template <class Type>
      class CL
      {
         Type member;
         T mem;
      };
      // ...
   public:
      //  -
      template <class Iter>
      void assign( Iter first, Iter last )
      {
         while ( ! is_empty() )
         remove(); //  Queue<T>::remove()
         for ( ; first != last; ++first )
         add( *first ); //  Queue<T>::add( const T & )
      }
   };

(,  -   ,  
  C++.        
   ,    6.)
    -   . ,   
CL   Type,     assign()   Iter.  ,
  -     
. ,   CL    T,  
  Queue.
    -    Queue ,   Queue
        CL
- assign(). ,   Queue<int> 
 :

   Queue<int>::CL<char>
   Queue<int>::CL<string>

  :

   void Queue<int>::assign( int *, int * )
   void Queue<int>::assign( vector<int>::iterator, vector<int>::iterator )

    -     ,      .
   CL     Queue,   - 
 Queue     .   ,  
assign()    , ,    .

                                                               ++   819

   -      . ,
assign()        main():

   int main()
   { 
      //  Queue<int>
      Queue<int> qi;

      //  Queue<int>::assign( int *, int * )
      int ai[4] = { 0, 3, 6, 9 };
      qi.assign( ai, ai + 4 );

      //  Queue<int>::assign( vector<int>::iterator,
      // vector<int>::iterator )
      vector<int> vi( ai, ai + 4 );
      qi.assign( vi.begin(), vi.end() );
   }

     assign(),     Queue, 
  -    .
,    Queue<int>,    
    (,    ), 
     int (..  ,    ), 
   int. - assign()   .  
    ,   assign()  
   ;      
  ,    .
     main() - assign()    int*, 
   qi     int.  -
  vector<int>::iterator      
 qi     int. ,  
  ,        int. 
 ,    int.  ,   ,   
  assign():

   template <class Iter>
   void assign( Iter first, Iter last )
   {
      //     
      for ( ; first != last; ++first )
         add( *first );
   }

     assign()  add()   - Queue<Type>::add().
 Queue   int,   add()   :

   void Queue<int>::add( const int &val );

    *first    int  ,   
-  const int.   . , 

                                                                ++   820

  SmallInt   15.9,   ,  
   SmallInt,   - assign()  
  Queue<int>.   ,    SmallInt 
   SmallInt  int:

   class SmallInt {
   public:
      SmallInt( int ival = 0 ) : value( ival ) { }
      // : SmallInt ==> int
      operator int() { return value; }
      // ...
   private:
      int value;
   };

   int main()
   {
      //  Queue<int>
      Queue<int> qi;

      vector<SmallInt> vsi;
      //  
      // 
      // Queue<int>::assign( vector<SmallInt>::iterator,
      // vector<SmallInt>::iterator )
      qi.assign( vsi.begin(), vsi.end() );

      list<int*> lpi;
      //  
      //    - assign():
      //    int*  int
      qi.assign( lpi.begin(), lpi.end() );
   }

     assign() ,     
  SmallInt   int , ,   add() .  
 :   int*      
const int,    add() .
      C++   assign(),
    ,  - assign()    Queue.
 -     .  ,  , 
. ,    Queue    
:

                                                            ++   821

   template <class T>
   class Queue {
      // ...
   public:
      // - 
      template <class Iter>
      Queue( Iter first, Iter last )
         : front( 0 ), back( 0 )
      {
         for ( ; first != last; ++first )
            add( * first );
      }
   };

         
.       C++  
       -. ,  
(  )   main()  - 
:

   vector<int> vi( ai, ai + 4 );

          vector<int>
 int*,       
 int.
   -,    ,     
    . ,     CL
   assign()       
Queue:

                                                   ++   822

   template <class T>
   class Queue {
   private:
      template <class Type> class CL;
      // ...
   public:
      template <class Iter>
      void assign( Iter first, Iter last );
      // ...
   };

   template <class T> template <class Type>
   class Queue<T>::CL<Type>
   {
      Type member;
      T mem;
   };

   template <class T> template <class Iter>
   void Queue<T>::assign( Iter first, Iter last )
   {
      while ( ! is_empty() )
         remove();
      for ( ; first != last; ++first )
         add( *first );
   }

    -,      
,      ,    
   .     
assign() (   Queue)  

   template <class T> template <class Iter>

       template <class T>    
Queue.     - assign().    
  ,       .
  -  - assign():

   void Queue<TT>::assign( IterType first, IterType last )
   template <class TT> template <class IterType>
   { ... }


                    16.8.      A

            
  .        . ,
  :

                                                              ++   823

   template <class Type>
   class Queue { ... };

     Queue. ,   
 ,   , :

   int main() {
      Queue<int> *p_qi = new Queue<int>;
   }

    Queue<int>,   
   Queue.
      ,     , 
  . (      16.2.) 
   Queue<int> ,     
  Queue<int>,       , 
 new.
        ,      
,    ,     
,    :

   //   
   template <class Type>
   class Queue;

   Queue<int>* global_pi = 0; // :    

   int main() {
      // :  
      //      
      Queue<int> *p_qi = new Queue<int>;
   }

              .
      ,      
 ,    ,   
    ,      
,    .    
 ,    ,    
 .
   -   -  ,    
      ,   .   
       . 
 :

                                                            ++   824

   template <class Type>
   void Queue<Type>::add( const Type &val )
   { ... }

    Queue<Type>::add(). ,   
    -,    
Queue<int>,   Queue<int>::add(const int &), 
 :

   #include "Queue.h"

   int main() {
      //  Queue<int>
      Queue<int> *p_qi = new Queue<int>;
      int ival;
      // ...
      //  Queue<int>::add( const int & )
      p_qi->add( ival );
      // ...
   }

           
      .    
   ,     (..  
 ,     ;  -   
;      ).
    -        
,          10.5. 
   -     ,
        ? ,
   - add()      int
 main()?     -   
     (     
),   ,    
?       ,  
   ,       
    (    
-   )?
               C++,
     ,    
 .   (    ),  
 10.5,        -  
-  .       
       .

                 16.8.1.    

         -   
    ,   .   -
,    ,   .  

                                                              ++   825

          
 .         . ,
  Queue  QueueItem,    -  
,     Queue.h.
       :  -  
     ,   
     .  ,   
        
 .   (  )  
    (..   -  
-).

                     16.8.2.    

             -
   ,    - 
 -       .  ,
        ,  
  ( )   :

   // ---- Queue.h ----
   //  Queue    
   export template <class Type>
   class Queue {
      // ...
   public:
     Type& remove();
     void add( const Type & );
     // ...
   };

   // ---- Queue.C ----
   //     Queue
   //   Queue.h
   #include "Queue.h"

   template <class Type>
   void Queue<Type>::add( const Type &val ) { ... }
   template <class Type>
   Type& Queue<Type>::remove() { ... }

   ,     -,  
   :

                                                             ++   826

   // ---- User.C ----
   #include "Queue.h"

   int main() {
      //  Queue<int>
      Queue<int> *p_qi = new Queue<int>;
      int ival;
      // ...
      // :  Queue<int>::add( const int & )
      p_qi->add( ival );
      // ...
   }

       - add()     User.C,
  Queue<int>::add(const int &)  
.        .
     ,     - 
 -      .
      ,   .
       ,   template  
       export:

   export template <class Type>
   class Queue { ... };

       export     Queue   Queue.h;
     Queue.C,   - add() 
remove(),       
     .
   , ,     ,  
     User.C. 
Queue<int>::add()  User.C   ,   
- Queue<int>::add()  Queue<int>::remove().   
   .  ,  export  
  -   -.
         .   
  export     ,   
 . ,     Queue 
  - Queue<Type>::add() (..   
 Queue.h   ),   export    
 - add():

                                                              ++   827

   // ---- Queue.h ----
   template <class Type>
   class Queue {
      // ...
   public:
      Type& remove();
      void add( const Type & );
      // ...
   };

   // ,   remove()  
   template <class Type>
   Type& Queue<Type>::remove() { ... }

   // ---- Queue.C ----
   #include "Queue.h"
   //   - add()
   export template <class Type>
   void Queue<Type>::add( const Type &val ) { ... }

    ,     - remove()  
  Queue.h.  ,  remove()    
  , ,       
,    .
    -     
      .  
  ,      ,  
      .   
   :

       , ,    
          ;
           
      ,      
       ;
          
     ,   .

   ,  ,      
      
.  ,       , 
       .
              
  ,       , 
      .     
 ,  ,  ,     :  
    ,     
 C++.

                                                            ++   828

          ,     
   ,     
 .

                  16.8.3.   

            
   ,     .
 ,       , 
  (  )   
    .    
(         )   
 ,   .
         ,    :
      . ,   
           , 
   .
    ,    ,  
.     ,  
,   C++     ,  
  template   class     .
       Queue<int>,  
   int   Queue:

   #include "Queue.h"
   //   
   template class Queue<int>;

       ,       ,
    . ,  ,   
,      ,   
  .       :

   template <class Type>
   class Queue;
   // :  Queue     
   template class Queue<int>;

           ,  
   ,      ?
  ,          
           
?
   ,       (.  10.5.3), 
  ,   .  

                                                                ++   829

  ,     
 .

                                      16.9

        -   - 
 ,        
 ?  .

                                        16.10

      Screen,      
(   -,    16.5   16.3, 
 ,    16.7   16.5). 
 ,      
.

                         16.9.    A

            , 
     ,    Queue -
min()  max().          
     (, ,
      min()  max(),  
 12,         Queue,  
 .)

   template <class Type>
   class Queue {
      // ...
   public:
      Type min();
      Type max();
      // ...
   };

   //      Queue
   template <class Type>
   Type Queue<Type>::min()
   {
      assert( ! is_empty() );
      Type min_val = front->item;
      for ( QueueItem *pq = front->next; pq != 0; pq = pq->next )
         if ( pq->item < min_val )
            min_val = pq->item;
      return min_val;
   }

   //      Queue
   template <class Type>
   Type Queue<Type>::max()
   {
      assert( ! is_empty() );
      Type max_val = front->item;
      for ( QueueItem *pq = front->next; pq != 0; pq = pq->next )
         if ( pq->item > max_val )
            max_val = pq->item;
      return max_val;
   }

                                                       ++   830

      - min()     Queue:

   pq->item < min_val

        ,   
  Queue:       
     ,   , 
   operator<().     ,  
 min()         ,  
  . (     max(),
   operator>()).
   ,    Queue    :

   class LongSouble {
   public:
      LongDouble( double dbval ) : value( dval ) { }
      bool compareLess( const LongDouble & );
   private:
      double value;
   };

         operator<(),    
 LongDouble,      Queue<LongDouble> -
 min()  max() .        
 operator<()  operator>(),      
Queue<LongDouble>  - compareLess.  
    min()  max()     
.
       ,     :
   - min()  max()   
Queue  LongDouble    
Queue<LongDouble>::min()  Queue<LongDouble>::max(),   -
 compareLess()  LongDouble.
     ,     ,  
  template     <>,    
  .     - min()  max()
 Queue<LongDouble>,   ,  
:

                                                                ++   831

   //   
   template<> LongDouble Queue<LongDouble>::min()
   {
      assert( ! is_empty() );
      LongDouble min_val = front->item;
      for ( QueueItem *pq = front->next; pq != 0; pq = pq->next )
         if ( pq->item.compareLess( min_val ) )
            min_val = pq->item;
      return min_val;
   }

   template<> LongDouble Queue<LongDouble>::max()
   {
      assert( ! is_empty() );
      LongDouble max_val = front->item;
      for ( QueueItem *pq = front->next; pq != 0; pq = pq->next )
        if ( max_val.compareLess( pq->item ) )
           max_val = pq->item;
      return max_val;
   }

      Queue<LongDouble>   ,   
    - min()  max()   , 
         Queue.
       min()  max()   
 ,      :  
     .     
,  . :

   //    -
   template <> LongDouble Queue<LongDouble>::min();
   template <> LongDouble Queue<LongDouble>::max();

        ,     
,      ,     -
 .
          
 .        
.     Queue<LongDouble>:

                                                        ++   832

   // QueueLD.h:    Queue<LongDouble>
   #include "Queue.h"
   template<> Queue<LongDouble> {
      Queue<LongDouble>();
      ~Queue<LongDouble>();
      LongDouble& remove();
      void add( const LongDouble & );
      bool is_empty() const;
      LongDouble min();
      LongDouble max();
   private:
      //  
   };

           ,  
    (    ).  , 
 ,      .  
      Queue.h  
  ,     , , 
Queue     .
         ,    
   -   -.   
         
:      . 
       Queue<LongDouble>,
    - min()  max(),    .
   ,  template<>   
    :

   #include "QueueLD.h"
   //  - min()
   //    
   LongDouble Queue<LongDouble>::min() { }

             ,  
   ,        .
,   QueueItem<LongDouble>   
 ,   :

   // ---- File1.C ----
   #include "Queue.h"
   void ReadIn( Queue<LongDouble> *pq ) {
      //  pq->add()
      //    QueueItem<LongDouble>
   }

                                                             ++   833

   // ---- File2.C ----
   #include "QueueLD.h"
   void ReadIn( Queue<LongDouble> * );

   int main() {
      //     Queue<LongDouble>
      Queue<LongDouble> *qld = new Queue<LongDouble>;
      ReadIn( qld );
      // ...
   }

     ,      :
  QueueLD.h     ,  
Queue<LongDouble>,    .

                16.10.     A

         ,    
     ,   .
 ,   ,    , 
 ,       . 
      .  
   ,     
.
      Screen,    16.2.  
Screen<hi,80>        80 :

   template <int hi, int wid>
   class Screen {
      // ...
   };

   //     Screen
   template <int hi>
   class Screen<hi, 80> {
   public:
      Screen();
      // ...
   private:
      string _screen;
      string::size_type _cursor;
      short _height;
      //    80    
   };

         ,     
 .      template,   
 ,    .    
     .   
 Screen    - hi,   

                                                              ++   834
  80, ..       ,  
   .
           ,  
,    Screen.       
.        <hi,80>.  
     ,       
  ;      80,  
 .
           
.      
  24  hi:

   Screen<24,80> hp2621;

    ,   Screen<24,80>    
   ,     .   
     ?    
  ,    , 
     .     
  ,    . , 
  Screen<40,132>   
 .        Screen 
80 .
           . 
      ,    
-,     .   
         
 . ,    Screen<hi,80>
    :

   //     Screen<hi,80>
   template <int hi>
   Screen<hi,80>::Screen() : _height( hi ), _cursor( 0 ),
                             _screen( hi * 80, bk )
      { }

          , 
        , 
  Screen<hi,80> .

                16.11.      A

          (.  10.9)  
  ,       .      
     .      
:    ,           ,
    ,        
.   ,   - remove()
  Queue:

                                                                ++   835

   // Queue.h:
   #include <iostream>
   #include <cstdlib>

   //   Queue
   template <class Type>
   Type Queue<Type>::remove() {
      if ( is_empty() ) {
         cerr << "remove()    \n";
         exit(-1);
      }
      QueueItem<Type> *pt = front;
      front = front->next;
      Type retval = pt->item;
      delete pt;

      cout << " : ";
      cout << retval << endl;

      return retval;
   }

    

   cout << retval << endl;

 retval   Type,       
- remove(). ,   operator<<()  ,  
  retval,   Type.   
remove()    operator<<().   ,  
     .
       exit()  .    
,       remove(). 
      ,    
  Type, ,     exit(),
    cstdlib.      

   cout << " : ";

   

   ostream& operator<<( ostream &, const char * );

    " : "  C- ,      
  Type.     
remove() operator<<()   .      
     ,     
.
    ,          
   :

   ,     ,    
    .

                                                            ++   836

   ,    ,    
    .

         ,   
. ,     
.       ,    
   ,  ,      
       . 
    .    
      ,     
  ,    ,  
 .
        ,      
    ,    . 
    ,     .
    - remove()    Queue  
  iostream  cstdlib,   

   cout << " : ";

     exit()    .
       ,      
,   ,   . , 
  Queue    LongDouble (.  16.9), 
,   - remove()  

   cout << retval << endl;

  operator<<(),    LongDouble:

   #include "Queue.h"
   #include "ldouble.h"
   // :
   // class LongDouble { ... };
   // ostream& operator<<( ostream &, const LongDouble & );

   int main() {
      //  Queue<LongDouble>
      Queue<LongDouble> *qld = new Queue<LongDouble>;
      //  Queue<LongDouble>::remove()
      //     LongDouble
      qld->remove();
      // ...
   }

  ,    ,  
.  ,     
  ,    .
         
     ,   

                                                              ++   837

 .   -  
         ,
    .
        Queue<LongDouble>  
main(),       ,   
  Queue,       .
      remove()  
    ,   main().
       16.2,  ,    
,    .    
   ,   ,     .
         
  ,         .
  ,  ,      
,     ,    
       .

                           16.12.     

          ,   
    . (   
 8.5  8.6.)        ;   
  ,       . 
         ,
  using-:

   #include <iostream>
   #include <cstdlib>

   namespace cplusplus_primer {

      template <class Type>
      class Queue { // ...
      };

      template <class Type>
      Type Queue<Type>::remove()
      {
         // ...
      }
   }

     Queue      
cplusplus_primer,          
 using-.      Queue 
,   : ,   -, 
,    .. :

                                                          ++   838

    cplusplus_primer::Queue<int> ,    
 new:

   int main() {
      using cplusplus_primer Queue; // using-
      //        cplusplus_primer
      Queue<int> *p_qi = new Queue<int>;
      // ...
      p_qi->remove();
   }

   ... = new Queue<int>;

p_qi       cplusplus_primer::Queue<int>.  
   - remove(),       
  .
            
         (. 
16.9  16.10).          ,
   .
         cplusplus_primer 
   Queue<char *>  - remove() 
Queue<double>:

   #include <iostream>
   #include <cstdlib>

   namespace cplusplus_primer {
      template <class Type>
      class Queue { ... };

      template <class Type>
      Type Queue<Type>::remove() { ... }

      //  
      //  cplusplus_primer::Queue<char *>
      template<> class Queue<char*> { ... };

      //  
      //  - cplusplus_primer::Queue<double>::remove()
      template<> double Queue<double>::remove() { ... }
   }

       cplusplus_primer,    
 .      
   ,      
,  cplusplus_primer,    
   :

                                                       ++   839

   namespace cplusplus_primer
   {
      //  Queue   -
   }

   //  
   // cplusplus_primer::Queue<char*>
   template<> class cplusplus_primer::Queue<char*> { ... };
   //   -
   // cplusplus_primer::Queue<double>::remove()
   template<> double cplusplus_primer::Queue<double>::remove()
   { ... }

      cplusplus_primer::Queue<char*>  -
remove()   cplusplus_primer::Queue<double>   
 .      
cplusplus_primer,      , 
    Queue  .


                              16.13.   Array

           Array,    2.5
(         18.3  
    18.6).     :

                                                                  ++   840

   #ifndef ARRAY_H
   #define ARRAY_H
   #include <iostream>

   template <class elemType> class Array;
   template <class elemType> ostream&
      operator<<( ostream &, Array<elemType> & );

   template <class elemType>
   class Array {
   public:
      explicit Array( int sz = DefaultArraySize )
         { init( 0, sz ); }

      Array( const elemType *ar, int sz )
         { init( ar, sz ); }

      Array( const Array &iA )
         { init( iA._ia, iA._size ); }

      ~Array() { delete[] _ia; }

      Array & operator=( const Array & );
      int size() const { return _size; }

      elemType& operator[]( int ix ) const
      { return _ia[ix]; }

      ostream &print( ostream& os = cout ) const;
      void grow();

      void sort( int,int );
      int find( elemType );
      elemType min();
      elemType max();
   private:
      void init( const elemType*, int );
      void swap( int, int );

      static const int DefaultArraySize = 12;

      int _size;
      elemType *_ia;
   };

   #endif

   ,      ,    -
 init().        
 Array,      :

                                                            ++   841

   template <class elemType>
   void Array<elemType>::init( const elemType *array, int sz )
   {
      _size = sz;
      _ia = new elemType[ _size ];
       
      for ( int ix = 0; ix < _size; ++ix )
         if ( ! array )
            _ia[ ix ] = 0;
         else _ia[ ix ] = array[ ix ];
   }

         . 
   14.7,          :

   template <class elemType> Array<elemType>&
      Array<elemType>::operator=( const Array<elemType> &iA )
   {
      if ( this != &iA ) {
         delete[] _ia;
         init( iA._ia, iA._size );
      }
      return *this;
   }

   - print()      ,  
 Array. ,   ,  ,  
   .    
Array<int>   3, 5, 8, 13  21,     :

   (5) < 3, 5, 8, 13, 21 >

        print().  
  :

                                                          ++   842

   template <class elemType> ostream&
      operator<<( ostream &os, Array<elemType> &ar )
   {
      return ar.print( os );
   }

   template <class elemType>
      ostream & Array<elemType>::print( ostream &os ) const
   {
      const int lineLength = 12;

      os << "( " << _size << " )< ";
      for ( int ix = 0; ix < _size; ++ix )
      {
         if ( ix % lineLength == 0 && ix )
            os << "\n\t";
         os << _ia[ ix ];

         //        ,
         //      
         if ( ix % lineLength != lineLength-1 && ix != _size-1 )
            os << ", ";
      }

      os << " >\n";
      return os;
   }

         print()   :

   os << _ia[ ix ];

           , 
  Array:       
  .      
  Array       ,  
 .
   - grow()     Array.     
 :

                                                              ++   843

   template <class elemType>
   void Array<elemType>::grow()
   {
      elemType *oldia = _ia;
      int oldSize = _size;

      _size = oldSize + oldSize/2 + 1;
      _ia = new elemType[_size];

      int ix;
      for ( ix = 0; ix < oldSize; ++ix )
         _ia[ix] = oldia[ix];

      for ( ; ix < _size; ++ix )
         _ia[ix] = elemType();

      delete[] oldia;
   }

   - find(), min()  max()    
  _ia.     , , ,   
   .

   template <class elemType>
   elemType Array<elemType>::min( )
   {
      assert( _ia != 0 );
      elemType min_val = _ia[0];
      for ( int ix = 1; ix < _size; ++ix )
         if ( _ia[ix] < min_val )
            min_val = _ia[ix];
       
      return min_val;
   }

   template <class elemType>
   elemType Array<elemType>::max()
   {
      assert( _ia != 0 );
      elemType max_val = _ia[0];

      for ( int ix = 1; ix < _size; ++ix )
         if ( max_val < _ia[ix] )
           max_val = _ia[ix];

      return max_val;
   }

   template <class elemType>
   int Array<elemType>::find( elemType val )
   {
      for ( int ix = 0; ix < _size; ++ix )
         if ( val == _ia[ix] )
            return ix;
      return -1;
   }

                                                           ++   844

      Array  - sort(),   
  .      , 
  10.11. - swap()     sort();  
          :

   template <class elemType>
   void Array<elemType>::swap( int i, int j )
   {
      elemType tmp = _ia[i];
      _ia[i] = _ia[j];
      _ia[j] = tmp;
   }

   template <class elemType>
   void Array<elemType>::sort( int low, int high )
   {
      if ( low >= high ) return;
      int lo = low;
      int hi = high + 1;
      elemType elem = _ia[low];

      for ( ;; ) {
         while ( _ia[++lo] < elem ) ;
         while ( _ia[--hi] > elem ) ;
         if ( lo < hi )
            swap( lo,hi );
         else break;
      }

      swap( low, hi );
      sort( low, hi-1 );
      sort( hi+1, high );
   }

   ,   , ,  ,   . try_array() 
  ,      Array:

                                                             ++   845

   #include "Array.h"
   template <class elemType>
      void try_array( Array<elemType> &iA )
   { 
      cout << "try_array:   \n";
      cout << iA << endl;

      elemType find_val = iA [ iA.size()-1 ];
      iA[ iA.size()-1 ] = iA.min();

      int mid = iA.size()/2;
      iA[0] = iA.max();
      iA[mid] = iA[0];
      cout << "try_array:  \n";
      cout << iA << endl;

      Array<elemType> iA2 = iA;
      iA2[mid/2] = iA2[mid];
      cout << "try_array:  \n";
      cout << iA << endl;

      iA = iA2;
      cout << "try_array:   \n";
      cout << iA << endl;

      iA.grow();
      cout << "try_array:   grow\n";
      cout << iA << endl;
      int index = iA.find( find_val );
      cout << " : " << find_val;
      cout << "\t : " << index << endl;

      elemType value = iA[index];
      cout << "    : ";
      cout << value << endl;
  }

      try_array().      
Array,       ,  
  ,       
.   find_val  ,   
 find().   try_array()   ,   
  .         ,
   ,     .
   Array     
,   min(), max(), size() , ,  
.
     iA2    iA,    
 .        
ia2:      mid/2. (  
   ,  iA    Array,   
   .       18 
 .)   iA    
iA2,         Array. 
 - grow()  find(). ,  find() 
 1,     .     Array

                                                              ++   846

   1      . (  18  
      Array ,    
  .)
   ,         ,
  ,      ,   main(),
  try_array()     :

   #include "Array.C"
   #include "try_array.C"
   #include <string>

   int main()
   {
      static int ia[] = { 12,7,14,9,128,17,6,3,27,5 };
      static double da[] = { 12.3,7.9,14.6,9.8,128.0 };
      static string sa[] = {
         "Eeyore", "Pooh", "Tigger",
         "Piglet", "Owl", "Gopher", "Heffalump"
      };
      Array<int> iA( ia, sizeof(ia)/sizeof(int) );
      Array<double> dA( da, sizeof(da)/sizeof(double) );
      Array<string> sA( sa, sizeof(sa)/sizeof(string) );

      cout << "template Array<int> class\n" << endl;
      try_array(iA);

      cout << "template Array<double> class\n" << endl;
      try_array(dA);

     cout << "template Array<string> class\n" << endl;
     try_array(sA);

      return 0;
   }

          Array  double:

   try_array:   
   ( 5 )< 12.3, 7.9, 14.6, 9.8, 128 >

   try_array:  
   ( 5 )< 14.6, 7.9, 14.6, 9.8, 7.9 >

   try_array:  
   ( 5 )< 14.6, 7.9, 14.6, 9.8, 7.9 >

   try_array:   
   ( 5 )< 14.6, 14.6, 14.6, 9.8, 7.9 >

   try_array:   grow
   ( 8 )< 14.6, 14.6, 14.6, 9.8, 7.9, 0, 0, 0 >

    : 128  : -1
       : 3.35965e-322

          ,   
  .   Array  string
  :

                                                          ++   847

   template Array<string> class

   try_array:   
   ( 7 )< Eeyore, Pooh, Tigger, Piglet, Owl, Gopher, Heffalump >

   try_array:  
   ( 7 )< Tigger, Pooh, Tigger, Tigger, Owl, Gopher, Eeyore >

   try_array:  
   ( 7 )< Tigger, Pooh, Tigger, Tigger, Owl, Gopher, Eeyore >

   try_array:   
   ( 7 )< Tigger, Tigger, Tigger, Tigger, Owl, Gopher, Eeyore >

   try_array:   grow
   ( 11 )< Tigger, Tigger, Tigger, Tigger, Owl, Gopher, Eeyore, <>, <>,
   <>, <> >
  
    : Heffalump  : -1
   Memory fault (coredump)

                                   16.11

      Array,    - sort(), find(), max(),
min()  swap(),    try_array() ,    
   (.  12).
