C++ для начинающих

Алгоритм 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}.

Во втором варианте разность соседних элементов вычисляется с помощью указанной бинарной операции. Возьмем ту же исходную последовательность и передадим объект-функцию timesint. Как и раньше, первый элемент просто копируется. Второй элемент - это произведение первого и второго элементов исходной последовательности; он тоже равен 0. Третий элемент - произведение второго и третьего элементов исходной последовательности: 1 * 1 = 1, и т.д. Результат - {0,1,2,6,15,40}.

В обоих вариантах итератор OutputIterator указывает на элемент, расположенный за последним элементом новой последовательности. adjacent_difference() - это один из численных алгоритмов, для его использования в программу необходимо включить заголовочный файл .

#include numeric

#include list

#include functional

#include iterator

#include iostream.h

int main()

{

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

listint,allocator ilist(ia, ia+6);

listint,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_iteratorint(cout," "));

cout  endl;

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

ilist_result.begin(), timesint() );

// на выходе печатается:

// 1 1 2 6 15 40

copy( ilist_result.begin(), ilist_result.end(),

ostream_iteratorint(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] и возвращен итератор, указывающий на первую единицу.

#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. В первом варианте предполагается, что контейнер отсортирован с помощью оператора "меньше". Во втором варианте порядок определяется указанным объектом-функцией.

#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(), greaterint() );

found_it = binary_search( vec.begin(), vec.end(),

26, greaterint() );

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 в первую позицию, и так далее, пока каждый элемент не окажется в позиции на одну левее исходной.

#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. Тогда элемент 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";

}

Алгоритм count()

template  class InputIterator, class Type 

iterator_traitsInputIterator::distance_type

count( InputIterator first,

InputIterator last, const Type& value );

count() сравнивает каждый элемент со значением value в диапазоне, ограниченном парой итераторов [first,last), с помощью оператора равенства. Алгоритм возвращает число элементов, равных value. (Отметим, что в имеющейся у нас реализации стандартной библиотеки поддерживается более ранняя спецификация count().)

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

liststring,allocator textlines;

typedef liststring,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_traitsInputIterator::

*distance_type dis_type;

*

* dis_type elem_count;

* elem_count = count( textlines.begin(), textlines.end(),

*                     search_item );

***********************************************************************

int elem_count = 0;

liststring,allocator::iterator

ibegin = textlines.begin(),

iend   = textlines.end();

// устаревшая форма count()

count( ibegin, iend, search_item, elem_count );

cout  "count(): "   search_item

 " встречается "    elem_count   " раз(а)\n";

}

Алгоритм count_if()

template  class InputIterator, class Predicate 

iterator_traitsInputIterator::distance_type

count_if( InputIterator first,

InputIterator last, Predicate pred );

count_if() применяет предикат pred к каждому элементу из диапазона, ограниченного парой итераторов [first,last). Алгоритм сообщает, сколько раз предикат оказался равным true.

#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_traitsInputIterator::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(lessint(),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(lessint(),10), list_count );

// печатается:

//   count_if(): есть 7 элемент(ов), меньших 10.

cout  "count_if(): есть "

 list_count

 " элемент(ов), меньших 10.\n";

}

Алгоритм 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.

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

listint, 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;

}

Алгоритм 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 

pairForwardIterator, 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.

#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(), greaterint() );

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,

greaterint() );

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,

greaterint() );

cout   "результат equal_range при поиске отсутствующего значения 21:\n\t"

  "*ivec_iter.first: "    *ivec_iter.first   "\t"

  "*ivec_iter.second: "   *ivec_iter.second

  "\n\n";

}

Алгоритм fill()

template class ForwardIterator, class Type 

void

fill( ForwardIterator first,

ForwardIterator last, const Type& value );

fill() помещает копию значения value в каждый элемент диапазона, ограниченного парой итераторов [first,last).

#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 liststring,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()

template class ForwardIterator, class Size, class Type 

void

fill_n( ForwardIterator first,

Size n, const Type& value );

