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

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

 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() );
  sort( vec2.begin(), vec2.end(), greater() );
 
  merge( vec1.begin(), vec1.end(),
  vec2.begin(), vec2.end(),
  vec_result.begin(), greater() );
 
  // печатается: 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
 mismatch( InputIterator1 first,
  InputIterator1 last, InputIterator2 first2 );
 
 template< class InputIterator1, class InputIterator2,
  class BinaryPredicate >
 pair
 mismatch( InputIterator1 first, InputIterator1 last,
  InputIterator2 first2, BinaryPredicate pred );
 mismatch() сравнивает две последовательности и находит первую позицию, где элементы различны. Возвращается пара итераторов, каждый из которых указывает на эту позицию в соответствующей последовательности. Если все элементы одинаковы, то каждый итератор в паре указывает на элемент last в своем контейнере. Так, если даны последовательности meet и meat, то оба итератора указывают на третий элемент. В первом варианте для сравнения элементов применяется оператор равенства, а во втором – операция сравнения, заданная пользователем. Если вторая последовательность длиннее первой, “лишние” элементы игнорируются; если же она короче, то поведение программы не определено.
 #include
 #include
 #include
 #include
 
 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 pair_ia = mismatch( ia, ia+7, ia2 );
 
  // печатается: первая пара неодинаковых: ia: 3 и ia2: 4
  cout << "первая пара неодинаковых: ia: "
  << *pair_ia.first << " и ia2: "
  << *pair_ia.second << endl;
 
  list ilist( ia, ia+7 );
  list ilist2( ia2, ia2+7 );
 
  typedef list::iterator iter;
  pair 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
 #include
 #include
 
 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 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
 #include
 #include
 
 /* печатается:
 исходный вектор: 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 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() );
  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
 #include
 #include
 
 /*
 * печатается:
  исходный вектор: 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 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() );
  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.

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

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