Chapter 1. Обобщенные алгоритмы в алфавитном порядке

// следует читать: включая first и все последующие
// элементы до last, но не включая сам last
[first, last)

first == last

#include <algorithm>

#include <numeric>

// Алгоритм accumulate()
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);

#include <numeric>
#include <list>
#include <functional>
#include <iostream>

/*
 * выход:
 * accumulate()
 *     работает с последовательностью {1,2,3,4}
 *    результат для сложения по умолчанию: 10
 *    результат для объекта-функции plus<int>: 10
 */

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

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

    std::cout << "accumulate()\n\t"
         << "работает с последовательностью {1,2,3,4}\n\t"
         << "результат для сложения по умолчанию: "
         << ia_result << "\n\t"
         << "результат для объекта-функции plus<int>: "
         << ilist_res
         << std::endl;

    return 0;
}

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

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

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

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

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

    // на выходе печатается:
    // 1 0 1 1 2 3
    std::copy(ilist_result.begin(), ilist_result.end(), ostream_iterator<int>(std::cout," "));
    std::cout << std::endl;

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

    // на выходе печатается:
    // 1 1 2 6 15 40
    std::copy(ilist_result.begin(), ilist_result.end(), ostream_iterator<int>(std::cout," "));
    std::cout << std::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);

#include <algorithm>
#include <vector>
#include <iostream>
#include <cassert>

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

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

     int *piter;
    std::vector<int>::iterator iter;

    // piter указывает на ia[1]
    piter = std::adjacent_find(ia, ia+4);
    assert(*piter == ia[1]);

    // iter указывает на vec[2]
    iter = std::adjacent_find(vec.begin(), vec.end(), TwiceOver());
    assert(*iter == vec[2]);

    // пришли сюда: все хорошо
    std::cout <<"ok: adjacent-find() завершился успешно!\n";
    return 0;
}

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

#include <algorithm>
#include <vector>
#include <cassert>

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

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

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

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

int ia[] = {0, 1, 2, 3, 4, 5 };
// сдвинуть элементы влево на один, получится {1,2,3,4,5,5}
copy(ia+1, ia+6, ia);

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

/* печатается:
   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 };
    std::vector<int> vec(ia, ia+7);
    ostream_iterator<int>  ofile(std::cout, " ");

    std::cout << "исходная последовательность элементов:\n";
    std::copy(vec.begin(), vec.end(), ofile); std::cout << '\n';

    // сдвиг влево на один элемент
    std::copy(ia+1, ia+7, ia);

    std::cout << "сдвиг массива влево на 1:\n";
    std::copy(ia, ia+7, ofile); std::cout << '\n';

    // сдвиг влево на два элемента
    std::copy(vec.begin()+2, vec.end(), vec.begin());

    std::cout << "сдвиг вектора влево на 2:\n";
    std::copy(vec.begin(), vec.end(), ofile); std::cout << '\n';
}

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

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

class print_elements {
public:
   void operator()(std::string elem) {
        std::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() {
   std::string sa[] = {
      "The", "light", "untonsured", "hair",
     "grained", "and", "hued", "like", "pale", "oak" };

   std::vector<std::string> svec(sa, sa+10);

   std::cout <<"исходный список строк:\n\t";
   std::for_each(svec.begin(), svec.end(), print_elements());
   std::cout << "\n\n";

   std::copy_backward(svec.begin()+1, svec.end()-3, svec.end());

   print_elements::reset_line_cnt();

   std::cout << "после copy_backward(begin+1, end-3, end):\n";
   std::for_each(svec.begin(), svec.end(), print_elements());
   std::cout << "\n";
}

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

#include <algorithm>
#include <string>
#include <list>
#include <iterator>

#include <cassert>
#include <iostream>
#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);

   std::list<std::string,allocator> textlines;

   typedef std::list<std::string,allocator>::difference_type diff_type;
   istream_iterator< std::string, diff_type > instream(infile),
                     eos;

   copy(instream, eos, back_inserter(textlines));

   std::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;
   std::list<std::string>::iterator
        ibegin = textlines.begin(),
        iend   = textlines.end();

   // устаревшая форма count()
   std::count(ibegin, iend, search_item, elem_count);

   std::cout <<"count(): " << search_item
       <<" встречается "  << elem_count << " раз(а)\n";
}

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

#include <algorithm>
#include <list>
#include <iostream>

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};
   std::list<int> 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(std::less<int>(),10));
    *******************************************************/
   int ia_count = 0;
   std::count_if(&ia[0], &ia[10], Even(), ia_count);

   // печатается:
   // count_if(): есть 4 четных элемент(а).
   std::cout << "count_if(): есть " << ia_count << " четных элемент(а).\n";

   int list_count = 0;
   std::count_if(ilist.begin(), ilist.end(),
             bind2nd(std::less<int>(),10), list_count);

   // печатается:
   // count_if(): есть 7 элемент(ов), меньших 10.
   std::cout << "count_if(): есть " << list_count << " элемент(ов), меньших 10.\n";
}

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

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

