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