                                                        ++   1088



                21.     

          .    
       (  ),    
    .      :  
     ,   ,    
      , , ,  
    , ,     .

         (,  
)   ,  first  last,  
     ,   
.   (     
),  ,   :

   //  :  first   
   //   last,     last
   [ first, last )

    ,     first   last,  
 last  . 

   first == last

 ,   .
        : last   , 
  first     . 
      .   
 ,    ;    
   .
         , 
   (     . 
 12.4). ,  find(),   
    ,    InputIterator.
    -      
 .       . 
,    (   
)   ,      
 ,   ,    .
        :    
   ,     -   
,    . ,  unique()
        

                                                               ++   1089

,   ,     .  
           
,    -    ,
  .    ,  
 ,    . ,   
    _if,  find_if(). ,  
 replace(),     ,   
 replace_if(),    - 
  -.
   ,  ,      :
    ,      
. ,   replace()  replace_copy().   
 (     _copy)    
,  .  ,   sort()  .
  ,  ,     ,    
     .
           
 

   #include <algorithm>

      :
adjacent_difference(), accumulate(), inner_product()  partial_sum() 
   

   #include <numeric>

        ,   
    ,    
  .   / iostream 
,    ; ,   
  iostream.h,   iostream.   
  .     ,   ,
,    .
   ,  ,    ,    
   [MUSSER96], ,     
   C++.

                                 accumulate()

                                                             ++   1090

   template < class InputIterator, class Type >
   Type accumulate(
      InputIterator first, InputIterator last,
      Type init );

   template < class InputIterator, class Type,
                   class BinaryOperation >
   Type accumulate(
      InputIterator first, InputIterator last,
      Type init, BinaryOperation op );

     accumulate()    
  ,    [first,last), 
 ,    init. ,  
 {1,1,2,3,5,8}    0,   
  20.        
   .     
accumulate() - times<int>    1,   
 240. accumulate()      ;  
       <numeric>.

   #include <numeric>
   #include <list>
   #include <functional>
   #include <iostream.h>
   /*
    * :
    * accumulate()
    *    {1,2,3,4}
    *     : 10
    *   - plus<int>: 10
    */

   int main()
   {
      int ia[] = { 1, 2, 3, 4 };
      list<int,allocator> ilist( ia, ia+4 );

      int ia_result = accumulate(&ia[0], &ia[4], 0);
      int ilist_res = accumulate(
         ilist.begin(), ilist.end(), 0, plus<int>() );

      cout << "accumulate()\n\t"
             << "   {1,2,3,4}\n\t"
             << "    : "
             << ia_result << "\n\t"
             << "  - plus<int>: "
             << ilist_res
             << endl;

   return 0;
   }

                                                        ++   1091

                               adjacent_difference()

   template < class InputIterator, class OutputIterator >
   OutputIterator adjacent_difference(
      InputIterator first, InputIterator last,
      OutputIterator result );

   template < class InputIterator, class OutputIterator >
                    class BinaryOperation >
   OutputIterator adjacent_difference(
       InputIterator first, InputIterator last,
      OutputIterator result, BinaryOperation op );

     adjacent_difference()   , 
   ,  ,     
   . ,  
{0,1,1,2,3,5,8},       : 0.
       : 1. 
      : 1-1=0,  ..   
  {0,1,0,1,1,2,3}.
            
 .        -
 times<int>.   ,    . 
         ;
   0.        
 : 1 * 1 = 1,  ..   {0,1,2,6,15,40}.
       OutputIterator   ,  
   . adjacent_difference()   
  ,       
  <numeric>.

                                                          ++   1092

   #include <numeric>
   #include <list>
   #include <functional>
   #include <iterator>
   #include <iostream.h>

   int main()
   {
      int ia[] = { 1, 1, 2, 3, 5, 8 };

      list<int,allocator> ilist(ia, ia+6);
      list<int,allocator> ilist_result(ilist.size());

      adjacent_difference(ilist.begin(), ilist.end(),
                                   ilist_result.begin() );

      //   :
      // 1 0 1 1 2 3
      copy( ilist_result.begin(), ilist_result.end(),
               ostream_iterator<int>(cout," "));
      cout << endl;

      adjacent_difference(ilist.begin(), ilist.end(),
                                   ilist_result.begin(), times<int>() );

      //   :
      // 1 1 2 6 15 40
      copy( ilist_result.begin(), ilist_result.end(),
               ostream_iterator<int>(cout," "));

      cout << endl;
   }

                          adjacent_find()

   template < class ForwardIterator >
   ForwardIterator
   adjacent_find( ForwardIterator first, ForwardIterator last );

   template < class ForwardIterator, class BinaryPredicate >
   ForwardIterator
   adjacent_find( ForwardIterator first,
      ForwardIterator last, Predicate pred );

   adjacent_find()        ,
  [first,last).    , 
   ,    
,     last. ,   
{0,1,1,2,2,4},     [1,1]   ,  
 .

                                                            ++   1093

   #include <algorithm>
   #include <vector>
   #include <iostream.h>
   #include <assert.h>

   class TwiceOver {
   public:
      bool operator() ( int val1, int val2 )
      { return val1 == val2/2 ? true : false; }
   };

   int main()
   {
      int ia[] = { 1, 4, 4, 8 };
      vector< int, allocator > vec( ia, ia+4 );

      int *piter;
      vector< int, allocator >::iterator iter;

      // piter   ia[1]
      piter = adjacent_find( ia, ia+4 );
      assert( *piter == ia[ 1 ] );

      // iter   vec[2]
      iter = adjacent_find( vec.begin(), vec.end(), TwiceOver() );
      assert( *iter == vec[ 2 ] );

       //  :  
       cout << "ok: adjacent-find()  !\n";
       return 0;
   }

                                 binary_search()

   template < class ForwardIterator, class Type >
   bool
   binary_search( ForwardIterator first,
                          ForwardIterator last, const Type &value );

   template < class ForwardIterator, class Type >
   bool
   binary_search( ForwardIterator first,
                         ForwardIterator last, const Type &value,
             Compare comp );

   binary_search()   value   ,
   [first,last).    ,
 true,   false.    ,  
    .    
  -.

                                                       ++   1094

   #include <algorithm>
   #include <vector>
   #include <assert.h>

   int main()
   {
      int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};
      vector< int, allocator > vec( ia, ia+12 );

      sort( &ia[0], &ia[12] );
      bool found_it = binary_search( &ia[0], &ia[12], 18 );
      assert( found_it == false );

      vector< int > vec( ia, ia+12 );
      sort( vec.begin(), vec.end(), greater<int>() );
              found_it = binary_search( vec.begin(), vec.end(),
              26, greater<int>() );
      assert( found_it == true );
   }

                                      copy()

   template < class InputIterator, class OutputIterator >
   OutputIterator
   copy( InputIterator first1, InputIterator last,
         OutputIterator first2 )

   copy()   ,   
[first,last),   ,   ,    first2.
  ,     ,
   . ,   
{0,1,2,3,4,5},           :

   int ia[] = {0, 1, 2, 3, 4, 5 };
   //     ,  {1,2,3,4,5,5}
   copy( ia+1, ia+6, ia );

   copy()      ia,  1   , 
 ,           .

                                                                ++   1095

   #include <algorithm>
   #include <vector>
   #include <iterator>
   #include <iostream.h>

   /* :
          0 1 1 3 5 8 13
           1:
          1 1 3 5 8 13 13
          2:
         1 3 5 8 13 8 13
   */

   int main()
   {
      int ia[] = { 0, 1, 1, 3, 5, 8, 13 };
      vector< int, allocator > vec( ia, ia+7 );
      ostream_iterator< int > ofile( cout, " " );
      cout << "  :\n";
      copy( vec.begin(), vec.end(), ofile ); cout << '\n';

      //     
      copy( ia+1, ia+7, ia );
      cout << "    1:\n";
      copy( ia, ia+7, ofile ); cout << '\n';

      //     
      copy( vec.begin()+2, vec.end(), vec.begin() );
      cout << "    2:\n";
      copy( vec.begin(), vec.end(), ofile ); cout << '\n';

   }


                                 copy_backward()

   template < class BidirectionalIterator1,
                    class BidirectionalIterator2 >
   BidirectionalIterator2
   copy_backward( BidirectionalIterator1 first,
                            BidirectionalIterator1 last1,
               BidirectionalIterator2 last2 )

   copy_backward()    ,  copy(),    
 :    last1-1    first. 
,       ,   last2-1,  
  last1-first .
   ,    {0,1,2,3,4,5},   
   (3,4,5)     (0,1,2),  first 
  0, last1    3,  last2    5. 

                                                            ++   1096

 5     2,  4    1,   3   
