<< Пред. стр. 108 (из 121) След. >>
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
sort( ivec.begin()+10, ivec.end(), greater
cout << "ivec разбит на два отсортированных подвектора: \n";
for_each( ivec.begin(), ivec.end(), pfi ); cout << "\n\n";
inplace_merge( ivec.begin(), ivec.begin()+10,
ivec.end(), greater
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
#include
#include
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
#include
#include
#include
#include
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
#include
#include
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
search_value = 26;
vector< int, allocator >::iterator iter;
// необходимо указать, как именно
// осуществлялась сортировка ...
iter = lower_bound( ivec.begin(), ivec.end(),
search_value, greater
// печатается:
// Первый элемент, перед которым можно вставить 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
#include
#include
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
#include
#include