| Меню сайта |
|
 |
| Категория |
|
|
| Развлечение |
|
|
| ON - LINE |
|
|
| Опрос |
|
|
| Оbserver Ward |
Онлайн всего: 1 Гостей: 1 Пользователей: 0
|
|
| Друзья сайта |
|
|
| Hаша кнопка |
Для обмена банерами , наша кнопка для размещения у вас на сайте
|
|
|
21. Обобщенные алгоритмы в алфавитном порядке (3)
Алгоритм 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(), greater<int>() );
search_value = 26;
vector< int, allocator >::iterator iter;
// необходимо указать, как именно
// осуществлялась сортировка ...
iter = lower_bound( ivec.begin(), ivec.end(),
search_value, greater<int>() );
// печатается:
// Первый элемент, перед которым можно вставить 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< class ForwardIterator, class Compare >
ForwardIterator
max_element( ForwardIterator first,
ForwardIterator last, Compare comp );
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 );
template<class 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(), greater<int>() );
sort( vec2.begin(), vec2.end(), greater<int>() );
merge( vec1.begin(), vec1.end(),
vec2.begin(), vec2.end(),
vec_result.begin(), greater<int>() );
// печатается: 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 >
pair<InputIterator1, InputIterator2>
mismatch( InputIterator1 first,
InputIterator1 last, InputIterator2 first2 );
template< class InputIterator1, class InputIterator2,
class BinaryPredicate >
pair<InputIterator1, 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 };
pair<int*,int*> pair_ia = mismatch( ia, ia+7, ia2 );
// печатается: первая пара неодинаковых: ia: 3 и ia2: 4
cout << "первая пара неодинаковых: ia: "
<<*pair_ia.first << " и ia2: "
<< *pair_ia.second << endl;
list<int,allocator> ilist( ia, ia+7 );
list<int,allocator> ilist2( ia2, ia2+7 );
typedef list<int,allocator>::iterator iter;
pair<iter,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()
{
vector<char,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_iterator<int> 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(), greater<int>() );
copy( vec.begin(), vec.end(), out ); cout << endl;
}
Алгоритм partial_sort()
template < class RandomAccessIterator >
void
partial_sort( RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last );
template < class RandomAccessIterator, class Compare >
void
partial_sort( RandomAccessIterator first,
RandomAccessIterator middle,
RandomAccessIterator last, Compare comp );
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_iterator<int> 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(), greater<int>() );
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} и объект-функцию times<int>. Результатом будет {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
частичная сумма элементов с использованием times<int>():
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<int>():\n";
partial_sum( vec.begin(), vec.end(), vec_res.begin(),
times<int>() );
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 };
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<int>(),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_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(), поскольку его размер невозможно изменить)
|
| Категория: С++ | Добавил: r2d2 (29.09.2011)
|
| Просмотров: 1038
| Рейтинг: 0.0/0 |
Добавлять комментарии могут только зарегистрированные пользователи. [ Регистрация | Вход ] |
|
| Born in Ussr |
|
|
| Залогиниться |
|
|
|
| Турниры |
|
|
|
