<< Пред. стр. 110 (из 121) След. >>
Список литературы по разделу
Во втором варианте вместо оператора сложения используется бинарная операция, заданная программистом. Предположим, мы задали последовательность {1,2,3,4} и объект-функцию times
. Результатом будет {1,2,6,24}. В обоих случаях итератор записи OutputIterator указывает на элемент за последним элементом новой последовательности.
partial_sum() – это один из численных алгоритмов. Для его использования необходимо включить в программу стандартный заголовочный файл .
#include
#include
#include
/*
* печатается:
элементы: 1 3 4 5 7 8 9
частичная сумма элементов:
1 4 8 13 20 28 37
частичная сумма элементов с использованием times():
1 3 12 60 420 3360 30240
*/
int main()
{
const int ia_size = 7;
int ia[ ia_size ] = { 1, 3, 4, 5, 7, 8, 9 };
int ia_res[ ia_size ];
ostream_iterator< int > outfile( cout, " " );
vector< int, allocator > vec( ia, ia+ia_size );
vector< int, allocator > vec_res( vec.size() );
cout << "элементы: ";
copy( ia, ia+ia_size, outfile ); cout << endl;
cout << "частичная сумма элементов:\n";
partial_sum( ia, ia+ia_size, ia_res );
copy( ia_res, ia_res+ia_size, outfile ); cout << endl;
cout << "частичная сумма элементов с использованием times():\n";
partial_sum( vec.begin(), vec.end(), vec_res.begin(),
times() );
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
#include
#include
class even_elem {
public:
bool operator()( int elem )
{ return elem%2 ? false : true; }
};
/*
* печатается:
исходная последовательность:
29 23 20 22 17 15 26 51 19 12 35 40
разбиение, основанное на четности элементов:
40 12 20 22 26 15 17 51 19 23 35 29
разбиение, основанное на сравнении с 25:
12 23 20 22 17 15 19 51 26 29 35 40
*/
int main()
{
const int ia_size = 12;
int ia[ia_size] = { 29,23,20,22,17,15,26,51,19,12,35,40 };
vector< int, allocator > vec( ia, ia+ia_size );
ostream_iterator< int > outfile( cout, " " );
cout << "исходная последовательность: \n";
copy( vec.begin(), vec.end(), outfile ); cout << endl;
cout << "разбиение, основанное на четности элементов:\n";
partition( &ia[0], &ia[ia_size], even_elem() );
copy( ia, ia+ia_size, outfile ); cout << endl;
cout << "разбиение, основанное на сравнении с 25:\n";
partition( vec.begin(), vec.end(), bind2nd(less(),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
#include
#include
// печатается: 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
#include
#include
int main()
{
vector< int, allocator > vec;
for ( int ix = 0; ix < 20; ix++ )
vec.push_back( ix );
random_shuffle( vec.begin(), vec.end() );
// печатает:
// random_shuffle для последовательности 1 .. 20:
// 6 11 9 2 18 12 17 7 0 15 4 8 10 5 1 19 13 3 14 16
cout << "random_shuffle для последовательности 1 .. 20:\n";
copy( vec.begin(), vec.end(), ostream_iterator< int >( cout," " ));
}
Алгоритм remove()
template< class ForwardIterator, class Type >
ForwardIterator
remove( ForwardIterator first,
ForwardIterator last, const Type &value );
remove() удаляет из диапазона [first,last) все элементы со значением value. Этот алгоритм (как и remove_if()) на самом деле не исключает элементы из контейнера (т.е. размер контейнера сохраняется), а перемещает каждый оставляемый элемент в очередную позицию, начиная с first. Возвращаемый итератор указывает на элемент, следующий за позицией, в которую помещен последний неудаленный элемент. Рассмотрим, например, последовательность {0,1,0,2,0,3,0,4}. Предположим, что нужно удалить все нули. В результате получится последовательность {1,2,3,4,0,4,0,4}. 1 помещена в первую позицию, 2 – во вторую, 3 – в третью и 4 – в четвертую. Элементы, начиная с 0 в пятой позиции, – это “отходы” алгоритма. Возвращенный итератор указывает на 0 в пятой позиции. Обычно этот итератор затем передается алгоритму erase(), который удаляет неподходящие элементы. (При работе со встроенным массивом лучше использовать алгоритмы remove_copy() и remove_copy_if(), а не remove() и remove_if(), поскольку его размер невозможно изменить)
Алгоритм remove_copy()
template< class InputIterator, class OutputIterator,
class Type >
OutputIterator
remove_copy( InputIterator first, InputIterator last,
OutputIterator result, const Type &value );
remove_copy() копирует все элементы, кроме имеющих значение value, в контейнер, на начало которого указывает result. Возвращаемый итератор указывает на элемент за последним скопированным. Исходный контейнер не изменяется.
#include
#include
#include
#include
/* печатается:
исходный вектор:
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
#include
#include
/* печатается:
исходная последовательность:
0 1 1 2 3 5 8 13 21 34
последовательность после применения remove_if < 10:
13 21 34
последовательность после применения remove_copy_if четное:
1 1 3 5 13 21
*/
class EvenValue {
public:
bool operator()( int value ) {
return value % 2 ? false : true; }
};
int main()
{
int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 };
vector< int, allocator >::iterator iter;
vector< int, allocator > vec( ia, ia+10 );
ostream_iterator< int > ofile( cout, " " );
cout << "исходная последовательность:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
iter = remove_if( vec.begin(), vec.end(),
bind2nd(less(),10) );
vec.erase( iter, vec.end() );
cout << "последовательность после применения remove_if < 10:\n";
copy( vec.begin(), vec.end(), ofile ); cout << '\n';
vector< int, allocator > vec_res( 10 );
iter = remove_copy_if( ia, ia+10, vec_res.begin(), EvenValue() );
cout << "последовательность после применения remove_copy_if четное:\n";
copy( vec_res.begin(), iter, ofile ); cout << '\n';
}
Алгоритм replace()
template< class ForwardIterator, class Type >
void
replace( ForwardIterator first, ForwardIterator last,
const Type& old_value, const Type& new_value );
replace() заменяет в диапазоне [first,last) все элементы со значением old_value на new_value.
Алгоритм replace_copy()
template< class InputIterator, class InputIterator,
class Type >
OutputIterator
replace_copy( InputIterator first, InputIterator last,
class OutputIterator result,
const Type& old_value, const Type& new_value );
replace_copy() ведет себя так же, как replace(), только новая последовательность копируется в контейнер, начиная с result. Возвращаемый итератор указывает на элемент, расположенный за последним скопированным. Исходный контейнер остается без изменения.
#include
#include
#include
/* печатается:
исходная последовательность:
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"
};
<< Пред. стр. 110 (из 121) След. >>
Список литературы по разделу