<< Пред.           стр. 108 (из 121)           След. >>

Список литературы по разделу

  int ia[] = { 29,23,20,17,15,26,51,12,35,40,
  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
 #include
 #include
 
 template
 void print_elements( Type elem ) { cout << elem << " "; }
 

<< Пред.           стр. 108 (из 121)           След. >>

Список литературы по разделу