Алгоритм iter_swap()

template< class ForwardIterator1, class ForwardIterator2

>

void

iter_swap( ForwardIterator1 a, ForwardIterator2 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;

iter_swap() обменивает значения элементов, на которые указывают итераторы a и b.

}

Алгоритм 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.