0.     {3,4,5,3,4,5}.

   #include <algorithm>
   #include <vector>
   #include <iterator>
   #include <iostream.h>

   class print_elements {
   public:
      void operator()( string elem ) {
         cout << elem
                << ( _line_cnt++%8 ? " " : "\n\t" );
      }
      static void reset_line_cnt() { _line_cnt = 1; }
   private:
      static int _line_cnt;
   };

      int print_elements::_line_cnt = 1;
      /* :
           :
         The light untonsured hair grained and hued like
         pale oak
         copy_backward( begin+1, end-3, end ):
        The light untonsured hair light untonsured hair grained
        and hued
   */

   int main()
  {
      string sa[] = {
           "The", "light", "untonsured", "hair",
           "grained", "and", "hued", "like", "pale", "oak" };

      vector< string, allocator > svec( sa, sa+10 );
      cout << "  :\n\t";
      for_each( svec.begin(), svec.end(), print_elements() );
      cout << "\n\n";
      copy_backward( svec.begin()+1, svec.end()-3, svec.end() );
      print_elements::reset_line_cnt();
      cout << " copy_backward( begin+1, end-3, end ):\n";
      for_each( svec.begin(), svec.end(), print_elements() );
      cout << "\n";
   }
                                                          ++   1097

                           count()

   template < class InputIterator, class Type >
   iterator_traits<InputIterator>::distance_type
   count( InputIterator first,
      InputIterator last, const Type& value );

   count()      value  , 
  [first,last),    . 
  ,  value. (,     
      
count().)

                                                              ++   1098


   #include <algorithm>
   #include <string>
   #include <list>
   #include <iterator>
   #include <assert.h>
   #include <iostream.h>
   #include <fstream.h>

   /***********************************************************************
   *  :
     Alice Emma has long flowing red hair. Her Daddy says
     when the wind blows through her hair, it looks almost alive,
     like a fiery bird in flight. A beautiful fiery bird, he tells her,
     magical but untamed. "Daddy, shush, there is no such thing,"
     she tells him, at the same time wanting him to tell her more.
     Shyly, she asks, "I mean, Daddy, is there?"
   ************************************************************************
   *  :
   * count(): fiery  2 ()
   ************************************************************************
   */

   int main()
   {
      ifstream infile( "alice_emma" );
      assert ( infile != 0 );
      list<string,allocator> textlines;
      typedef list<string,allocator>::difference_type diff_type;
      istream_iterator< string, diff_type > instream( infile ),
         eos;
      copy( instream, eos, back_inserter( textlines ));
      string search_item( "fiery" );

   /*************************************************************
    * :    count(),  
    *  .    
    *  RogueWave    ,  
    *  distance_type   ,   count()
    *     
    *
    *     :
    *
    * typedef iterator_traits<InputIterator>::
    * distance_type dis_type;
    *
    * dis_type elem_count;
    * elem_count = count( textlines.begin(), textlines.end(),
    * search_item );
    **************************************************************

   int elem_count = 0;
   list<string,allocator>::iterator
   ibegin = textlines.begin(),
   iend = textlines.end();

   //   count()
   count( ibegin, iend, search_item, elem_count );
   cout << "count(): " << search item

                                                        ++   1099

   }

 
                             count_if()

   template < class InputIterator, class Predicate >
   iterator_traits<InputIterator>::distance_type
   count_if( InputIterator first,
      InputIterator last, Predicate pred );

   count_if()   pred     ,
   [first,last).  ,  
   true.

                                                         ++   1100

   #include <algorithm>
   #include <list>
   #include <iostream.h>

   class Even {
   public:
      bool operator()( int val )
      { return val%2 ? false : true; }
   };

   int main()
   {
      int ia[] = {0,1,1,2,3,5,8,13,21,34};
      list< int,allocator > ilist( ia, ia+10 );

   /*
    *     
    *****************************************************
   typedef
   iterator_traits<InputIterator>::distance_type
   distance_type;
   distance_type ia_count, list_count;
   //   : 4
   ia_count = count_if( &ia[0], &ia[10], Even() );
   list_count = count_if( ilist.begin(), ilist_end(),
   bind2nd(less<int>(),10) );
   ******************************************************
   */

   int ia_count = 0;
   count_if( &ia[0], &ia[10], Even(), ia_count );

      // :
      // count_if():  4  ().
      cout << "count_if():  "
            << ia_count << "  ().\n";
      int list_count = 0;
      count_if( ilist.begin(), ilist.end(),
      bind2nd(less<int>(),10), list_count );

      // :
      // count_if():  7 (),  10.
      cout << "count_if():  "
             << list_count
             << " (),  10.\n";
   }

                                                             ++   1101

                                      equal()

   template< class InputIterator1, class InputIterator2 >
   bool
   equal( InputIterator1 first1,
      InputIterator1 last, InputIterator2 first2 );
   template< class InputIterator1, class InputIterator2,
      class BinaryPredicate >
   bool
   equal( InputIterator1 first1, InputIterator1 last,
      InputIterator2 first2, BinaryPredicate pred );

   equal()  true,      ,
   [first,last).   
  ,  .   
  ,  :

   if ( vec1.size() == vec2.size() &&
   equal( vec1.begin(), vec1.end(), vec2.begin() );

   ,     :
vec1 == vec2.      ,  , 
      ,  
  .      
    ,       
 pred.

                                                              ++   1102

   #include <algorithm>
   #include <list>
   #include <iostream.h>

   class equal_and_odd{
   public:
      bool
      operator()( int val1, int val2 )
      {
         return ( val1 == val2 &&
            ( val1 == 0 || val1 % 2 ))
            ? true : false;
      }
   };

   int main()
   {
       int ia[] = { 0,1,1,2,3,5,8,13 };
       int ia2[] = { 0,1,1,2,3,5,8,13,21,34 };
       bool res;
       // true:      ia
       // : int ia[7]  int ia2[9]? .
       res = equal( &ia[0], &ia[7], &ia2[0] );
       cout << "int ia[7]  int ia2[9]? "
              << ( res ? "" : "" ) << ".\n";
      list< int, allocator > ilist( ia, ia+7 );
      list< int, allocator > ilist2( ia2, ia2+9 );
      // :  ilist  ilist2? .
      res = equal( ilist.begin(), ilist.end(), ilist2.begin() );
      cout << " ilist  ilist2? "
             << ( res ? "" : "" ) << ".\n";
      // false: 0, 2, 8     
      // :  ilist equal_and_odd() ilist2? .
      res = equal( ilist.begin(), ilist.end(),
      ilist2.begin(), equal_and_odd() );
      cout << " ilist equal_and_odd() ilist2? "
             << ( res ? "" : "" ) << ".\n";
     return 0;
   }
                                                           ++   1103

                               equal_range()

   template< class ForwardIterator, class Type >
   pair< ForwardIterator, ForwardIterator >
   equal_range( ForwardIterator first,
       ForwardIterator last, const Type &value );

   template< class ForwardIterator, class Type, class Compare >
   pair< ForwardIterator, ForwardIterator >
   equal_range( ForwardIterator first,
        ForwardIterator last, const Type &value,
      Compare comp );

   equal_range()   :    ,
  lower_bound(),    upper_bound(). (
      .) , 
:

   int ia[] = {12,15,17,19,20,22,23,26,29,35,40,51};

     equal_range()   21   ,  
    22.     22  
,  first   22,  second   23.    
   ,    
;     comp.

                                                              ++   1104


   #include <algorithm>
   #include <vector>
   #include <utility>
   #include <iostream.h>

   /* :
          :
      12 15 17 19 20 22 23 26 29 35 40 51

       equal_range    23:
       *ia_iter.first: 23 *ia_iter.second: 26

      equal_range     21:
      *ia_iter.first: 22 *ia_iter.second: 22

         :
       51 40 35 29 26 23 22 20 19 17 15 12

      equal_range    26:
       *ivec_iter.first: 26 *ivec_iter.second: 23

      equal_range     21:
       *ivec_iter.first: 20 *ivec_iter.second: 20
    */

   int main()
   {
      int ia[] = { 29,23,20,22,17,15,26,51,19,12,35,40 };
      vector< int, allocator > ivec( ia, ia+12 );
      ostream_iterator< int > ofile( cout, " " );

      sort( &ia[0], &ia[12] );

      cout << "    :\n";
      copy( ia, ia+12, ofile ); cout << "\n\n";

      pair< int*,int* > ia_iter;
      ia_iter = equal_range( &ia[0], &ia[12], 23 );

      cout << " equal_range    23:\n\t"
           << "*ia_iter.first: " << *ia_iter.first << "\t"
           << "*ia_iter.second: " << *ia_iter.second << "\n\n";

      ia_iter = equal_range( &ia[0], &ia[12], 21 );

      cout << " equal_range   "
           << "  21:\n\t"
           << "*ia_iter.first: " << *ia_iter.first << "\t"
           << "*ia_iter.second: " << *ia_iter.second << "\n\n";

      sort( ivec.begin(), ivec.end(), greater<int>() );

      cout << "    :\n";
      copy( ivec.begin(), ivec.end(), ofile ); cout << "\n\n";

      typedef vector< int, allocator >::iterator iter_ivec;
      pair< iter_ivec, iter_ivec > ivec_iter;

      ivec_iter = equal_range( ivec.begin(), ivec.end(), 26,
                               greater<int>() );

      cout << " equal_range    26:\n\t"
           << "*ivec_iter.first: " << *ivec_iter.first << "\t"
           << "*ivec_iter.second: " << *ivec_iter.second
           << "\n\n";

      ivec_iter = equal_range( ivec.begin(), ivec.end(), 21,
                               greater<int>() );

      cout << " equal_range    
              21:\n\t"
           << "*ivec_iter.first: " << *ivec_iter.first << "\t"
           << "*ivec iter.second: " << *ivec iter.second

                                                           ++   1105

}

                                fill()

   template< class ForwardIterator, class Type >
   void
   fill( ForwardIterator first,
      ForwardIterator last, const Type& value );

   fill()    value    , 
  [first,last).

                                                             ++   1106

   #include <algorithm>
   #include <list>
   #include <string>
   #include <iostream.h>

   /* :
         :
      0 1 1 2 3 5 8

        fill(ia+1,ia+6):
      0 9 9 9 9 9 8

         :
      c eiffel java ada perl

        fill(++ibegin,--iend):
      c c++ c++ c++ perl
    */

   int main()
   {
      const int value = 9;
      int ia[] = { 0, 1, 1, 2, 3, 5, 8 };
      ostream_iterator< int > ofile( cout, " " );

      cout << "   :\n";
      copy( ia, ia+7, ofile ); cout << "\n\n";

      fill( ia+1, ia+6, value );

      cout << "  fill(ia+1,ia+6):\n";
      copy( ia, ia+7, ofile ); cout << "\n\n";

      string the_lang( "c++" );
      string langs[5] = { "c", "eiffel", "java", "ada", "perl" };

      list< string, allocator > il( langs, langs+5 );
      ostream_iterator< string > sofile( cout, " " );

      cout << "   :\n";
      copy( il.begin(), il.end(), sofile ); cout << "\n\n";

      typedef list<string,allocator>::iterator iterator;

      iterator ibegin = il.begin(), iend = il.end();
      fill( ++ibegin, --iend, the_lang );

      cout << "  fill(++ibegin,--iend):\n";
      copy( il.begin(), il.end(), sofile ); cout << "\n\n";

   }

                                 fill_n()

                                                            ++   1107

   template< class ForwardIterator, class Size, class Type >
   void
   fill_n( ForwardIterator first,
      Size n, const Type& value );

   fill_n()  count    [first,first+count) 
value.

                                                              ++   1108

   #include <algorithm>
   #include <vector>
   #include <string>
   #include <iostream.h>

   class print_elements {
   public:
      void operator()( string elem ) {
         cout << elem
              << ( _line_cnt++%8 ? " " : "\n\t" );
      }

     static void reset_line_cnt() { _line_cnt = 1; }
  private:
     static int _line_cnt;
   };

   int print_elements::_line_cnt = 1;

   /* :
         :
      0 1 1 2 3 5 8

        fill_n( ia+2, 3, 9 ):
      0 1 9 9 9 5 8

        :
      Stephen closed his eyes to hear his boots
      crush crackling wrack and shells

         fill_n():

      Stephen closed his xxxxx xxxxx xxxxx xxxxx xxxxx
      xxxxx crackling wrack and shells
   */

   int main()
   {
      int value = 9; int count = 3;
      int ia[] = { 0, 1, 1, 2, 3, 5, 8 };
      ostream_iterator< int > iofile( cout, " " );

      cout << "   :\n";
      copy( ia, ia+7, iofile ); cout << "\n\n";

      fill_n( ia+2, count, value );

      cout << "  fill_n( ia+2, 3, 9 ):\n";
      copy( ia, ia+7, iofile ); cout << "\n\n";

      string replacement( "xxxxx" );
      string sa[] = { "Stephen", "closed", "his", "eyes", "to",
                      "hear", "his", "boots", "crush", "crackling",
                      "wrack", "and", "shells" };

     vector< string, allocator > svec( sa, sa+13 );

     cout << "  :\n\t";
     for_each( svec.begin(), svec.end(), print_elements() );
     cout << "\n\n";

      fill_n( svec.begin()+3, count*2, replacement );

      print_elements::reset_line_cnt();

      cout << "   fill_n():\n\t";
      for_each( svec.begin(), svec.end(), print_elements() );
      cout << "\n";

                                                              ++   1109

   }

                               find()

   template< class InputIterator, class T >
   InputIterator
   find( InputIterator first,
       InputIterator last, const T &value );

     ,    [first,last),
   value    ,  
  .    ,  .
find()    InputIterator,   
;     last.

   #include <algorithm>
   #include <iostream.h>
   #include <list>
   #include <string>

   int main()
   {
      int array[ 17 ] = { 7,3,3,7,6,5,8,7,2,1,3,8,7,3,8,4,3 };

      int elem = array[ 9 ];
      int *found_it;

      found_it = find( &array[0], &array[17], elem );

      // :    1 !
      cout << "   "
             << elem << "\t"
             << ( found_it ? "!\n" : " !\n" );

      string beethoven[] = {
           "Sonata31", "Sonata32", "Quartet14", "Quartet15",
           "Archduke", "Symphony7" };

      string s_elem( beethoven[ 1 ] );
      list< string, allocator > slist( beethoven, beethoven+6 );
      list< string, allocator >::iterator iter;

      iter = find( slist.begin(), slist.end(), s_elem );
      // :    Sonata32 !

      cout << "   "
             << s_elem << "\t"
             << ( found_it ? "!\n" : " !\n" );
   }

                                                               ++   1110

                            find_if()

   template< class InputIterator, class Predicate >
   InputIterator
   find_if( InputIterator first,
      InputIterator last, Predicate pred );

        [first,last)  
 pred.    true,  . find_if() 
  InputIterator,    ;  
  last.

                                                                 ++   1111

   #include <algorithm>
   #include <list>
   #include <set>
   #include <string>
   #include <iostream.h>

   //   
   //  true,     - FriendSet
   class OurFriends { //  
   public:
      bool operator()( const string& str ) {
         return ( friendset.count( str ));
      }
      static void
      FriendSet( const string *fs, int count ) {
         copy( fs, fs+count,
         inserter( friendset, friendset.end() ));
      }
   private:
      static set< string, less<string>, allocator > friendset;
   };

   set< string, less<string>, allocator > OurFriends::friendset;

   int main()
   {
      string Pooh_friends[] = { "", "", "-" };
      string more_friends[] = { "", "", "" };
      list<string,allocator> lf( more_friends, more_friends+3 );
       
      //    
      OurFriends::FriendSet( Pooh_friends, 3 );
      list<string,allocator>::iterator our_mutual_friend;
      our_mutual_friend =
         find_if( lf.begin(), lf.end(), OurFriends());

      // :
      // -,    -   .
      if ( our_mutual_friend != lf.end() )
         cout << "-,   "
                << *our_mutual_friend
                << "   .\n";

   return 0;
   }

                                                            ++   1112


                                     find_end()

   template< class ForwardIterator1, class ForwardIterator2 >
   ForwardIterator1
   find_end( ForwardIterator1 first1, ForwardIterator1 last1,
   ForwardIterator2 first2, ForwardIterator2 last2 );
   template< class ForwardIterator1, class ForwardIterator2,
      class BinaryPredicate >
   ForwardIterator1
   find_end( ForwardIterator1 first1, ForwardIterator1 last1,
      ForwardIterator2 first2, ForwardIterator2 last2,
      BinaryPredicate pred );

    ,   [first1,last1),  
  ,   [first2,last2).
,      Mississippi,    ss, 
find_end()  ,    s    ss.
      ,   last1.  
   ,    
,      ,  .

                                                             ++   1113

   #include <algorithm>
   #include <vector>
   #include <iostream.h>
   #include <assert.h>

   int main()
   {
      int array[ 17 ] = { 7,3,3,7,6,5,8,7,2,1,3,7,6,3,8,4,3 };
      int subarray[ 3 ] = { 3, 7, 6 };

      int *found_it;

      // find     3,7,6
      //         ...

      found_it = find_end( &array[0], &array[17],
         &subarray[0], &subarray[3] );

      assert( found_it == &array[10] );

      vector< int, allocator > ivec( array, array+17 );
      vector< int, allocator > subvec( subarray, subarray+3 );
      vector< int, allocator >::iterator found_it2;

      found_it2 = find_end( ivec.begin(), ivec.end(),
         subvec.begin(), subvec.end(),
         equal_to<int>() );

      assert( found_it2 == ivec.begin()+10 );

      cout << "ok: find_end    "
             << "  : 3,7,6!\n";
   }

                             find_first_of()

   template< class ForwardIterator1, class ForwardIterator2 >
   ForwardIterator1
   find_first_of( ForwardIterator1 first1, ForwardIterator1 last1,
      ForwardIterator2 first2, ForwardIterator2 last2 );

   template< class ForwardIterator1, class ForwardIterator2,
      class BinaryPredicate >
   ForwardIterator1
   find_first_of( ForwardIterator1 first1, ForwardIterator1 last1,
      ForwardIterator2 first2, ForwardIterator2 last2,
      BinaryPredicate pred );

   ,   [first2,last2),  , 
   ,   [first1,last1).
,        synesthesia.
      aeiou. find_first_of()
 ,      

                                                  ++   1114

  ,    e.   
       ,   last1.
     ,    
,       pred.

   #include <algorithm>
   #include <vector>
   #include <string>
   #include <iostream.h>

   int main()
   {
      string s_array[] = { "Ee", "eE", "ee", "Oo", "oo", "ee" };

      //    "ee" -- &s_array[2]
      string to_find[] = { "oo", "gg", "ee" };

      string *found_it =
         find_first_of( s_array, s_array+6,
         to_find, to_find+3 );

      // :
      // : ee
      // &s_array[2]: 0x7fff2dac
      // &found_it: 0x7fff2dac

      if ( found_it != &s_array[6] )
         cout << ": " << *found_it << "\n\t"
                << "&s_array[2]:\t" << &s_array[2] << "\n\t"
                << "&found_it:\t" << found_it << "\n\n";

      vector< string, allocator > svec( s_array, s_array+6);
      vector< string, allocator > svec_find( to_find, to_find+2 );

      //   "oo" -- svec.end()-2
      vector< string, allocator >::iterator found_it2;

      found_it2 = find_first_of(
         svec.begin(), svec.end(),
         svec_find.begin(), svec_find.end(),
         equal_to<string>() );

      // :
      //  : oo
      //    &svec.end()-2: 0x100067b0
      //    &found_it2: 0x100067b0

      if ( found_it2 != svec.end() )
         cout << " : " << *found_it2 << "\n\t"
                << "&svec.end()-2:\t" << svec.end()-2 << "\n\t"
                << "&found_it2:\t" << found_it2 << "\n";
   }

                             for_each()

                                                           ++   1115

   InputIterator last, Function func );
   template< class InputIterator, class Function >
   Function
   for_each( InputIterator first,
      InputIterator last, Function func );

   for_each()  - func     
