|
Алгоритм adjacent_difference()
| template < class InputIterator, class OutputIterator >
OutputIterator adjacent_difference(
InputIterator first, InputIterator last,
OutputIterator result );
template < class InputIterator, class OutputIterator >
class BinaryOperation >
OutputIterator adjacent_difference(
InputIterator first, InputIterator last,
| OutputIterator result, BinaryOperation op );
Первый вариант adjacent_difference() создает новую последовательность, в которой значение каждого элемента, кроме первого, равно разности между текущим и предыдущим элементами исходной последовательности. Например, если дано {0,1,1,2,3,5,8}, то первым элементом новой последовательности будет копия: 0. Вторым – разность первых двух элементов исходной последовательности: 1. Третий элемент равен разности третьего и второго элементов: 1‑1=0, и т.д. В результате мы получим последовательность {0,1,0,1,1,2,3}.
Во втором варианте разность соседних элементов вычисляется с помощью указанной бинарной операции. Возьмем ту же исходную последовательность и передадим объект-функцию times<int>. Как и раньше, первый элемент просто копируется. Второй элемент – это произведение первого и второго элементов исходной последовательности; он тоже равен 0. Третий элемент – произведение второго и третьего элементов исходной последовательности: 1 * 1 = 1, и т.д. Результат – {0,1,2,6,15,40}.
В обоих вариантах итератор OutputIterator указывает на элемент, расположенный за последним элементом новой последовательности. adjacent_difference() – это один из численных алгоритмов, для его использования в программу необходимо включить заголовочный файл <numeric>.
| #include <numeric>
#include <list>
#include <functional>
#include <iterator>
#include <iostream.h>
int main()
{
int ia[] = { 1, 1, 2, 3, 5, 8 };
list<int,allocator> ilist(ia, ia+6);
list<int,allocator> ilist_result(ilist.size());
adjacent_difference(ilist.begin(), ilist.end(),
ilist_result.begin() );
// на выходе печатается:
// 1 0 1 1 2 3
copy( ilist_result.begin(), ilist_result.end(),
ostream_iterator<int>(cout," "));
cout << endl;
adjacent_difference(ilist.begin(), ilist.end(),
ilist_result.begin(), times<int>() );
// на выходе печатается:
// 1 1 2 6 15 40
copy( ilist_result.begin(), ilist_result.end(),
ostream_iterator<int>(cout," "));
cout << endl;
| }
Алгоритм adjacent_find()
| template < class ForwardIterator >
ForwardIterator
adjacent_find( ForwardIterator first, ForwardIterator last );
template < class ForwardIterator, class BinaryPredicate >
ForwardIterator
adjacent_find( ForwardIterator first,
| ForwardIterator last, Predicate pred );
adjacent_find() ищет первую пару одинаковых соседних элементов в диапазоне, ограниченном итераторами [first,last). Если соседние дубликаты найдены, то алгоритм возвращает однонаправленный итератор, указывающий на первый элемент пары, в противном случае возвращается last. Например, если дана последовательность {0,1,1,2,2,4}, то будет найдена пара [1,1] и возвращен итератор, указывающий на первую единицу.
| #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(), greater<int>() );
found_it = binary_search( vec.begin(), vec.end(),
26, greater<int>() );
assert( found_it == true );
| }
Алгоритм copy()
| template < class InputIterator, class OutputIterator >
OutputIterator
copy( InputIterator first1, InputIterator last,
| OutputIterator first2 )
copy() копирует последовательность элементов, ограниченную парой итераторов [first,last), в другой контейнер, начиная с позиции, на которую указывает first2. Алгоритм возвращает итератор, указывающий на элемент второго контейнера, следующий за последним вставленным. Например, если дана последовательность {0,1,2,3,4,5}, мы можем сдвинуть элементы на один влево с помощью такого вызова:
| int ia[] = {0, 1, 2, 3, 4, 5 };
// сдвинуть элементы влево на один, получится {1,2,3,4,5,5}
| copy( ia+1, ia+6, ia );
copy() начинает копирование со второго элемента ia, копируя 1 в первую позицию, и так далее, пока каждый элемент не окажется в позиции на одну левее исходной.
| #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_traits<InputIterator>::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 );
list<string,allocator> textlines;
typedef list<string,allocator>::difference_type diff_type;
istream_iterator< string, diff_type > instream( infile ),
eos;
copy( instream, eos, back_inserter( textlines ));
string search_item( "fiery" );
/*********************************************************************
* примечание: ниже показан интерфейс count(), принятый в
* стандартной библиотеке. В текущей реализации библиотеки
* от RogueWave поддерживается более ранняя версия, в которой
* типа distance_type еще не было, так что count()
* возвращала результат в последнем аргументе
*
* вот как должен выглядеть вызов:
*
* typedef iterator_traits<InputIterator>::
* distance_type dis_type;
*
* dis_type elem_count;
* elem_count = count( textlines.begin(), textlines.end(),
* search_item );
***********************************************************************
int elem_count = 0;
list<string,allocator>::iterator
ibegin = textlines.begin(),
iend = textlines.end();
// устаревшая форма count()
count( ibegin, iend, search_item, elem_count );
cout << "count(): " << search_item
<< " встречается " << elem_count << " раз(а)\n";
| }
Алгоритм count_if()
| template < class InputIterator, class Predicate >
iterator_traits<InputIterator>::distance_type
count_if( InputIterator first,
| InputIterator last, Predicate pred );
count_if() применяет предикат pred к каждому элементу из диапазона, ограниченного парой итераторов [first,last). Алгоритм сообщает, сколько раз предикат оказался равным true.
| #include <algorithm>
#include <list>
#include <iostream.h>
class Even {
public:
bool operator()( int val )
{ return val%2 ? false : true; }
};
int main()
{
int ia[] = {0,1,1,2,3,5,8,13,21,34};
list< int,allocator > ilist( ia, ia+10 );
/*
* не поддерживается в текущей реализации
*****************************************************
typedef
iterator_traits<InputIterator>::distance_type
distance_type;
distance_type ia_count, list_count;
// счетчик четных элементов: 4
ia_count = count_if( &ia[0], &ia[10], Even() );
list_count = count_if( ilist.begin(), ilist_end(),
bind2nd(less<int>(),10) );
******************************************************
*/
int ia_count = 0;
count_if( &ia[0], &ia[10], Even(), ia_count );
// печатается:
// count_if(): есть 4 четных элемент(а).
cout << "count_if(): есть "
<< ia_count << " четных элемент(а).\n";
int list_count = 0;
count_if( ilist.begin(), ilist.end(),
bind2nd(less<int>(),10), list_count );
// печатается:
// count_if(): есть 7 элемент(ов), меньших 10.
cout << "count_if(): есть "
<< list_count
<< " элемент(ов), меньших 10.\n";
| }
Алгоритм 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 );
list< int, allocator > ilist2( ia2, ia2+9 );
// печатается: список ilist равен ilist2? Да.
res = equal( ilist.begin(), ilist.end(), ilist2.begin() );
cout << "список ilist равен ilist2? "
<< ( res ? "Да" : "Нет" ) << ".\n";
// false: 0, 2, 8 не являются равными и нечетными
// печатается: список ilist equal_and_odd() ilist2? Нет.
res = equal( ilist.begin(), ilist.end(),
ilist2.begin(), equal_and_odd() );
cout << "список ilist equal_and_odd() ilist2? "
<< ( res ? "Да" : "Нет" ) << ".\n";
return 0;
| }
Алгоритм equal_range()
| template< class ForwardIterator, class Type >
pair< ForwardIterator, ForwardIterator >
equal_range( ForwardIterator first,
ForwardIterator last, const Type &value );
template< class ForwardIterator, class Type, class Compare >
pair< ForwardIterator, ForwardIterator >
equal_range( ForwardIterator first,
ForwardIterator last, const Type &value,
| Compare comp );
equal_range() возвращает пару итераторов: первый представляет значение итератора, возвращаемое алгоритмом lower_bound(), второй – алгоритмом upper_bound(). (О семантике этих алгоритмов рассказано в их описаниях.) Например, дана последовательность:
int ia[] = {12,15,17,19,20,22,23,26,29,35,40,51};
Обращение к equal_range() со значением 21 возвращает пару итераторов, в которой оба указывают на значение 22. Обращение же со значением 22 возвращает пару итераторов, где first указывает на 22, а second – на 23. В первом варианте при сравнении используется оператор “меньше”, определенный для типа элементов контейнера; во втором – предикат comp.
| #include <algorithm>
#include <vector>
#include <utility>
#include <iostream.h>
/* печатается:
последовательность элементов массива после сортировки:
12 15 17 19 20 22 23 26 29 35 40 51
результат equal_range при поиске значения 23:
*ia_iter.first: 23 *ia_iter.second: 26
результат equal_range при поиске отсутствующего значения 21:
*ia_iter.first: 22 *ia_iter.second: 22
последовательность элементов вектора после сортировки:
51 40 35 29 26 23 22 20 19 17 15 12
результат equal_range при поиске значения 26:
*ivec_iter.first: 26 *ivec_iter.second: 23
результат equal_range при поиске отсутствующего значения 21:
*ivec_iter.first: 20 *ivec_iter.second: 20
*/
int main()
{
int ia[] = { 29,23,20,22,17,15,26,51,19,12,35,40 };
vector< int, allocator > ivec( ia, ia+12 );
ostream_iterator< int > ofile( cout, " " );
sort( &ia[0], &ia[12] );
cout << "последовательность элементов массива после сортировки:\n";
copy( ia, ia+12, ofile ); cout << "\n\n";
pair< int*,int* > ia_iter;
ia_iter = equal_range( &ia[0], &ia[12], 23 );
cout << "результат equal_range при поиске значения 23:\n\t"
<< "*ia_iter.first: " << *ia_iter.first << "\t"
<< "*ia_iter.second: " << *ia_iter.second << "\n\n";
ia_iter = equal_range( &ia[0], &ia[12], 21 );
cout << "результат equal_range при поиске "
<< "отсутствующего значения 21:\n\t"
<< "*ia_iter.first: " << *ia_iter.first << "\t"
<< "*ia_iter.second: " << *ia_iter.second << "\n\n";
sort( ivec.begin(), ivec.end(), greater<int>() );
cout << "последовательность элементов вектора после сортировки:\n";
copy( ivec.begin(), ivec.end(), ofile ); cout << "\n\n";
typedef vector< int, allocator >::iterator iter_ivec;
pair< iter_ivec, iter_ivec > ivec_iter;
ivec_iter = equal_range( ivec.begin(), ivec.end(), 26,
greater<int>() );
cout << "результат equal_range при поиске значения 26:\n\t"
<< "*ivec_iter.first: " << *ivec_iter.first << "\t"
<< "*ivec_iter.second: " << *ivec_iter.second
<< "\n\n";
ivec_iter = equal_range( ivec.begin(), ivec.end(), 21,
greater<int>() );
cout << "результат equal_range при поиске отсутствующего значения 21:\n\t"
<< "*ivec_iter.first: " << *ivec_iter.first << "\t"
<< "*ivec_iter.second: " << *ivec_iter.second
<< "\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 list<string,allocator>::iterator iterator;
iterator ibegin = il.begin(), iend = il.end();
fill( ++ibegin, --iend, the_lang );
cout << "список после fill(++ibegin,--iend):\n";
copy( il.begin(), il.end(), sofile ); cout << "\n\n";
| }
Алгоритм fill_n()
| 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, allocator > svec( sa, sa+13 );
cout << "исходная последовательность строк:\n\t";
for_each( svec.begin(), svec.end(), print_elements() );
cout << "\n\n";
fill_n( svec.begin()+3, count*2, replacement );
print_elements::reset_line_cnt();
cout << "последовательность после применения fill_n():\n\t";
for_each( svec.begin(), svec.end(), print_elements() );
cout << "\n";
| }
Алгоритм 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, less<string>, allocator > friendset;
};
set< string, less<string>, allocator > OurFriends::friendset;
int main()
{
string Pooh_friends[] = { "Пятачок", "Тигра", "Иа-Иа" };
string more_friends[] = { "Квазимодо", "Чип", "Пятачок" };
list<string,allocator> lf( more_friends, more_friends+3 );
// заполнить список друзей Пуха
OurFriends::FriendSet( Pooh_friends, 3 );
list<string,allocator>::iterator our_mutual_friend;
our_mutual_friend =
find_if( lf.begin(), lf.end(), OurFriends());
// печатается:
// Представьте-ка, наш друг Пятачок - также друг Пуха.
if ( our_mutual_friend != lf.end() )
cout << "Представьте-ка, наш друг "
<< *our_mutual_friend
<< " также друг Пуха.\n";
return 0;
| }
Алгоритм 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_to<int>() );
assert( found_it2 == ivec.begin()+10 );
cout << "ok: find_end правильно вернула начало "
<< "последнего вхождения последовательности: 3,7,6!\n";
| }
Алгоритм find_first_of()
| template< class ForwardIterator1, class ForwardIterator2 >
ForwardIterator1
find_first_of( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2 );
template< class ForwardIterator1, class ForwardIterator2,
class BinaryPredicate >
ForwardIterator1
find_first_of( ForwardIterator1 first1, ForwardIterator1 last1,
ForwardIterator2 first2, ForwardIterator2 last2,
| BinaryPredicate pred );
Последовательность, ограниченная парой [first2,last2), содержит элементы, поиск которых ведется в последовательности, ограниченной итераторами [first1,last1). Допустим, нужно найти первую гласную в последовательности символов synesthesia. Для этого определим вторую последовательность как aeiou. find_first_of() возвращает итератор, указывающий на первое вхождение любого элемента последовательности гласных букв, в данном случае e. Если же первая последовательность не содержит ни одного элемента из второй, то возвращается last1. В первом варианте используется оператор равенства, определенный для типа элементов контейнера, а во втором – бинарный предикат pred.
| #include <algorithm>
#include <vector>
#include <string>
#include <iostream.h>
int main()
{
string s_array[] = { "Ee", "eE", "ee", "Oo", "oo", "ee" };
// возвращает первое вхождение "ee" -- &s_array[2]
string to_find[] = { "oo", "gg", "ee" };
string *found_it =
find_first_of( s_array, s_array+6,
to_find, to_find+3 );
// печатается:
// найдено: ee
// &s_array[2]: 0x7fff2dac
// &found_it: 0x7fff2dac
if ( found_it != &s_array[6] )
cout << "найдено: " << *found_it << "\n\t"
<< "&s_array[2]:\t" << &s_array[2] << "\n\t"
<< "&found_it:\t" << found_it << "\n\n";
vector< string, allocator > svec( s_array, s_array+6);
vector< string, allocator > svec_find( to_find, to_find+2 );
// возвращает вхождение "oo" -- svec.end()-2
vector< string, allocator >::iterator found_it2;
found_it2 = find_first_of(
svec.begin(), svec.end(),
svec_find.begin(), svec_find.end(),
equal_to<string>() );
// печатает:
// тоже найдено: oo
// &svec.end()-2: 0x100067b0
// &found_it2: 0x100067b0
if ( found_it2 != svec.end() )
cout << "тоже найдено: " << *found_it2 << "\n\t"
<< "&svec.end()-2:\t" << svec.end()-2 << "\n\t"
<< "&found_it2:\t" << found_it2 << "\n";
| }
Алгоритм for_each()
| 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(), greater<int>() );
sort( ivect2.begin(), ivect2.end(), greater<int>() );
res = includes( ivect1.begin(), ivect1.end(),
ivect2.begin(), ivect2.end(),
greater<int>() );
// печатает: каждый элемент ivect2 входит в ivect1? Да
cout << "каждый элемент ivect2 входит в ivect1? "
<< (res ? "Да" : "Нет") << endl;
| }
Алгоритм inner_product()
| template< class InputIterator1, class InputIterator2
class Type >
Type
inner_product(
InputIterator1 first1, InputIterator1 last,
InputIterator2 first2, Type init );
template< class InputIterator1, class InputIterator2
class Type,
class BinaryOperation1, class BinaryOperation2 >
Type
inner_product(
InputIterator1 first1, InputIterator1 last,
InputIterator2 first2, Type init,
| BinaryOperation1 op1, BinaryOperation2 op2 );
Первый вариант суммирует произведения соответственных членов обеих последовательностей и прибавляет результат к начальному значению init. Первая последовательность ограничена итераторами [first1,last1), вторая начинается с first2 и обходится синхронно с первой. Например, если даны последовательности {2,3,5,8} и {1,2,3,4}, то результат вычисляется следующим образом:
2*1 + 3*2 + 5*3 + 8*4
Если начальное значение равно 0, алгоритм вернет 55.
Во втором варианте вместо сложения используется бинарная операция op1, а вместо умножения – бинарная операция op1. Например, если для приведенных выше последовательностей применить вычитание в качестве op1 и сложение в качестве op2, то результат будет вычисляться так:
(2+1) - (3+2) - (5+3) - (8+4)
inner_product() – это один из численных алгоритмов. Для его использования в программу необходимо включить заголовочный файл <numeric>.
| #include <numeric>
#include <vector>
#include <iostream.h>
int main()
{
int ia[] = { 2, 3, 5, 8 };
int ia2[] = { 1, 2, 3, 4 };
// перемножить пары элементов из обоих массивов,
// сложить и добавить начальное значение: 0
int res = inner_product( &ia[0], &ia[4], &ia2[0], 0 );
// печатает: скалярное произведение массивов: 55
cout << "скалярное произведение массивов: "
<< res << endl;
vector<int, allocator> vec( ia, ia+4 );
vector<int, allocator> vec2( ia2, ia2+4 );
// сложить пары элементов из обоих векторов,
// вычесть из начального значения: 0
res = inner_product( vec.begin(), vec.end(),
vec2.begin(), 0,
minus<int>(), plus<int>() );
// печатает: скалярное произведение векторов: -28
cout << "скалярное произведение векторов: "
<< res << endl;
return 0;
| }
Алгоритм inplace_merge()
| template< class BidirectionalIterator >
void
inplace_merge( BidirectionalIterator first,
BidirectionalIterator middle,
BidirectionalIterator last );
template< class BidirectionalIterator, class Compare >
void
inplace_merge( BidirectionalIterator first,
BidirectionalIterator middle,
| BidirectionalIterator last, Compare comp );
inplace_merge() объединяет две соседние отсортированные последовательности, ограниченные парами итераторов [first,middle) и [middle,last). Результирующая последовательность затирает исходные, начиная с позиции first. В первом варианте для упорядочения элементов используется оператор “меньше”, определенный для типа элементов контейнера, во втором – операция сравнения, переданная программистом.
| #include <algorithm>
#include <vector>
#include <iostream.h>
template <class Type>
void print_elements( Type elem ) { cout << elem << " "; }
/*
* печатает:
ia разбит на два отсортированных подмассива:
12 15 17 20 23 26 29 35 40 51 10 16 21 41 44 54 62 65 71 74
ia inplace_merge:
10 12 15 16 17 20 21 23 26 29 35 40 41 44 51 54 62 65 71 74
ivec разбит на два отсортированных подвектора:
51 40 35 29 26 23 20 17 15 12 74 71 65 62 54 44 41 21 16 10
ivec inplace_merge:
74 71 65 62 54 51 44 41 40 35 29 26 23 21 20 17 16 15 12 10
*/
int main()
{
int ia[] = { 29,23,20,17,15,26,51,12,35,40,
74,16,54,21,44,62,10,41,65,71 };
vector< int, allocator > ivec( ia, ia+20 );
void (*pfi)( int ) = print_elements;
// отсортировать обе подпоследовательности
sort( &ia[0], &ia[10] );
sort( &ia[10], &ia[20] );
cout << "ia разбит на два отсортированных подмассива: \n";
for_each( ia, ia+20, pfi ); cout << "\n\n";
inplace_merge( ia, ia+10, ia+20 );
cout << "ia inplace_merge:\n";
for_each( ia, ia+20, pfi ); cout << "\n\n";
sort( ivec.begin(), ivec.begin()+10, greater<int>() );
sort( ivec.begin()+10, ivec.end(), greater<int>() );
cout << "ivec разбит на два отсортированных подвектора: \n";
for_each( ivec.begin(), ivec.end(), pfi ); cout << "\n\n";
inplace_merge( ivec.begin(), ivec.begin()+10,
ivec.end(), greater<int>() );
cout << "ivec inplace_merge:\n";
for_each( ivec.begin(), ivec.end(), pfi ); cout << endl;
| }
Алгоритм 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;
| }
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|