fill_n() присваивает count элементам из диапазона [first,first+count) значение value.

#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, allocatorsvec( 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";

}

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

}

Алгоритм find_if()

template class InputIterator, class Predicate 

InputIterator

find_if( InputIterator first,

InputIterator last, Predicate pred );

К каждому элементу из диапазона [first,last) последовательно применяется предикат pred. Если он возвращает true, поиск прекращается. find_if() возвращает итератор типа InputIterator, указывающий на найденный элемент; в противном случае возвращается last.

#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, lessstring, allocator  friendset;

};

set string, lessstring, allocator  OurFriends::friendset;

int main()

{

string Pooh_friends[] = { "Пятачок", "Тигра", "Иа-Иа"  };

string more_friends[] = { "Квазимодо", "Чип", "Пятачок" };

liststring,allocator lf( more_friends, more_friends+3 );

// заполнить список друзей Пуха

OurFriends::FriendSet( Pooh_friends, 3 );

liststring,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;

}

Алгоритм 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. В первом варианте используется оператор равенства, определенный для типа элементов контейнера, а во втором - бинарный предикат, переданный пользователем.

#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_toint() );

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() возвращает итератор, указывающий на первое вхождение любого элемента последовательности гласных букв, в данном случае 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_tostring() );

// печатает:

// тоже найдено: 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()

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, который может быть объектом-функцией или указателем на функцию.

#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, который может быть объектом-функцией или указателем на функцию.

#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). Первый вариант предполагает, что последовательности отсортированы в порядке, определяемом оператором “меньше”; второй - что порядок задается параметром-типом 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(), greaterint() );

sort( ivect2.begin(), ivect2.end(), greaterint() );

res = includes( ivect1.begin(), ivect1.end(),

ivect2.begin(), ivect2.end(),

greaterint() );

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

cout   "каждый элемент ivect2 входит в ivect1? "

  (res ? "Да" : "Нет")   endl;

}

Алгоритм inner_product()

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() - это один из численных алгоритмов. Для его использования в программу необходимо включить заголовочный файл .

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

vectorint, allocator vec(  ia,  ia+4 );

vectorint, allocator vec2( ia2, ia2+4 );

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

// вычесть из начального значения: 0

res = inner_product( vec.begin(), vec.end(),

vec2.begin(), 0,

minusint(), plusint() );

// печатает: скалярное произведение векторов: -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. В первом варианте для упорядочения элементов используется оператор “меньше”, определенный для типа элементов контейнера, во втором - операция сравнения, переданная программистом.

#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, greaterint() );

sort( ivec.begin()+10, ivec.end(),      greaterint() );

cout  "ivec разбит на два отсортированных подвектора: \n";

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

inplace_merge( ivec.begin(), ivec.begin()+10,

ivec.end(),   greaterint() );

cout  "ivec inplace_merge:\n";

for_each( ivec.begin(), ivec.end(), pfi ); cout  endl;

}

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

}

Алгоритм 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.

Во втором варианте алгоритма вместо оператора сравнения используется предикатный объект:

#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()

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.

#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(), greaterint() );

search_value = 26;

vector int, allocator ::iterator iter;

// необходимо указать, как именно

// осуществлялась сортировка ...

iter = lower_bound( ivec.begin(), ivec.end(),

search_value, greaterint() );

// печатается:

// Первый элемент, перед которым можно вставить 26, - это 26

// Предыдущее значение равно 29

cout  "Первый элемент, перед которым можно вставить "

 search_value

 ", - это "

 *iter  endl

 "Предыдущее значение равно "

 *(iter-1)  endl;

return 0;

}

Алгоритм max()

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

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. Алгоритм min_element()

template class ForwardIterator 

ForwardIterator

min_element( ForwardIterator first,

ForwardIterator last );

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

}

Алгоритм 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.

#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(), greaterint() );

sort( vec2.begin(), vec2.end(), greaterint() );

merge( vec1.begin(), vec1.end(),

vec2.begin(), vec2.end(),

vec_result.begin(), greaterint() );