[first,last). func    ,    
  .    , 
  transform(). func   ,  
.

   #include <algorithm>
   #include <vector>
   #include <iostream.h>

   template <class Type>
   void print_elements( Type elem ) { cout << elem << " "; }

   int main()
   {
      vector< int, allocator > ivec;

      for ( int ix = 0; ix < 10; ix++ )
         ivec.push_back( ix );

      void (*pfi)( int ) = print_elements;
      for_each( ivec.begin(), ivec.end(), pfi );

   return 0;
   }

                               generate()

   template< class ForwardIterator, class Generator >
   void
   generate( ForwardIterator first,
      ForwardIterator last, Generator gen );

generate()  ,    [first,last),
   gen,    - 
  .

                                                      ++   1116

   #include <algorithm>
   #include <list>
   #include <iostream.h>

   int odd_by_twos() {
      static int seed = -1;
      return seed += 2;
   }

   template <class Type>
   void print_elements( Type elem ) { cout << elem << " "; }

   int main()
   {
      list< int, allocator > ilist( 10 );
      void (*pfi)( int ) = print_elements;

      generate( ilist.begin(), ilist.end(), odd_by_twos );

      // :
      //   ,  :
      // 1 3 5 7 9 11 13 15 17 19

      cout << "  ,  :\n";
      for_each( ilist.begin(), ilist.end(), pfi );
      generate( ilist.begin(), ilist.end(), odd_by_twos );

      // :
      //   ,  :
      // 21 23 25 27 29 31 33 35 37 39
      cout << "\n\n  ,  :\n";
      for_each( ilist.begin(), ilist.end(), pfi );

      return 0;
   }

                                 generate_n()

   template< class OutputIterator, class Size, class Generator >
   void
   generate_n( OutputIterator first, Size n, Generator gen );

   generate_n()  ,   first, n   gen,
   -    .

                                                           ++   1117

   #include <algorithm>
   #include <iostream.h>
   #include <list>

   class even_by_twos {
   public:
      even_by_twos( int seed = 0 ) : _seed( seed ){}
      int operator()() { return _seed += 2; }
   private:
      int _seed;
   };

   template <class Type>
   void print_elements( Type elem ) { cout << elem << " "; }

   int main()
   {
      list< int, allocator > ilist( 10 );
      void (*pfi)( int ) = print_elements;

      generate_n( ilist.begin(), ilist.size(), even_by_twos() );

      // :
      // generate_n  even_by_twos():
      // 2 4 6 8 10 12 14 16 18 20

      cout << "generate_n  even_by_twos():\n";
      for_each( ilist.begin(), ilist.end(), pfi ); cout << "\n";
      generate_n( ilist.begin(), ilist.size(), even_by_twos( 100 ) );

      // :
      // generate_n  even_by_twos( 100 ):
      // 102 104 106 108 110 112 114 116 118 120

      cout << "generate_n  even_by_twos( 100 ):\n";
      for_each( ilist.begin(), ilist.end(), pfi );

   }

                             includes()

   template< class InputIterator1, class InputIterator2 >
   bool
   includes( InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2 );

   template< class InputIterator1, class InputIterator2, class Compare >
   bool
   includes( InputIterator1 first1, InputIterator1 last1,
                 InputIterator2 first2, InputIterator2 last2,
           Compare comp );

   includes() ,     [first1,last1)
   [first2,last2).   , 

                                                      ++   1118

   ,   ;
     - comp.

   #include <algorithm>
   #include <vector>
   #include <iostream.h>

   int main()
   {
      int ia1[] = { 13, 1, 21, 2, 0, 34, 5, 1, 8, 3, 21, 34 };
      int ia2[] = { 21, 2, 8, 3, 5, 1 };

      //  includes    
      sort( ia1, ia1+12 ); sort( ia2, ia2+6 );

      // :   ia2   ia1? 

      bool res = includes( ia1, ia1+12, ia2, ia2+6 );
      cout << "  ia2   ia1? "
             << (res ? "" : "") << endl;

      vector< int, allocator > ivect1( ia1, ia1+12 );
      vector< int, allocator > ivect2( ia2, ia2+6 );

      //    
      sort( ivect1.begin(), ivect1.end(), greater<int>() );
      sort( ivect2.begin(), ivect2.end(), greater<int>() );

      res = includes( ivect1.begin(), ivect1.end(),
         ivect2.begin(), ivect2.end(),
         greater<int>() );

      // :   ivect2   ivect1? 
      cout << "  ivect2   ivect1? "
              << (res ? "" : "") << endl;
   }

                              inner_product()

                                                        ++   1119

   template< class InputIterator1, class InputIterator2
                   class Type >
   Type
   inner_product(
      InputIterator1 first1, InputIterator1 last,
      InputIterator2 first2, Type init );

   template< class InputIterator1, class InputIterator2
                  class Type,
                  class BinaryOperation1, class BinaryOperation2 >
   Type
   inner_product(
       InputIterator1 first1, InputIterator1 last,
       InputIterator2 first2, Type init,
      BinaryOperation1 op1, BinaryOperation2 op2 );

         
       init. 
   [first1,last1),   
first2     . ,   
{2,3,5,8}  {1,2,3,4},     :

   2*1 + 3*2 + 5*3 + 8*4

       0,   55.
           op1,  
    op1. ,    
     op1     op2,
    :

   (2+1) - (3+2) - (5+3) - (8+4)

