Сделай Сам Свою Работу на 5

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

}



©2015- 2019 stydopedia.ru Все материалы защищены законодательством РФ.