// печатается: 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()

template class InputIterator1, class InputIterator2 

pairInputIterator1, InputIterator2

mismatch( InputIterator1 first,

InputIterator1 last, InputIterator2 first2 );

template class InputIterator1, class InputIterator2,

class BinaryPredicate 

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

pairint*,int* pair_ia = mismatch( ia, ia+7, ia2 );

// печатается: первая пара неодинаковых: ia: 3 и ia2: 4

cout  "первая пара неодинаковых: ia: "

*pair_ia.first  " и ia2: "

 *pair_ia.second  endl;

listint,allocator ilist(  ia,  ia+7  );

listint,allocator ilist2( ia2, ia2+7 );

typedef listint,allocator::iterator iter;

pairiter,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;

}

Алгоритм 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, то не удалось бы сгенерировать все перестановки.

#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()

{

vectorchar,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;

}

Алгоритм 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, упорядочены. В первом варианте для сравнения используется оператор "меньше", определенный для типа элементов контейнера, во втором - бинарная операция сравнения, заданная программистом.

#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_iteratorint 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(),   greaterint() );

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

}

Алгоритм partial_sort()

template  class RandomAccessIterator 

void

partial_sort( RandomAccessIterator first,

RandomAccessIterator middle,

RandomAccessIterator last );

template

partial_sort() сортирует часть последовательности, укладывающуюся в диапазон [first,middle). Элементы в диапазоне [middle,last) остаются неотсортированными. Например, если дан массив

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

то вызов 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 ia[] = {29,23,20,22,17,15,26,51,19,12,35,40};

int ia2[5];

Тогда обращение к partial_sort_copy(), где в качестве middle указан восьмой элемент:

partial_sort_copy( &ia[0], &ia[7], &ia[12],

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

заполняет массив 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_iteratorint 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(), greaterint() );

copy( res.begin(), res.end(), out ); cout  endl;

}

Алгоритм partial_sum()

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} и объект-функцию timesint. Результатом будет {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

частичная сумма элементов с использованием timesint():

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 "частичная сумма элементов с использованием timesint():\n";

partial_sum( vec.begin(), vec.end(), vec_res.begin(),

timesint() );

copy( vec_res.begin(), vec_res.end(), outfile );

cout endl;

}

Алгоритм 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(), рассматриваемый ниже.

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

vectorint, 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(lessint(),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), и, рассматривая ее как перестановку, возвращает предшествующую ей (о том, как упорядочиваются перестановки, говорилось в разделе 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].

#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_iteratorint ( 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()

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;

}

Алгоритм 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. Возвращаемый итератор указывает на элемент, расположенный за последним скопированным. Исходный контейнер остается без изменения.

#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(lessint(),10) );

vec.erase( iter, vec.end() );

cout  "последовательность после применения remove_if

Алгоритм replace()

template

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. Возвращаемый итератор указывает на элемент, расположенный за последним скопированным. Исходный контейнер остается без изменения.

#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. Алгоритм replace_copy_if()

templateclass 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. Возвращаемый итератор указывает на элемент, расположенный за последним скопированным. Исходный контейнер остается без изменения.

#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(lessint(),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 );

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. Возвращаемый итератор указывает на элемент, расположенный за последним скопированным. Исходный контейнер остается без изменения. #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() ); }

Алгоритм 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. Возвращаемый итератор указывает на элемент, расположенный за последним скопированным. Исходный контейнер остается без изменения.

#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()

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

}

Алгоритм 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. В первом варианте для сравнения элементов используется оператор равенства, во втором - указанная программистом операция сравнения.

#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} и {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 );

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.

#include algorithm

#include set

#include string

#include iostream.h

/* печатается:

элементы множества #1:

Иа-Иа Пух Пятачок Тигра

элементы множества #2:

Бука Пух Слонопотам

элементы set_union():

Бука Иа-Иа Пух Пятачок Слонопотам Тигра

элементы set_intersection():