inner_product()      .    
     <numeric>.

                                                       ++   1120

   #include <numeric>
   #include <vector>
   #include <iostream.h>

   int main()
   {
      int ia[] = { 2, 3, 5, 8 };
      int ia2[] = { 1, 2, 3, 4 };

      //      ,
      //     : 0

      int res = inner_product( &ia[0], &ia[4], &ia2[0], 0 );

      // :   : 55
      cout << "  : "
             << res << endl;

      vector<int, allocator> vec( ia, ia+4 );
      vector<int, allocator> vec2( ia2, ia2+4 );

      //      ,
      //    : 0

      res = inner_product( vec.begin(), vec.end(),
         vec2.begin(), 0,
         minus<int>(), plus<int>() );

      // :   : -28
     cout << "  : "
            << res << endl;

      return 0;
   }

                            inplace_merge()

   template< class BidirectionalIterator >
   void
   inplace_merge( BidirectionalIterator first,
      BidirectionalIterator middle,
      BidirectionalIterator last );

   template< class BidirectionalIterator, class Compare >
   void
   inplace_merge( BidirectionalIterator first,
      BidirectionalIterator middle,
      BidirectionalIterator last, Compare comp );

   inplace_merge()     ,
   [first,middle)  [middle,last). 
  ,    first.   

                                                          ++   1121

     ,   
 ,     ,  .

   #include <algorithm>
   #include <vector>
   #include <iostream.h>

   template <class Type>
   void print_elements( Type elem ) { cout << elem << " "; }

   /*
    * :
   ia     :
   12 15 17 20 23 26 29 35 40 51 10 16 21 41 44 54 62 65 71 74

   ia inplace_merge:
   10 12 15 16 17 20 21 23 26 29 35 40 41 44 51 54 62 65 71 74

   ivec     :
   51 40 35 29 26 23 20 17 15 12 74 71 65 62 54 44 41 21 16 10

   ivec inplace_merge:
   74 71 65 62 54 51 44 41 40 35 29 26 23 21 20 17 16 15 12 10
   */

   int main()
   {
      int ia[] = { 29,23,20,17,15,26,51,12,35,40,
         74,16,54,21,44,62,10,41,65,71 };

      vector< int, allocator > ivec( ia, ia+20 );
      void (*pfi)( int ) = print_elements;

      //   
      sort( &ia[0], &ia[10] );
      sort( &ia[10], &ia[20] );

      cout << "ia     : \n";
      for_each( ia, ia+20, pfi ); cout << "\n\n";

      inplace_merge( ia, ia+10, ia+20 );

      cout << "ia inplace_merge:\n";
      for_each( ia, ia+20, pfi ); cout << "\n\n";

      sort( ivec.begin(), ivec.begin()+10, greater<int>() );
      sort( ivec.begin()+10, ivec.end(), greater<int>() );

      cout << "ivec     : \n";
      for_each( ivec.begin(), ivec.end(), pfi ); cout << "\n\n";

      inplace_merge( ivec.begin(), ivec.begin()+10,
         ivec.end(), greater<int>() );

      cout << "ivec inplace_merge:\n";
       for_each( ivec.begin(), ivec.end(), pfi ); cout << endl;
   }

                                                            ++   1122

                                    iter_swap()

   template< class ForwardIterator1, class ForwardIterator2 >
   void
    iter_swap( ForwardIterator1 a, ForwardIterator2 b );

iter_swap()   ,     a  b.

   #include <algorithm>
   #include <list>
   #include <iostream.h>

   int main()
   {
      int ia[] = { 5, 4, 3, 2, 1, 0 };
      list< int,allocator > ilist( ia, ia+6 );

      typedef list< int, allocator >::iterator iterator;
      iterator iter1 = ilist.begin(),iter2,
          iter_end = ilist.end();

      //   "" ...
      for ( ; iter1 != iter_end; ++iter1 )
         for ( iter2 = iter1; iter2 != iter_end; ++iter2 )
           if ( *iter2 < *iter1 )
              iter_swap( iter1, iter2 );

      // :
      // ilist   ""   iter_swap():
      // { 0 1 2 3 4 5 }

      cout << "ilist   ""  
      iter_swap(): { ";
     for ( iter1 = ilist.begin(); iter1 != iter_end; ++iter1 )
         cout << *iter1 << " ";
          cout << "}\n";

      return 0;

   }

                                                            ++   1123

                           lexicographical_compare()

   template< class InputIterator1, class InputIterator2 >
   bool
   lexicographical_compare(
      InputIterator1 first1, InputIterator1 last1,
      InputIterator1 first2, InputIterator2 last2 );

   template< class InputIterator1, class InputIterator2,
                    class Compare >
   bool
   lexicographical_compare(
      InputIterator1 first1, InputIterator1 last1,
      InputIterator1 first2, InputIterator2 last2,
      Compare comp );

   lexicographical_compare()      
,   [first1,last1)  [first2,last2).
 ,        , 
  [last1,last2]      last1  last2 (
   ).     
  :

       ,  true,  false;
    last1 ,  last2 ,  true;
    last2 ,  last1 ,  false;
      last1,  last2 (..   ),  false.

    ,     
.
,   :

   string arr1[] = { "Piglet", "Pooh", "Tigger" };
   string arr2[] = { "Piglet", "Pooch", "Eeyore" };

        ,   . Pooh  ,
 Pooch,   c   h (  
   ).      (
   ).    false.
           
:

                                                             ++   1124

   #include <algorithm>
   #include <list>
   #include <string>
   #include <assert.h>
   #include <iostream.h>

   class size_compare {
   public:
      bool operator()( const string &a, const string &b ) {
         return a.length() <= b.length();
     }
   };

   int main()
   {
      string arr1[] = { "Piglet", "Pooh", "Tigger" };
      string arr2[] = { "Piglet", "Pooch", "Eeyore" };

      bool res;

      //     false
      // Pooch  Pooh
      //       false

      res = lexicographical_compare( arr1, arr1+3,
          arr2, arr2+3 );

      assert( res == false );
      //  true:    ilist2
      //     
      //  ilist1

      list< string, allocator > ilist1( arr1, arr1+3 );
      list< string, allocator > ilist2( arr2, arr2+3 );

      res = lexicographical_compare(
         ilist1.begin(), ilist1.end(),
         ilist2.begin(), ilist2.end(), size_compare() );

      assert( res == true );

      cout << "ok: lexicographical_compare  !\n";
   }

                                 lower_bound()


                                                       ++   1125

   template< class ForwardIterator, class Type >
   ForwardIterator
   lower_bound( ForwardIterator first,
      ForwardIterator last, const Type &value );

   template< class ForwardIterator, class Type, class Compare >
   ForwardIterator
   lower_bound( ForwardIterator first,
       ForwardIterator last, const Type &value,
    class Compare );

   lower_bound()  ,     
 ,   [first,last), 
    value,   .  
  ,    value. ,   
:

   int ia = = {12,15,17,19,20,22,23,26,29,35,40,51};

   lower_bound()   value=21  ,
  23.    22    . 
     ,   
 ,        
comp.

                                                         ++   1126

   #include <algorithm>
   #include <vector>
   #include <iostream.h>

   int main()
   {
      int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};
      sort( &ia[0], &ia[12] );

      int search_value = 18;
      int *ptr = lower_bound( ia, ia+12, search_value );

      // :
      //  ,     18, -  19
      //    17

      cout << " ,     "
             << search_value
             << ",   "
             << *ptr << endl
             << "   "
             << *(ptr-1) << endl;

      vector< int, allocator > ivec( ia, ia+12 );

      //     ...
      sort( ivec.begin(), ivec.end(), greater<int>() );
      search_value = 26;
      vector< int, allocator >::iterator iter;

      //  ,  
      //   ...
      iter = lower_bound( ivec.begin(), ivec.end(),
         search_value, greater<int>() );

      // :
      //  ,     26, -  26
      //    29

      cout << " ,     "
             << search_value
            << ", -  "
            << *iter << endl
            << "   "
            << *(iter-1) << endl;

      return 0;

   }

                                      max()

                                                                ++   1127
   template< class Type >
   const Type&
   max( const Type &aval, const Type &bval );

   template< class Type, class Compare >
   const Type&
     max( const Type &aval, const Type &bval, Compare comp );

   max()      aval  bval.   
  ,    Type;    
 comp.

                                   max_element()

   template< class ForwardIterator >
   ForwardIterator
   max_element( ForwardIterator first,
      ForwardIterator last );

   template< class ForwardIterator, class Compare >
   ForwardIterator
   max_element( ForwardIterator first,
      ForwardIterator last, Compare comp );

   max_element()  ,   ,  
   ,   [first,last).
     ,    
;      comp.

                                   min()

   template< class Type >
   const Type&
   min( const Type &aval, const Type &bval );

   template< class Type, class Compare >
   const Type&
   min( const Type &aval, const Type &bval, Compare comp );

   min()      aval  bval.   
  ,    Type;    
 comp.

                                                          ++   1128

                          min_element()

   template< class ForwardIterator >
   ForwardIterator
   min_element( ForwardIterator first,
      ForwardIterator last );

   template< class ForwardIterator, class Compare >
   ForwardIterator
   min_element( ForwardIterator first,
      ForwardIterator last, Compare comp );

   max_element()  ,   ,  
  ,   [first,last). 
    ,    
;      comp.

   //  max(), min(), max_element(), min_element()
   #include <algorithm>
   #include <vector>
   #include <iostream.h>

   int main()
   {
      int ia[] = { 7, 5, 2, 4, 3 };
      const vector< int, allocator > ivec( ia, ia+5 );

      int mval = max( max( max( max(ivec[4],ivec[3]),
         ivec[2]),ivec[1]),ivec[0]);

      // :    max() : 7
      cout << "   max() : "
             << mval << endl;

      mval = min( min( min( min(ivec[4],ivec[3]),
         ivec[2]),ivec[1]),ivec[0]);

      // :    min() : 2
     cout << "   min() : "
            << mval << endl;

      vector< int, allocator >::const_iterator iter;
      iter = max_element( ivec.begin(), ivec.end() );

      // :    max_element()  : 7
      cout << "   max_element()  : "
             << *iter << endl;

      iter = min_element( ivec.begin(), ivec.end() );

      // :    min_element()  : 2
      cout << "   min_element()  : "
              << *iter << endl;

                                                          ++   1129

   }

                               merge()

   template< class InputIterator1, class InputIterator2,
      class OutputIterator >
   OutputIterator
   merge( InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2,
      OutputIterator result );

   template< class InputIterator1, class InputIterator2,
      class OutputIterator, class Compare >
   OutputIterator
   merge( InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2,
      OutputIterator result, Compare comp );

   merge()    , 
 [first1,last1)  [first2,last2),   
,    result.  
       .   
    ,    
;      comp.

                                                          ++   1130

   #include <algorithm>
   #include <vector>
   #include <list>
   #include <deque>
   #include <iostream.h>

   template <class Type>
   void print_elements( Type elem ) { cout << elem << " "; }
   void (*pfi)( int ) = print_elements;

   int main()
   {
int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};
int ia2[] = {74,16,39,54,21,44,62,10,27,41,65,71};

vector< int, allocator > vec1( ia, ia +12 ),
   vec2( ia2, ia2+12 );

int ia_result[24];
vector< int, allocator > vec_result(vec1.size()+vec2.size());

sort( ia, ia +12 );
sort( ia2, ia2+12 );

// :
// 10 12 15 16 17 19 20 21 22 23 26 27 29 35
// 39 40 41 44 51 54 62 65 71 74

merge( ia, ia+12, ia2, ia2+12, ia_result );
for_each( ia_result, ia_result+24, pfi ); cout << "\n\n";

sort( vec1.begin(), vec1.end(), greater<int>() );
sort( vec2.begin(), vec2.end(), greater<int>() );

merge( vec1.begin(), vec1.end(),
   vec2.begin(), vec2.end(),
   vec_result.begin(), greater<int>() );