#include <algorithm>
#include <list>
#include <iostream>

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]);
   std::cout << "int ia[7] равно int ia2[9]? "
        <<(res ? "Да" : "Нет") << ".\n";

   std::list<int> ilist(ia,  ia+7);
   std::list<int> ilist2(ia2, ia2+9);

   // печатается: список ilist равен ilist2? Да.
   res = std::equal(ilist.begin(), ilist.end(), ilist2.begin());
   std::cout << "список ilist равен ilist2? "
        << (res ? "Да" : "Нет") << ".\n";

   // false: 0, 2, 8 не являются равными и нечетными
   // печатается: список ilist equal_and_odd() ilist2? Нет.
   res = std::equal(ilist.begin(), ilist.end(), ilist2.begin(), equal_and_odd());
   std::cout << "список ilist equal_and_odd() ilist2? "
        << (res ? "Да" : "Нет") << ".\n";

   return 0;
}

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

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

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

/* печатается:
   последовательность элементов массива после сортировки:
   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 };
   std::vector<int> ivec(ia, ia+12);
   ostream_iterator<int> ofile(std::cout, " ");

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

   std::cout << "последовательность элементов массива после сортировки:\n";
   std::copy(ia, ia+12, ofile); std::cout << "\n\n";

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

   std::cout << "результат equal_range при поиске значения 23:\n\t"
        << "*ia_iter.first: "  << *ia_iter.first << "\t"
        << "*ia_iter.second: " << *ia_iter.second <<"\n\n";

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

   std::cout << "результат equal_range при поиске "
        << "отсутствующего значения 21:\n\t"
        << "*ia_iter.first: "  << *ia_iter.first << "\t"
        << "*ia_iter.second: " << *ia_iter.second << "\n\n";

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

   std::cout << "последовательность элементов вектора после сортировки:\n";
   std::copy(ivec.begin(), ivec.end(), ofile); std::cout << "\n\n";

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

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

   std::cout << "результат equal_range при поиске значения 26:\n\t"
        << "*ivec_iter.first: "  << *ivec_iter.first <<"\t"
       <<"*ivec_iter.second: " << *ivec_iter.second
        << "\n\n";

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

   std::cout << "результат equal_range при поиске отсутствующего значения 21:\n\t"
        << "*ivec_iter.first: "  << *ivec_iter.first << "\t"
       << "*ivec_iter.second: " << *ivec_iter.second
        << "\n\n";
}

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

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

/* печатается:
   исходная последовательность элементов массива:
   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(std::cout, " ");

   std::cout << "исходная последовательность элементов массива:\n";
   copy(ia, ia+7, ofile); std::cout << "\n\n";

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

   std::cout << "массив после fill(ia+1,ia+6):\n";
   std::copy(ia, ia+7, ofile); std::cout << "\n\n";

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

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

   std::cout << "исходная последовательность элементов списка:\n";
   std::copy(il.begin(), il.end(), sofile); std::cout << "\n\n";

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

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

   std::cout << "список после fill(++ibegin,--iend):\n";
   std::copy(il.begin(), il.end(), sofile); std::cout << "\n\n";
}

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

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

class print_elements {
public:
   void operator()(std::string elem) {
      std::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(std::cout, " ");

   std::cout << "исходная последовательность элементов массива:\n";
   std::copy(ia, ia+7, iofile); std::cout << "\n\n";

   std::fill_n(ia+2, count, value);

   std::cout << "массив после fill_n(ia+2, 3, 9):\n";
   std::copy(ia, ia+7, iofile); std::cout << "\n\n";

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

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

   std::cout << "исходная последовательность строк:\n\t";
   std::for_each(svec.begin(), svec.end(), print_elements());
   std::cout << "\n\n";

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

   print_elements::reset_line_cnt();

   std::cout << "последовательность после применения fill_n():\n\t";
   std::for_each(svec.begin(), svec.end(), print_elements());
   std::cout << "\n";
}

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

#include <algorithm>
#include <iostream>
#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 = std::find(&array[0], &array[17], elem);

    // печатается: поиск первого вхождения 1 найдено!

    std::cout << "поиск первого вхождения "
         << elem <<"\t"
         << (found_it ? "найдено!\n" : "не найдено!\n");

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

    std::string s_elem(beethoven[1]);

    std::list<std::string> slist(beethoven, beethoven+6);
    std::list<std::string>::iterator iter;

    iter = std::find(slist.begin(), slist.end(), s_elem);

    // печатается: поиск первого вхождения Sonata32 найдено!

    std::cout << "поиск первого вхождения "
         << s_elem << "\t"
         << (found_it ? "найдено!\n" : "не найдено!\n");
}

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

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

// альтернатива оператору равенства
// возвращает true, если строка содержится в объекте-члене FriendSet    
class OurFriends {     // наши друзья
public:
    bool operator()(const std::string& str) {
       return (friendset.count(str));
    }

    static void
    FriendSet(const std::string *fs, int count) {
       std::copy(fs, fs+count, std::inserter(friendset, friendset.end()));
    }

private:
    static std::set<std::string, std::less<std::string>> friendset;
};

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

int main()
{
    std::string Pooh_friends[] = { "Пятачок", "Тигра", "Иа-Иа"  };
    std::string more_friends[] = { "Квазимодо", "Чип", "Пятачок" };
    std::list<std::string> lf(more_friends, more_friends+3);

    // заполнить список друзей Пуха
    OurFriends::FriendSet(Pooh_friends, 3);

    std::list<std::string,allocator>::iterator our_mutual_friend;
    our_mutual_friend = std::find_if(lf.begin(), lf.end(), OurFriends());

    // печатается:
    //   Представьте-ка, наш друг Пятачок - также друг Пуха.
    if (our_mutual_friend != lf.end())
         std::cout << "Представьте-ка, наш друг "
              << *our_mutual_friend
              << " также друг Пуха.\n";

    return 0;
}

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

#include <algorithm>
#include <vector>
#include <iostream>
#include <cassert>

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 = std::find_end(&array[0], &array[17],
                    &subarray[0], &subarray[3]);

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

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

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

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

    std::cout << "ok: find_end правильно вернула начало "
         << "последнего вхождения последовательности: 3,7,6!\n";
}

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

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

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

    // возвращает первое вхождение "ee" -- &s_array[2]
    std::string to_find[] = { "oo", "gg", "ee" };

    std::string *found_it =
        std::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])
       std::cout << "найдено: "      << *found_it     << "\n\t"
          << "&s_array[2]:\t" << &s_array[2]   << "\n\t"
          << "&found_it:\t"   << found_it      << "\n\n";

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

    // возвращает вхождение "oo" -- svec.end()-2
    std::vector<std::string>::iterator found_it2;

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

    // печатает:
    // тоже найдено: oo
    //         &svec.end()-2:  0x100067b0
    //         &found_it2:     0x100067b0

    if (found_it2 != svec.end())
       std::cout << "тоже найдено: "   << *found_it2   << "\n\t"
          << "&svec.end()-2:\t" << svec.end()-2 << "\n\t"
          << "&found_it2:\t"    << found_it2    << "\n";
}

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

#include <algorithm>
#include <vector>
#include <iostream>

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

int main() {
    std::vector<int> ivec;
    for (int ix = 0; ix < 10; ix++)
       ivec.push_back(ix);

    void (*pfi)(int) = print_elements;
    std::for_each(ivec.begin(), ivec.end(), pfi);
    return 0;
}

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

#include <algorithm>
#include <list>
#include <iostream>

int odd_by_twos() {
    static int seed = -1;
    return seed += 2;
}
template <class Type>
void print_elements(Type elem) { std::cout << elem << " "; }

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

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

    // печатается:
    // элементы в списке, первый вызов:
    // 1 3 5 7 9 11 13 15 17 19

    std::cout << "элементы в списке, первый вызов:\n";
    std::for_each(ilist.begin(), ilist.end(), pfi);
    std::generate(ilist.begin(), ilist.end(), odd_by_twos);

    // печатается:
    // элементы в списке, второй вызов:
    // 21 23 25 27 29 31 33 35 37 39
    std::cout <<"\n\nэлементы в списке, второй вызов:\n";
    std::for_each(ilist.begin(), ilist.end(), pfi);
    return 0;
}

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

#include <algorithm>
#include <iostream>
#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) { std::cout << elem << " "; }

int main() {
    std::list<int> 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

   std::cout << "generate_n с even_by_twos():\n";
   std::for_each(ilist.begin(), ilist.end(), pfi); std::cout << "\n";
   std::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

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

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

#include <algorithm>
#include <vector>
#include <iostream>

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 следует передавать отсортированные контейнеры
    std::sort(ia1, ia1+12); sort(ia2, ia2+6);

    // печатает: каждый элемент ia2 входит в ia1? Да

    bool res = includes(ia1, ia1+12, ia2, ia2+6);
    std::cout << "каждый элемент ia2 входит в ia1? "
         <<(res ? "Да" : "Нет") << std::endl;

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

    // отсортирован в порядке убывания
    std::sort(ivect1.begin(), ivect1.end(), std::greater<int>());
    std::sort(ivect2.begin(), ivect2.end(), std::greater<int>());

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

    // печатает: каждый элемент ivect2 входит в ivect1? Да
    std::cout << "каждый элемент ivect2 входит в ivect1? "
         << (res ? "Да" : "Нет") << std::endl;

}

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

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

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

#include <numeric>
#include <vector>
#include <iostream>

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

    // перемножить пары элементов из обоих массивов,
    // сложить и добавить начальное значение: 0

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

    // печатает: скалярное произведение массивов: 55
    std::cout << "скалярное произведение массивов: " << res << std::endl;

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

    // сложить пары элементов из обоих векторов,
    // вычесть из начального значения: 0

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

    // печатает: скалярное произведение векторов: -28
    std::cout << "скалярное произведение векторов: " << res << std::endl;

    return 0;
}

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

#include <algorithm>
#include <vector>
#include <iostream>

template <class Type>
void print_elements(Type elem) { std::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 };

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

    // отсортировать обе подпоследовательности
    std::sort(&ia[0], &ia[10]);
    std::sort(&ia[10], &ia[20]);

    std::cout << "ia разбит на два отсортированных подмассива: \n";
    std::for_each(ia, ia+20, pfi); std::cout << "\n\n";

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

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

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

    std::cout << "ivec разбит на два отсортированных подвектора: \n";
    std::for_each(ivec.begin(), ivec.end(), pfi); std::cout << "\n\n";

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

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

template< class ForwardIterator1, class ForwardIterator2 >
void
iter_swap(ForwardIterator1 a, ForwardIterator2 b);
// iter_swap() обменивает значения элементов, на которые указывают итераторы a и b.
#include <algorithm>
#include <list>
#include <iostream>

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

    typedef std::list<int>::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 }

    std::cout << "ilist после сортировки "пузырьком" с помощью iter_swap(): { ";
    for (iter1 = ilist.begin(); iter1 != iter_end; ++iter1)
          std::cout << *iter1 << " ";
        std::cout << "}\n";

    return 0;
}

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

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

#include <algorithm>
#include <list>
#include <string>
#include <cassert>
#include <iostream>

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

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

    bool res;

    // на втором элементе получаем false
    // Pooch меньше Pooh
    // на третьем элементе тоже получили бы false

    res = std::lexicographical_compare(arr1, arr1+3, arr2, arr2+3);
    assert(res == false);

    // получаем true: длина каждого элемента ilist2
    // меньше либо равна длине соответственного
    // элемента ilist1

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

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

    assert(res == true);

    std::cout << "ok: lexicographical_compare завершился успешно!\n";
}

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

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

#include <algorithm>
#include <vector>
#include <iostream>

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
    std::cout << "Первый элемент, перед которым можно вставить "
         << search_value
         << ", - это "
         << *ptr << std::endl
         << "Предыдущее значение равно "
         << *(ptr-1) << std::endl;

    std::vector<int> ivec(ia, ia+12);
    // отсортировать в порядке возрастания ...
    std::sort(ivec.begin(), ivec.end(), std::greater<int>());

    search_value = 26;
    std::vector<int>::iterator iter;
    // необходимо указать, как именно осуществлялась сортировка ...
    iter = std::lower_bound(ivec.begin(), ivec.end(),
                         search_value, std::greater<int>());
    // печатается:
    // Первый элемент, перед которым можно вставить 26, - это 26
    // Предыдущее значение равно 29
    std::cout << "Первый элемент, перед которым можно вставить "
         << search_value
         << ", - это "
         << *iter << std::endl
         << "Предыдущее значение равно "
         << *(iter-1) << std::endl;
        return 0;
}

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

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

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

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

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