// : 74 71 65 62 54 51 44 41 40 39 35 29 27 26 23 22
// 21 20 19 17 16 15 12 10
for_each( vec_result.begin(), vec_result.end(), pfi );
cout << "\n\n";

   }

                             mismatch()

                                                               ++   1131

   template< class InputIterator1, class InputIterator2 >
   pair<InputIterator1, InputIterator2>
   mismatch( InputIterator1 first,
         InputIterator1 last, InputIterator2 first2 );

   template< class InputIterator1, class InputIterator2,
   class BinaryPredicate >
   pair<InputIterator1, InputIterator2>
   mismatch( InputIterator1 first, InputIterator1 last,
         InputIterator2 first2, BinaryPredicate pred );

   mismatch()       , 
 .   ,     
    .    , 
       last   . ,  
 meet  meat,       . 
       ,  
   ,  .  
  ,   ;   
,     .

#include <algorithm>
#include <list>
#include <utility>
#include <iostream.h>

class equal_and_odd{
public:
bool operator()( int ival1, int ival2 )
{
//     ?
//   ?  ?

return ( ival1 == ival2 &&
( ival1 == 0 || ival1%2 ));
}
};

int main()
{
int ia[] = { 0,1,1,2,3,5,8,13 };
int ia2[] = { 0,1,1,2,4,6,10 };

pair<int*,int*> pair_ia = mismatch( ia, ia+7, ia2 );

// :   : ia: 3  ia2: 4
cout << "  : ia: "
<< *pair_ia.first << "  ia2: "
<< *pair_ia.second << endl;

list<int,allocator> ilist( ia, ia+7 );
list<int,allocator> ilist2( ia2, ia2+7 );

typedef list<int,allocator>::iterator iter;
pair<iter,iter> pair_ilist =
mismatch( ilist.begin(), ilist.end(),
ilist2.begin(), equal_and_odd() );

// :   :   ,  
    :
// ilist: 2  ilist2: 2

cout << "  :   , "
<< "  : \n\tilist: "
<< *pair_ilist.first << "  ilist2: "
<< *pair_ilist.second << endl;

   }

                                                               ++   1132

                                next_permutation()

   template < class BidirectionalIterator >
   bool
   next_permutation( BidirectionalIterator first,
                               BidirectionalIterator last );

   template < class BidirectionalIterator, class Compare >
   bool
   next_permutation( BidirectionalIterator first,
      BidirectionalIterator last, class Compare );

  next_permutation()  ,  
[first,last), ,   ,     ( , 
 ,    12.5).  
  ,   false,   true.  
        
  ,       comp.
   next_permutation()   
    ,    .
          
musil,  ilmsu,       .

                                                               ++   1133

#include <algorithm>
#include <vector>
#include <iostream.h>

void print_char( char elem ) { cout << elem ; }
void (*ppc)( char ) = print_char;

/* :
ilmsu ilmus ilsmu ilsum ilums ilusm imlsu imlus
imslu imsul imuls imusl islmu islum ismlu ismul
isulm isuml iulms iulsm iumls iumsl iuslm iusml
limsu limus lismu lisum liums liusm lmisu lmius
lmsiu lmsui lmuis lmusi lsimu lsium lsmiu lsmui
lsuim lsumi luims luism lumis lumsi lusim lusmi
milsu milus mislu misul miuls miusl mlisu mlius
mlsiu mlsui mluis mlusi msilu msiul msliu mslui
msuil msuli muils muisl mulis mulsi musil musli
silmu silum simlu simul siulm siuml slimu slium
slmiu slmui sluim slumi smilu smiul smliu smlui
smuil smuli suilm suiml sulim sulmi sumil sumli
uilms uilsm uimls uimsl uislm uisml ulims ulism
ulmis ulmsi ulsim ulsmi umils umisl umlis umlsi
umsil umsli usilm usiml uslim uslmi usmil usmli
*/

int main()
{
vector<char,allocator> vec(5);

//  : musil
vec[0] = 'm'; vec[1] = 'u'; vec[2] = 's';
vec[3] = 'i'; vec[4] = 'l';

int cnt = 2;
sort( vec.begin(), vec.end() );
for_each( vec.begin(), vec.end(), ppc ); cout << "\t";

//     "musil"
while( next_permutation( vec.begin(), vec.end()))
{
for_each( vec.begin(), vec.end(), ppc );
cout << "\t";

if ( ! ( cnt++ % 8 )) {
cout << "\n";
cnt = 1;
}
}

cout << "\n\n";
return 0;

   }

                                                               ++   1134

                                    nth_element()

   template < class RandomAccessIterator >
   void
   nth_element( RandomAccessIterator first,
      RandomAccessIterator nth,
      RandomAccessIterator last );
   template < class RandomAccessIterator, class Compare >
   void
   nth_element( RandomAccessIterator first,
      RandomAccessIterator nth,
      RandomAccessIterator last, Compare comp );

   nth_element()  ,  
[first,last),    ,   ,    
nth,   ,      . ,  


   int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};

  nth_element(),   nth     ( 
 26):

   nth_element( &ia[0], &ia[6], &ia[2] );

 ,    ,  26, 
  26,   ,  26, :

   {23,20,22,17,15,19,12,26,51,35,40,29}

   ,  ,      nth,
.        ,
    ,     
,  .

                                                               ++   1135

#include <algorithm>
#include <vector>
#include <iostream.h>

/* :
 : 29 23 20 22 17 15 26 51 19 12 35 40
,    26
12 15 17 19 20 22 23 26 51 29 35 40
,      23
40 35 29 51 26 23 22 20 19 17 15 12
*/

int main()
{
int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};
vector< int,allocator > vec( ia, ia+12 );
ostream_iterator<int> out( cout," " );

cout << " : ";
copy( vec.begin(), vec.end(), out ); cout << endl;

cout << ",    "
<< *( vec.begin()+6 ) << endl;
nth_element( vec.begin(), vec.begin()+6, vec.end() );
copy( vec.begin(), vec.end(), out ); cout << endl;

cout << " ,    "
<< "  "
<< *( vec.begin()+6 ) << endl;
nth_element( vec.begin(), vec.begin()+6,
vec.end(), greater<int>() );
copy( vec.begin(), vec.end(), out ); cout << endl;

   }

                                      partial_sort()

   template < class RandomAccessIterator >
   void
   partial_sort( RandomAccessIterator first,
      RandomAccessIterator middle,
      RandomAccessIterator last );
   template < class RandomAccessIterator, class Compare >
   void
   partial_sort( RandomAccessIterator first,
      RandomAccessIterator middle,
      RandomAccessIterator last, Compare comp );

   partial_sort()   ,   
[first,middle).    [middle,last) 
. ,   

   int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};

                                                               ++   1136

  partial_sort(), middle    :

   partial_sort( &ia[0], &ia[5], &ia[12] );

 ,     (.. middle-first)
 :

   {12,15,17,19,20,29,23,22,26,51,35,40}.

  middle  last-1    -  ,
        . 
      ,  
  ,       comp.

                             partial_sort_copy()

   template < class InputIterator, class RandomAccessIterator >
   RandomAccessIterator
   partial_sort_copy( InputIterator first, InputIterator last,
      RandomAccessIterator result_first,
      RandomAccessIterator result_last );

   template < class InputIterator, class RandomAccessIterator,
   class Compare >
   RandomAccessIterator
   partial_sort_copy( InputIterator first, InputIterator last,
      RandomAccessIterator result_first,
      RandomAccessIterator result_last,
   Compare comp );

   partial_sort_copy()    ,  partial_sort(),  
    ,  
[result_first,result_last] (      
,      ). , 
 :

   int ia2[5];

      partial_sort_copy(),    middle  
:

   &ia2[0], &ia2[5] );

                                                               ++   1137

  ia2   : {12,15,17,19,20}.
     .

#include <algorithm>
#include <vector>
#include <iostream.h>

/*
* :
 : 69 23 80 42 17 15 26 51 19 12 35 8
  partial_sort()  :  
8 12 15 17 19 23 26 80 69 51 42 35
  partial_sort_copy()   
    
26 23 19 17 15 12 8
*/

int main()
{
int ia[] = { 69,23,80,42,17,15,26,51,19,12,35,8 };
vector< int,allocator > vec( ia, ia+12 );
ostream_iterator<int> out( cout," " );

cout << " : ";
copy( vec.begin(), vec.end(), out ); cout << endl;

cout << "  partial_sort()  : "
<< "  \n";
partial_sort( vec.begin(), vec.begin()+7, vec.end() );
copy( vec.begin(), vec.end(), out ); cout << endl;

vector< int, allocator > res(7);
cout << "   partial_sort_copy()   
\n\t"
<< "     \n";

partial_sort_copy( vec.begin(), vec.begin()+7, res.begin(),
res.end(), greater<int>() );
copy( res.begin(), res.end(), out ); cout << endl;

   }

                                partial_sum()

                                                               ++   1138

   template < class InputIterator, class OutputIterator >
   OutputIterator
   partial_sum(
      InputIterator first, InputIterator last,
      OutputIterator result );

   template < class InputIterator, class OutputIterator,
      class BinaryOperation >
   OutputIterator
   partial_sum(
      InputIterator first, InputIterator last,
         OutputIterator result, BinaryOperation op );

     partial_sum()   , 
 [first,last),  ,    
    ,   . , 
 {0,1,1,2,3,5,8}   {0,1,2,4,7,12,20}, , ,
      (0,1,1)    (2),  
 4.
           ,
 . ,    {1,2,3,4} 
- times<int>.   {1,2,6,24}.    
 OutputIterator       
.
   partial_sum()      .   
       <numeric>.

#include <numeric>
#include <vector>
#include <iostream.h>

/*
* :
: 1 3 4 5 7 8 9
  :
1 4 8 13 20 28 37
     times<int>():
1 3 12 60 420 3360 30240
*/

int main()
{
const int ia_size = 7;
int ia[ ia_size ] = { 1, 3, 4, 5, 7, 8, 9 };
int ia_res[ ia_size ];

ostream_iterator< int > outfile( cout, " " );
vector< int, allocator > vec( ia, ia+ia_size );
vector< int, allocator > vec_res( vec.size() );

cout << ": ";
copy( ia, ia+ia_size, outfile ); cout << endl;

cout << "  :\n";
partial_sum( ia, ia+ia_size, ia_res );
copy( ia_res, ia_res+ia_size, outfile ); cout << endl;

cout << "    
times<int>():\n";
partial_sum( vec.begin(), vec.end(), vec_res.begin(),
times<int>() );

copy( vec_res.begin(), vec_res.end(), outfile );
cout << endl;

   }
                                                               ++   1139

                             partition()

   template < class BidirectionalIterator, class UnaryPredicate >
   BidirectionalIterator
   partition(
      BidirectionalIterator first,
      BidirectionalIterator last, UnaryPredicate pred );

   partition()     [first,last).  ,
   pred  true,   ,   
 false. ,    {0,1,2,3,4,5,6}  ,
    ,      
{0,2,4,6}  {1,3,5}.  ,      
,        , .. 4
   2,  5  1.    
 stable_partition(),  .

                                                               ++   1140

#include <algorithm>
#include <vector>
#include <iostream.h>

class even_elem {
public:
bool operator()( int elem )
{ return elem%2 ? false : true; }
};

/*
* :
 :
29 23 20 22 17 15 26 51 19 12 35 40
,    :
40 12 20 22 26 15 17 51 19 23 35 29
,     25:
12 23 20 22 17 15 19 51 26 29 35 40
*/

int main()
{
const int ia_size = 12;
int ia[ia_size] = { 29,23,20,22,17,15,26,51,19,12,35,40 };

vector< int, allocator > vec( ia, ia+ia_size );
ostream_iterator< int > outfile( cout, " " );

cout << " : \n";
copy( vec.begin(), vec.end(), outfile ); cout << endl;

cout << ",    :\n";
partition( &ia[0], &ia[ia_size], even_elem() );
copy( ia, ia+ia_size, outfile ); cout << endl;

cout << ",     25:\n";
partition( vec.begin(), vec.end(), bind2nd(less<int>(),25) );
copy( vec.begin(), vec.end(), outfile ); cout << endl;

   }

                             prev_permutation()

   template < class BidirectionalIterator >
   bool
   prev_permutation( BidirectionalIterator first,
      BidirectionalIterator last );

   template < class BidirectionalIterator, class Compare >
   bool
   prev_permutation( BidirectionalIterator first,
      BidirectionalIterator last, class Compare );

   prev_permutation()  ,  
[first,last), ,    ,   

                                                               ++   1141

( ,   ,    12.5). 
   ,   false,  true. 
       
    ,       ,
 .

   #include <algorithm>
   #include <vector>
   #include <iostream.h>
   // : n d a n a d d n a d a n a n d a d n

   int main()
   {
      vector< char, allocator > vec( 3 );
      ostream_iterator< char > out_stream( cout, " " );

vec[0] = 'n'; vec[1] = 'd'; vec[2] = 'a';
copy( vec.begin(), vec.end(), out_stream ); cout << "\t";

//    "dan"
while( prev_permutation( vec.begin(), vec.end() )) {
copy( vec.begin(), vec.end(), out_stream );
cout << "\t";
}

cout << "\n\n";

   }

                               random_shuffle()

   template < class RandomAccessIterator >
   void
   random_shuffle( RandomAccessIterator first,
      RandomAccessIterator last );

   template < class RandomAccessIterator,
      class RandomNumberGenerator >

   void
random_shuffle( RandomAccessIterator first,
      RandomAccessIterator last,
   RandomNumberGenerator rand);

   random_shuffle()     [first,last)  
.      -   
,   . ,   rand 
  double   [0,1].

                                                               ++   1142

#include <algorithm>
#include <vector>
#include <iostream.h>

int main()
{
vector< int, allocator > vec;
for ( int ix = 0; ix < 20; ix++ )
vec.push_back( ix );

random_shuffle( vec.begin(), vec.end() );

// :
// random_shuffle   1 .. 20:
// 6 11 9 2 18 12 17 7 0 15 4 8 10 5 1 19 13 3 14 16
cout << "random_shuffle   1 .. 20:\n";
copy( vec.begin(), vec.end(), ostream_iterator< int >( cout,"
" ));
   }

                                     remove()


   template< class ForwardIterator, class Type >
   ForwardIterator
   remove( ForwardIterator first,
      ForwardIterator last, const Type &value );

   remove()    [first,last)     value. 
 (  remove_if())        
(..   ),      
 ,   first.     ,
  ,      .
, ,  {0,1,0,2,0,3,0,4}. ,  
  .     {1,2,3,4,0,4,0,4}. 1
   , 2   , 3     4   . ,
  0   ,    .  
  0   .      
erase(),    . (   
    remove_copy()  remove_copy_if(),  
remove()  remove_if(),     )

                                    remove_copy()

                                                               ++   1143
   template< class InputIterator, class OutputIterator,
   class Type >
   OutputIterator
      remove_copy( InputIterator first, InputIterator last,
      OutputIterator result, const Type &value );

   remove_copy()   ,    value,  ,
    result.      
 .    .

#include <algorithm>
#include <vector>
#include <assert.h>
#include <iostream.h>

/* :
 :
0 1 0 2 0 3 0 4 0 5
  remove  erase():
1 2 3 4 5 3 0 4 0 5
  erase():
1 2 3 4 5
  remove_copy()
1 2 3 4 5
*/

int main()
{
int value = 0;
int ia[] = { 0, 1, 0, 2, 0, 3, 0, 4, 0, 5 };

vector< int, allocator > vec( ia, ia+10 );
ostream_iterator< int > ofile( cout," ");
vector< int, allocator >::iterator vec_iter;

cout << " :\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';

vec_iter = remove( vec.begin(), vec.end(), value );

cout << "  remove  erase():\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';

//     
vec.erase( vec_iter, vec.end() );

cout << "  erase():\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';

int ia2[5];
vector< int, allocator > vec2( ia, ia+10 );
remove_copy( vec2.begin(), vec2.end(), ia2, value );

cout << "  remove_copy():\n";
copy( ia2, ia2+5, ofile ); cout << endl;

   }

                                                               ++   1144

                               remove_if()

   template< class ForwardIterator, class Predicate >
   ForwardIterator
   remove_if( ForwardIterator first,
      ForwardIterator last, Predicate pred );

   remove_if()    [first,last)  ,   
 pred  true. remove_if() (  remove())   
   .     
   ,   first.  
  ,   ,    
 .       erase(),
   . (   
  remove_copy_if().)

                              remove_copy_if()

   template< class InputIterator, class OutputIterator,
      class Predicate >
   OutputIterator
   remove_copy_if( InputIterator first, InputIterator last,
      OutputIterator result, Predicate pred );

   remove_copy_if()   ,    pred  false, 
,      result.  
  ,    . 
   .

                                                               ++   1145

#include <algorithm>
#include <vector>
#include <iostream.h>

/* :
 :
0 1 1 2 3 5 8 13 21 34
   remove_if < 10:
13 21 34
   remove_copy_if :
1 1 3 5 13 21
*/

class EvenValue {
public:
bool operator()( int value ) {
return value % 2 ? false : true; }
};

int main()
{
int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 };

vector< int, allocator >::iterator iter;
vector< int, allocator > vec( ia, ia+10 );
ostream_iterator< int > ofile( cout, " " );

cout << " :\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';

iter = remove_if( vec.begin(), vec.end(),
bind2nd(less<int>(),10) );
vec.erase( iter, vec.end() );

cout << "   remove_if < 10:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';

vector< int, allocator > vec_res( 10 );
iter = remove_copy_if( ia, ia+10, vec_res.begin(), EvenValue()
);

cout << "   remove_copy_if
:\n";
copy( vec_res.begin(), iter, ofile ); cout << '\n';

   }

                                          replace()

   template< class ForwardIterator, class Type >
   void
   replace( ForwardIterator first, ForwardIterator last,


                                                               ++   1146

      const Type& old_value, const Type& new_value );

   replace()    [first,last)     old_value
 new_value.

                                      replace_copy()

   template< class InputIterator, class InputIterator,
      class Type >
   OutputIterator
   replace_copy( InputIterator first, InputIterator last,
      class OutputIterator result,
      const Type& old_value, const Type& new_value );

   replace_copy()    ,  replace(),   
  ,   result.    
,    .   
 .

                                                               ++   1147

#include <algorithm>
#include <vector>
#include <iostream.h>

/* :
 :
Christopher Robin Mr. Winnie the Pooh Piglet Tigger Eeyore
   replace():
Christopher Robin Pooh Piglet Tigger Eeyore
*/

int main()
{
string oldval( "Mr. Winnie the Pooh" );
string newval( "Pooh" );

ostream_iterator< string > ofile( cout, " " );
string sa[] = {
"Christopher Robin", "Mr. Winnie the Pooh",
"Piglet", "Tigger", "Eeyore"
};

vector< string, allocator > vec( sa, sa+5 );
cout << " :\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';

replace( vec.begin(), vec.end(), oldval, newval );

cout << "   replace():\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';

vector< string, allocator > vec2;
replace_copy( vec.begin(), vec.end(),
inserter( vec2, vec2.begin() ),
newval, oldval );

cout << "   replace_copy():\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';

   }

                                         replace_if()

   template< class ForwardIterator, class Predicate, class Type >
   void
   replace_if( ForwardIterator first, ForwardIterator last,
      Predicate pred, const Type& new_value );

   replace_if()       [first,last), 
  pred  true,  new_value.

                                                               ++   1148

                                    replace_copy_if()

   template< class ForwardIterator, class OutputIterator,
      class Predicate, class Type >
   OutputIterator
   replace_copy_if( ForwardIterator first, ForwardIterator last,
      class OutputIterator result,
      Predicate pred, const Type& new_value );

   replace_copy_if()    ,  replace_if(),  
   ,   result. 
   ,    .
    .

                                                               ++   1149

#include <algorithm>
#include <vector>
#include <iostream.h>

/*
 :
0 1 1 2 3 5 8 13 21 34
   replace_if < 10    0:
0 0 0 0 0 0 0 13 21 34
   replace_if     0:
0 1 1 0 3 5 0 13 21 0
*/

class EvenValue {
public:
bool operator()( int value ) {
return value % 2 ? false : true; }
};

int main()
{
int new_value = 0;

int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 };
vector< int, allocator > vec( ia, ia+10 );
ostream_iterator< int > ofile( cout, " " );

cout << " :\n";
copy( ia, ia+10, ofile ); cout << '\n';

replace_if( &ia[0], &ia[10],
bind2nd(less<int>(),10), new_value );

cout << "   replace_if < 10 "
<< "   0:\n";
copy( ia, ia+10, ofile ); cout << '\n';

replace_if( vec.begin(), vec.end(),
EvenValue(), new_value );

cout << "   replace_if "
<< "   0:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';

   }

                                           reverse()

   template< class BidirectionalIterator >
   void
   reverse( BidirectionalIterator first,
      BidirectionalIterator last );

                                                               ++   1150

   reverse()       [first,last) 
. ,    {0,1,1,2,3},  
  {3,2,1,1,0}.

                             reverse_copy()

   template< class BidirectionalIterator, class OutputIterator >
   OutputIterator
   reverse_copy( BidirectionalIterator first,
      BidirectionalIterator last, OutputIterator result );

   reverse_copy()    ,  reverse(),   
  ,   result.    
,    .   
 .

                                                               ++   1151

#include <algorithm>
#include <list>
#include <string>
#include <iostream.h>

/* :
  :
   Signature of all things I am here to
   read seaspawn and seawrack that rusty boot

    reverse():
   boot rusty that seawrack and seaspawn read to
   here am I things all of Signature
*/

class print_elements {
public:
void operator()( string elem ) {
cout << elem
<< ( _line_cnt++%8 ? " " : "\n\t" );
}

static void reset_line_cnt() { _line_cnt = 1; }
private:
static int _line_cnt;
};

int print_elements::_line_cnt = 1;

int main()
{
string sa[] = { "Signature", "of", "all", "things",
"I", "am", "here", "to", "read",
"seaspawn", "and", "seawrack", "that",
"rusty", "boot"
};

list< string, allocator > slist( sa, sa+15 );

cout << "  :\n\t";
for_each( slist.begin(), slist.end(), print_elements() );
cout << "\n\n";

reverse( slist.begin(), slist.end() );

print_elements::reset_line_cnt();

cout << "   
reverse():\n\t";
for_each( slist.begin(), slist.end(), print_elements() ); cout <<
"\n";

list< string, allocator > slist_copy( slist.size() );
reverse_copy( slist.begin(), slist.end(),
slist_copy.begin() );

   }

                                                               ++   1152

                                  rotate()

   template< class ForwardIterator >
   void
   rotate( ForwardIterator first,
      ForwardIterator middle, ForwardIterator last );

   rotate()     [first,last)   .
,    middle,  . ,  
"hissboo"    'b'    "boohiss".

                              rotate_copy()

   template< class ForwardIterator, class OutputIterator >
   OutputIterator
   rotate_copy( ForwardIterator first, ForwardIterator middle,
      ForwardIterator last, OutputIterator result );

   rotate_copy()    ,  rotate(),   
  ,   result.    
,    .   
 .

                                                               ++   1153

#include <algorithm>
#include <vector>
#include <iostream.h>

/* :
 :
1 3 5 7 9 0 2 4 6 8 10
   (0) ::
0 2 4 6 8 10 1 3 5 7 9
   (8) ::
8 10 1 3 5 7 9 0 2 4 6
rotate_copy    ::
7 9 0 2 4 6 8 10 1 3 5
*/

int main()
{
int ia[] = { 1, 3, 5, 7, 9, 0, 2, 4, 6, 8, 10 };

vector< int, allocator > vec( ia, ia+11 );
ostream_iterator< int > ofile( cout, " " );

cout << " :\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';

rotate( &ia[0], &ia[5], &ia[11] );

cout << "   (0) ::\n";
copy( ia, ia+11, ofile ); cout << '\n';

rotate( vec.begin(), vec.end()-2, vec.end() );

cout << "   (8) ::\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';

vector< int, allocator > vec_res( vec.size() );

rotate_copy( vec.begin(), vec.begin()+vec.size()/2,
vec.end(), vec_res.begin() );

cout << "rotate_copy    ::\n";
copy( vec_res.begin(), vec_res.end(), ofile );
cout << '\n';

   }

                                       search()

                                                             ++   1154

   template< class ForwardIterator1, class ForwardIterator2 >
   ForwardIterator
   search( ForwardIterator1 first1, ForwardIterator1 last1,
      ForwardIterator2 first2, ForwardIterator2 last2 );
   template< class ForwardIterator1, class ForwardIterator2,
      class BinaryPredicate >
   ForwardIterator
   search( ForwardIterator1 first1, ForwardIterator1 last1,
      ForwardIterator2 first2, ForwardIterator2 last2,
      BinaryPredicate pred );

      ,  search()  ,   
   [first1,last1),       
.    ,  last1.
,   Mississippi  iss  , 
search()  ,     .  
      ,   
   .

#include <algorithm>
#include <vector>
#include <iostream.h>

/* :
   'ate': a t e
   'vat': v a t
*/

int main()
{
ostream_iterator< char > ofile( cout, " " );

char str[ 25 ] = "a fine and private place";
char substr[] = "ate";

char *found_str = search(str,str+25,substr,substr+3);

cout << "   'ate': ";
copy( found_str, found_str+3, ofile ); cout << '\n';

vector< char, allocator > vec( str, str+24 );
vector< char, allocator > subvec(3);

subvec[0]='v'; subvec[1]='a'; subvec[2]='t';

vector< char, allocator >::iterator iter;
iter = search( vec.begin(), vec.end(),
subvec.begin(), subvec.end(),
equal_to< char >() );

cout << "   'vat': ";
copy( iter, iter+3, ofile ); cout << '\n';

   }

                                                               ++   1155

                                   search_n()

   template< class ForwardIterator, class Size, class Type >
   ForwardIterator
   search_n( ForwardIterator first, ForwardIterator last,
       Size count, const Type &value );

   template< class ForwardIterator, class Size,
   class Type, class BinaryPredicate >
   ForwardIterator
   search_n( ForwardIterator first, ForwardIterator last,
      Size count, const Type &value, BinaryPredicate pred );

   search_n()    [first,last) ,
  count   value.    , 
last. ,    ss   Mississippi   value
 's',  count  2.       
 ssi,  value   "ssi",  count  2. search_n()
       value.    
    ,    
  .

                                                               ++   1156

#include <algorithm>
#include <vector>
#include <iostream.h>

/* :
    'o': o o
   'mou': m o u
*/

int main()
{
ostream_iterator< char > ofile( cout, " " );

const char blank = ' ';
const char oh = 'o';

char str[ 26 ] = "oh my a mouse ate a moose";
char *found_str = search_n( str, str+25, 2, oh );

cout << "    'o': ";
copy( found_str, found_str+2, ofile ); cout << '\n';

vector< char, allocator > vec( str, str+25 );

//      ,
//       : mou of mouse

vector< char, allocator >::iterator iter;
iter = search_n( vec.begin(), vec.end(), 3,
blank, not_equal_to< char >() );

cout << "   'mou': ";
copy( iter, iter+3, ofile ); cout << '\n';

   }

                               set_difference()

   template< class InputIterator1, class InputIterator2,
      class OutputIterator >
   OutputIterator
   set_difference( InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2,
      OutputIterator result );

   template< class InputIterator1, class InputIterator2,
   class OutputIterator, class Compare >
   OutputIterator
   set_difference( InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2,
      OutputIterator result, Compare comp );

   set_difference()     ,
    [first1,last1),   
  [first2,last2). ,   {0,1,2,3} 

                                                               ++   1157

{0,2,4,6}  {1,3}.       
    result.    , 
       ,
    ;    
    comp.

                            set_intersection()

   template< class InputIterator1, class InputIterator2,
   class OutputIterator >
   OutputIterator
   set_intersection( InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2,
      OutputIterator result );

   template< class InputIterator1, class InputIterator2,
   class OutputIterator, class Compare >
   OutputIterator
   set_intersection( InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2,
      OutputIterator result, Compare comp );

   set_intersection()     ,
     [first1,last1)  [first2,last2).
,   {0,1,2,3}  {0,2,4,6}  {0,2}.
         
 result.    ,   
     ,   
 ;      
  comp.

                          set_symmetric_difference()

   template< class InputIterator1, class InputIterator2,
   class OutputIterator >
   OutputIterator
   set_symmetric_difference(
      InputIterator1 first1, InputIterator1 last1,
       InputIterator2 first2, InputIterator2 last2,
      OutputIterator result );

   template< class InputIterator1, class InputIterator2,
      class OutputIterator, class Compare >
   OutputIterator
   set_symmetric_difference(
      InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2,
      OutputIterator result, Compare comp );

                                                               ++   1158

   set_symmetric_difference()    
,      
[first1,last1)     [first2,last2). ,
   {0,1,2,3}  {0,2,4,6}  {1,3,4,6}.
         
 result.    ,   
     ,   
 ;      
  comp.

                              set_union()

   template< class InputIterator1, class InputIterator2,
      class OutputIterator >
   OutputIterator
   set_union(InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2,
      OutputIterator result );

   template< class InputIterator1, class InputIterator2,
      class OutputIterator, class Compare >
   OutputIterator
   set_union(InputIterator1 first1, InputIterator1 last1,
      InputIterator2 first2, InputIterator2 last2,
      OutputIterator result, Compare comp );

   set_union()     , 
     [first1,last1),    
[first2,last2),   . ,   {0,1,2,3}
 {0,2,4,6}  {0,1,2,3,4,6}.     
,     .  
         result. 
  ,      
  ,     ; 
       comp.

                                                               ++   1159

#include <algorithm>
#include <set>
#include <string>
#include <iostream.h>

/* :
  #1:
    -   

  #2:
     

 set_union():
    -    

 set_intersection():
   

 set_difference():
   -  

_symmetric_difference():
    -   
*/

int main()
{
string str1[] = { "", "", "", "-" };
string str2[] = { "", "", "" };
ostream_iterator< string > ofile( cout, " " );

set<string,less<string>,allocator> set1( str1, str1+4 );
set<string,less<string>,allocator> set2( str2, str2+3 );

cout << "  #1:\n\t";
copy( set1.begin(), set1.end(), ofile ); cout << "\n\n";
cout << "  #2:\n\t";
copy( set2.begin(), set2.end(), ofile ); cout << "\n\n";

set<string,less<string>,allocator> res;
set_union( set1.begin(), set1.end(),
set2.begin(), set2.end(),
inserter( res, res.begin() ));

cout << " set_union():\n\t";
copy( res.begin(), res.end(), ofile ); cout << "\n\n";

res.clear();
set_intersection( set1.begin(), set1.end(),
set2.begin(), set2.end(),
inserter( res, res.begin() ));

cout << " set_intersection():\n\t";
copy( res.begin(), res.end(), ofile ); cout << "\n\n";

res.clear();
set_difference( set1.begin(), set1.end(),
set2.begin(), set2.end(),
inserter( res, res.begin() ));

cout << " set_difference():\n\t";
copy( res.begin(), res.end(), ofile ); cout << "\n\n";

res.clear();
set_symmetric_difference( set1.begin(), set1.end(),
set2.begin(), set2.end(),
inserter( res, res.begin() ));

cout << " set symmetric difference():\n\t";


                                                               ++   1160

   }

                                               sort()

   template< class RandomAccessIterator >
   void
   sort( RandomAccessIterator first,
      RandomAccessIterator last );

   template< class RandomAccessIterator, class Compare >
   void
   sort( RandomAccessIterator first,
      RandomAccessIterator last, Compare comp );

   sort()     [first,last)  ,
  ,     . 
      comp. ( 
      stable_sort().)
   ,    
sort(),        ,   
binary_search(), equal_range()  inplace_merge().

                            stable_partition()

   template< class BidirectionalIterator, class Predicate >
   BidirectionalIterator
   stable_partition( BidirectionalIterator first,
      BidirectionalIterator last,
      Predicate pred );

   stable_partition()    ,  partition(),  
    .   
,     partition(),   
stable_partition().

                                                               ++   1161

#include <algorithm>
#include <vector>
#include <iostream.h>

/* :
 :
29 23 20 22 17 15 26 51 19 12 35 40
    :
20 22 26 12 40 29 23 17 15 51 19
   ,  25:
23 20 22 17 15 19 12 29 26 51 35 40
*/

class even_elem {
public:
bool operator()( int elem ) {
return elem%2 ? false : true;
}
};

int main()
{
int ia[] = { 29,23,20,22,17,15,26,51,19,12,35,40 };
vector< int, allocator > vec( ia, ia+12 );
ostream_iterator< int > ofile( cout, " " );

cout << " :\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';

stable_partition( &ia[0], &ia[12], even_elem() );

cout << "    :\n";
copy( ia, ia+11, ofile ); cout << '\n';

stable_partition( vec.begin(), vec.end(),
bind2nd(less<int>(),25) );

cout << "   ,  25:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
   }

                                     stable_sort()

   template< class RandomAccessIterator >
   void
   stable_sort( RandomAccessIterator first,
      RandomAccessIterator last );

   template< class RandomAccessIterator, class Compare >
   void
   stable_sort( RandomAccessIterator first,
      RandomAccessIterator last, Compare comp );

                                                               ++   1162

   stable_sort()    ,  sort(),   
    .   
       comp.

#include <algorithm>
#include <vector>
#include <iostream.h>

/* :
 :
  29 23 20 22 12 17 15 26 51 19 12 23 35 40

  -     :
   12 12 15 17 19 20 22 23 23 26 29 35 40 51

 :   :
   51 40 35 29 26 23 23 22 20 19 17 15 12 12
*/

int main()
{
int ia[] = { 29,23,20,22,12,17,15,26,51,19,12,23,35,40 };
vector< int, allocator > vec( ia, ia+14 );
ostream_iterator< int > ofile( cout, " " );

cout << " :\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';

stable_sort( &ia[0], &ia[14] );

cout << "  -   "
<< "  :\n";
copy( ia, ia+14, ofile ); cout << '\n';

stable_sort( vec.begin(), vec.end(), greater<int>() );

cout << " :   :\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';

   }

                                   swap()

   template< class Type >
   void
   swap ( Type &ob1, Type &ob2 );

   swap()    ob1  ob2.

                                                               ++   1163

#include <algorithm>
#include <vector>
#include <iostream.h>

/* :
 :
   3 4 5 0 1 2

  swap()    :
   0 1 2 3 4 5
*/

int main()
{
int ia[] = { 3, 4, 5, 0, 1, 2 };
vector< int, allocator > vec( ia, ia+6 );

for ( int ix = 0; ix < 6; ++ix )
for ( int iy = ix; iy < 6; ++iy ) {
if ( vec[iy] < vec[ ix ] )
swap( vec[iy], vec[ix] );
}

ostream_iterator< int > ofile( cout, " " );

cout << " :\n";
copy( ia, ia+6, ofile ); cout << '\n';

cout << "  swap()   "
<< " :\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';

   }

                                  swap_ranges()

   template< class ForwardIterator1, class ForwardIterator2 >
   ForwardIterator2
   swap_ranges( ForwardIterator1 first1, ForwardIterator1 last,
      ForwardIterator2 first2 );

   swap_ranges()     [first1,last)  
 ,   first2.     
    .    ,  
        ,    ,
    .   ,
     .

                                                               ++   1164
#include <algorithm>
#include <vector>
#include <iostream.h>

/* :
    :
0 1 2 3 4 5 6 7 8 9
    :
5 6 7 8 9
    :
5 6 7 8 9 0 1 2 3 4
     :
5 6 7 8 9 5 6 7 8 9
     :
0 1 2 3 4
*/

int main()
{
int ia[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int ia2[] = { 5, 6, 7, 8, 9 };

vector< int, allocator > vec( ia, ia+10 );
vector< int, allocator > vec2( ia2, ia2+5 );

ostream_iterator< int > ofile( cout, " " );

cout << "   
:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';

cout << "   
:\n";
copy( vec2.begin(), vec2.end(), ofile ); cout << '\n';

//    
swap_ranges( &ia[0], &ia[5], &ia[5] );

cout << "    :\n";
copy( ia, ia+10, ofile ); cout << '\n';
//   
vector< int, allocator >::iterator last =
find( vec.begin(), vec.end(), 5 );

swap_ranges( vec.begin(), last, vec2.begin() );

cout << "     :\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';

cout << "     :\n";
copy( vec2.begin(), vec2.end(), ofile ); cout << '\n';

   }

                                                               ++   1165

                                 transform()

   template< class InputIterator, class OutputIterator,
   class UnaryOperation >
   OutputIterator
   transform( InputIterator first, InputIterator last,
       OutputIterator result, UnaryOperation op );

   template< class InputIterator1, class InputIterator2,
      class OutputIterator, class BinaryOperation >
   OutputIterator
   transform( InputIterator1 first1, InputIterator1 last,
      InputIterator2 first2, OutputIterator result,
      BinaryOperation bop );

     transform()   , 
 op      [first,last). ,  
 {0,1,1,2,3,5}  - Double,  
,     {0,2,2,4,6,10}.
       ,   
bop   ,       [first1,last1),   
 ,   first2.    ,
     ,   . , 
  {1,3,5,9}  {2,4,6,8}  - AddAndDouble,
       ,  
{6,14,22,34}.
     transform()    
  ,     result.   
      ,    
      transform().  
        .

                                                               ++   1166

#include <algorithm>
#include <vector>
#include <math.h>
#include <iostream.h>

/*
* :
 : 3 5 8 13 21
   : 6 10 16 26 42
    : 3 5 8 13 21
*/

int double_val( int val ) { return val + val; }
int difference( int val1, int val2 ) {
return abs( val1 - val2 ); }

int main()
{
int ia[] = { 3, 5, 8, 13, 21 };
vector<int, allocator> vec( 5 );
ostream_iterator<int> outfile( cout, " " );

cout << " : ";
copy( ia, ia+5, outfile ); cout << endl;

cout << "   : ";
transform( ia, ia+5, vec.begin(), double_val );
copy( vec.begin(), vec.end(), outfile ); cout << endl;

cout << "    : ";
transform( ia, ia+5, vec.begin(), outfile, difference );
cout << endl;

   }

                                      unique()

   template< class ForwardIterator >
   ForwardIterator
   unique( ForwardIterator first,
      ForwardIterator last );

   template< class ForwardIterator, class BinaryPredicate >
   ForwardIterator
   unique( ForwardIterator first,
      ForwardIterator last, BinaryPredicate pred );

         .    
   ,     
.      ,    pred
   true.  ,  mississippi   
misisipi.  ,    'i'   ,  
  ,      's'.  ,   
   ,    .

                                                               ++   1167

       unique()      
remove().       :  
    ,   first.
          misisipippi,  ppi  ,
 .        
   erase()    . (
    erase()  ,  
  unique_copy().)

                                 unique_copy()

   template< class InputIterator, class OutputIterator >
   OutputIterator
   unique_copy( InputIterator first, InputIterator last,
      OutputIterator result );

   template< class InputIterator, class OutputIterator,
      class BinaryPredicate >
   OutputIterator
   unique_copy( InputIterator first, InputIterator last,
      OutputIterator result, BinaryPredicate pred );

   unique_copy()     ,   
        .  ,   
 ,     unique().  
   ,   
 .      
 .

                                                               ++   1168

#include <algorithm>
#include <vector>
#include <string>
#include <iterator>
#include <assert.h>

template <class Type>
void print_elements( Type elem ) { cout << elem << " "; }
void (*pfi)( int ) = print_elements;
void (*pfs)( string ) = print_elements;

int main()
{
int ia[] = { 0, 1, 0, 2, 0, 3, 0, 4, 0, 5 };

vector<int,allocator> vec( ia, ia+10 );
vector<int,allocator>::iterator vec_iter;

//   :    
// : 0 1 0 2 0 3 0 4 0 5
vec_iter = unique( vec.begin(), vec.end() );
for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";

//  ,   unique:

// : 0 1 2 3 4 5 2 3 4 5
sort( vec.begin(), vec.end() );
vec_iter = unique( vec.begin(), vec.end() );
for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";

//     
// : 0 1 2 3 4 5
vec.erase( vec_iter, vec.end() );
for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";

string sa[] = { "enough", "is", "enough",
"enough", "is", "good" };

vector<string,allocator> svec( sa, sa+6 );
vector<string,allocator> vec_result( svec.size() );
vector<string,allocator>::iterator svec_iter;

sort( svec.begin(), svec.end() );
svec_iter = unique_copy( svec.begin(), svec.end(),
vec_result.begin() );

// : enough good is
for_each( vec_result.begin(), svec_iter, pfs );
cout << "\n\n";

   }

                                                               ++   1169

                               upper_bound()

   template< class ForwardIterator, class Type >
   ForwardIterator
   upper_bound( ForwardIterator first,
      ForwardIterator last, const Type &value );

   template< class ForwardIterator, class Type, class Compare >
   ForwardIterator
   upper_bound( ForwardIterator first,
      ForwardIterator last, const Type &value,
      Compare comp );

   upper_bound()  ,     
  [first,last),     
 value,   .   ,  
   ,  ,  value. ,  
:

   int ia[] = {12,15,17,19,20,22,23,26,29,35,40,51};

   upper_bound()  value=21  ,   
22,    value=22    23.     
  ,     ; 
     comp.

                                                               ++   1170

#include <algorithm>
#include <vector>
#include <assert.h>
#include <iostream.h>

template <class Type>
void print_elements( Type elem ) { cout << elem << " "; }
void (*pfi)( int ) = print_elements;

int main()
{
int ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};
vector<int,allocator> vec(ia,ia+12);

sort(ia,ia+12);
int *iter = upper_bound(ia,ia+12,19);
assert( *iter == 20 );

sort( vec.begin(), vec.end(), greater<int>() );
vector<int,allocator>::iterator iter_vec;

iter_vec = upper_bound( vec.begin(), vec.end(),
27, greater<int>() );

assert( *iter_vec == 26 );

// : 51 40 35 29 27 26 23 22 20 19 17 15 12
vec.insert( iter_vec, 27 );
for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";

   }

                                 

       -. -    
   ,        
       -. ( 
-    [SEDGEWICK88].    -, 
            
 -.)        
( )     . , 
   ,   :

   X T O G S M N A E R A I

      X    ,     T,    O.
 ,        (..
       ,   ). G  S    T, 
M  N    O.  A  E   G, R  A   S, I  
 M,  N     .
         : make_heap(), pop_heap(),
push_heap()  sort_heap()       .
    ,  , 

                                                               ++   1171

 ,    (     
). ,        
,      .   
   ,       
pop_heap()  push_heap(),       . 
   ,       
 .

                                     make_heap()

   template< class RandomAccessIterator >
   void
   make_heap( RandomAccessIterator first,
      RandomAccessIterator last );

   template< class RandomAccessIterator, class Compare >
   void
   make_heap( RandomAccessIterator first,
      RandomAccessIterator last, Compare comp );

   make_heap()    ,  
[first,last).        ,
    ,      comp.

                                pop_heap()

   template< class RandomAccessIterator >
   void
   pop_heap( RandomAccessIterator first,
      RandomAccessIterator last );

   template< class RandomAccessIterator, class Compare >
   void
   pop_heap( RandomAccessIterator first,
      RandomAccessIterator last, Compare comp );

   pop_heap()      , 
 .      first  last-1,  
      [first,last-1).  
     - back()
  -     pop_back().  
     ,   
 ,      comp.

                                                               ++   1172

                                  push_heap()

   template< class RandomAccessIterator >
   void
   push_heap( RandomAccessIterator first,
      RandomAccessIterator last );

   template< class RandomAccessIterator, class Compare >
   void
   push_heap( RandomAccessIterator first,
      RandomAccessIterator last, Compare comp );

   push_heap() ,  ,  
[first,last-1),            
last-1.     [first,last)    . 
 push_heap()       ,
,   push_back() (    ).  
     ,   
 ;     comp.

                                  sort_heap()

   template< class RandomAccessIterator >
   void
   sort_heap( RandomAccessIterator first,
      RandomAccessIterator last );

   template< class RandomAccessIterator, class Compare >
   void
   sort_heap( RandomAccessIterator first,
      RandomAccessIterator last, Compare comp );

   sort_heap()     [first,last), ,
    ;      
. (,      !)  
     ,   
 ,      comp.

                                                               ++   1173
#include <algorithm>
#include <vector>
#include <assert.h>

template <class Type>
void print_elements( Type elem ) { cout << elem << " "; }

int main()
{
int ia[] = { 29,23,20,22,17,15,26,51,19,12,35,40 };
vector< int, allocator > vec( ia, ia+12 );

// : 51 35 40 23 29 20 26 22 19 12 17 15
make_heap( &ia[0], &ia[12] );
void (*pfi)( int ) = print_elements;
for_each( ia, ia+12, pfi ); cout << "\n\n";

// : 12 17 15 19 23 20 26 51 22 29 35 40
//  :    
make_heap( vec.begin(), vec.end(), greater<int>() );
for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";

// : 12 15 17 19 20 22 23 26 29 35 40 51
sort_heap( ia, ia+12 );
for_each( ia, ia+12, pfi ); cout << "\n\n";

//    
vec.push_back( 8 );

// : 8 17 12 19 23 15 26 51 22 29 35 40 20
//       
push_heap( vec.begin(), vec.end(), greater<int>() );
for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";

// : 12 17 15 19 23 20 26 51 22 29 35 40 8
//        

pop_heap( vec.begin(), vec.end(), greater<int>() );
for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";

   }
