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

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

  swap_ranges( &ia[0], &ia[5], &ia[5] );
 
  cout << "массив после перестановки двух половин:\n";
  copy( ia, ia+10, ofile ); cout << '\n';
 
  // перестановка разных контейнеров
  vector< int, allocator >::iterator last =
  find( vec.begin(), vec.end(), 5 );
 
  swap_ranges( vec.begin(), last, vec2.begin() );
 
  cout << "первый контейнер после перестановки двух векторов:\n";
  copy( vec.begin(), vec.end(), ofile ); cout << '\n';
 
  cout << "второй контейнер после перестановки двух векторов:\n";
  copy( vec2.begin(), vec2.end(), ofile ); cout << '\n';
 }
  Алгоритм transform()
 template< class InputIterator, class OutputIterator,
  class UnaryOperation >
 OutputIterator
 transform( InputIterator first, InputIterator last,
  OutputIterator result, UnaryOperation op );
 
 template< class InputIterator1, class InputIterator2,
  class OutputIterator, class BinaryOperation >
 OutputIterator
 transform( InputIterator1 first1, InputIterator1 last,
  InputIterator2 first2, OutputIterator result,
  BinaryOperation bop );
 Первый вариант transform() генерирует новую последовательность, применяя операцию op к каждому элементу из диапазона [first,last). Например, если есть последовательность {0,1,1,2,3,5} и объект-функция Double, удваивающий свой аргумент, то в результате получим {0,2,2,4,6,10}.
 Второй вариант генерирует новую последовательность, применяя бинарную операцию bop к паре элементов, один из которых взят из диапазона [first1,last1), а второй – из последовательности, начинающейся с first2. Поведение программы не определено, если во второй последовательности меньше элементов, чем в первой. Например, для двух последовательностей {1,3,5,9} и {2,4,6,8} и объекта-функции AddAndDouble, которая складывает два элемента и удваивает их сумму, результатом будет {6,14,22,34}.
 Оба варианта transform() помещают результирующую последовательность в контейнер с элемента, на который указывает итератор result. Этот итератор может адресовать и элемент любого из входных контейнеров, в таком случае исходные элементы будут заменены на результат выполнения transform(). Выходной итератор указывает на элемент за последним помещенным в результирующий контейнер.
 #include
 #include
 #include
 #include
 
 /*
 * печатается:
  исходный массив: 3 5 8 13 21
  преобразование элементов путем удваивания: 6 10 16 26 42
  преобразование элементов путем взятия разности: 3 5 8 13 21
 */
 
 int double_val( int val ) { return val + val; }
 int difference( int val1, int val2 ) {
  return abs( val1 - val2 ); }
 
 int main()
 {
  int ia[] = { 3, 5, 8, 13, 21 };
  vector vec( 5 );
  ostream_iterator outfile( cout, " " );
 
  cout << "исходный массив: ";
  copy( ia, ia+5, outfile ); cout << endl;
 
  cout << "преобразование элементов путем удваивания: ";
  transform( ia, ia+5, vec.begin(), double_val );
  copy( vec.begin(), vec.end(), outfile ); cout << endl;
 
  cout << "преобразование элементов путем взятия разности: ";
  transform( ia, ia+5, vec.begin(), outfile, difference );
  cout << endl;
 }
  Алгоритм unique()
 template< class ForwardIterator >
 ForwardIterator
 unique( ForwardIterator first,
  ForwardIterator last );
 template< class ForwardIterator, class BinaryPredicate >
 ForwardIterator
 unique( ForwardIterator first,
  ForwardIterator last, BinaryPredicate pred );
 Все группы равных соседних элементов заменяются одним. В первом варианте при сравнении используется оператор равенства, определенный для типа элементов в контейнере. Во втором варианте два элемента равны, если бинарный предикат pred для них возвращает true. Таким образом, слово mississippi будет преобразовано в misisipi. Обратите внимание, что три буквы 'i' не являются соседними, поэтому они не заменяются одной, как и две пары несоседних 's'. Если нужно, чтобы все одинаковые элементы были заменены одним, придется сначала отсортировать контейнер.
 На самом деле поведение unique() интуитивно не совсем очевидно и напоминает remove(). В обоих случаях размер контейнера не изменяется: каждый уникальный элемент помещается в очередную позицию, начиная с first.
 В нашем примере физически будет получено слово misisipippi, где ppi – остаток, “отходы” алгоритма. Возвращаемый итератор указывает на начало этого остатка и обычно передается алгоритму erase() для удаления ненужных элементов. (Поскольку для встроенного массива операция erase() не поддерживается, то лучше воспользоваться алгоритмом unique_copy().)
  Алгоритм unique_copy()
 template< class InputIterator, class OutputIterator >
 OutputIterator
 unique_copy( InputIterator first, InputIterator last,
  OutputIterator result );
 
 template< class InputIterator, class OutputIterator,
  class BinaryPredicate >
 OutputIterator
 unique_copy( InputIterator first, InputIterator last,
  OutputIterator result, BinaryPredicate pred );
 unique_copy() копирует входной контейнер в выходной, заменяя группы одинаковых соседних элементов на один элемент с тем же значением. О том, что понимается под равными элементами, говорилось при описании алгоритма unique(). Чтобы все дубликаты были гарантированно удалены, входной контейнер необходимо предварительно отсортировать. Возвращаемый итератор указывает на элемент за последним скопированным.
 #include
 #include
 #include
 #include
 #include
 
 template
 void print_elements( Type elem ) { cout << elem << " "; }
 
 void (*pfi)( int ) = print_elements;
 void (*pfs)( string ) = print_elements;
 
 int main()
 {
  int ia[] = { 0, 1, 0, 2, 0, 3, 0, 4, 0, 5 };
 
  vector vec( ia, ia+10 );
  vector::iterator vec_iter;
 
  // последовательность не изменяется: нули не стоят рядом
  // печатается: 0 1 0 2 0 3 0 4 0 5
  vec_iter = unique( vec.begin(), vec.end() );
  for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";
 
  // отсортировать вектор, затем применить unique: модифицируется
  // печатается: 0 1 2 3 4 5 2 3 4 5
  sort( vec.begin(), vec.end() );
  vec_iter = unique( vec.begin(), vec.end() );
  for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";
 
  // удалить из контейнера ненужные элементы
  // печатается: 0 1 2 3 4 5
  vec.erase( vec_iter, vec.end() );
  for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";
 
  string sa[] = { "enough", "is", "enough",
  "enough", "is", "good" };
 
  vector svec( sa, sa+6 );
  vector vec_result( svec.size() );
  vector::iterator svec_iter;
 
  sort( svec.begin(), svec.end() );
  svec_iter = unique_copy( svec.begin(), svec.end(),
  vec_result.begin() );
 
  // печатается: enough good is
  for_each( vec_result.begin(), svec_iter, pfs );
  cout << "\n\n";
 }
  Алгоритм upper_bound()
 template< class ForwardIterator, class Type >
 ForwardIterator
 upper_bound( ForwardIterator first,
  ForwardIterator last, const Type &value );
 
 template< class ForwardIterator, class Type, class Compare >
 ForwardIterator
 upper_bound( ForwardIterator first,
  ForwardIterator last, const Type &value,
  Compare comp );
 upper_bound() возвращает итератор, указывающий на последнюю позицию в отсортированной последовательности [first,last), в которую еще можно вставить значение value, не нарушая упорядоченности. Значения всех элементов, начиная с этой позиции и далее, будут больше, чем value. Например, если дана последовательность:
 int ia[] = {12,15,17,19,20,22,23,26,29,35,40,51};
 то обращение к upper_bound() с value=21 вернет итератор, указывающий на значение 22, а обращение с value=22 – на значение 23. В первом варианте для сравнения используется оператор “меньше”, определенный для типа элементов контейнера; во втором – заданная программистом операция comp.
 #include
 #include
 #include
 #include
 
 template
 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};
  vector vec(ia,ia+12);
 
  sort(ia,ia+12);
  int *iter = upper_bound(ia,ia+12,19);
  assert( *iter == 20 );
 
  sort( vec.begin(), vec.end(), greater() );
  vector::iterator iter_vec;
 
  iter_vec = upper_bound( vec.begin(), vec.end(),
  27, greater() );
 
  assert( *iter_vec == 26 );
 
  // печатается: 51 40 35 29 27 26 23 22 20 19 17 15 12
  vec.insert( iter_vec, 27 );
  for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";
 }
  Алгоритмы для работы с хипом
 В стандартной библиотеке используется макс-хип. Макс-хип – это представленное в виде массива двоичное дерево, для которого значение ключа в каждом узле больше либо равно значению ключа в каждом из узлов-потомков. (Подробное обсуждение макс-хипа можно найти в [SEDGEWICK88]. Альтернативой ему является мин-хип, для которого значение ключа в каждом узле меньше либо равно значению ключа в каждом из узлов-потомков.) В реализации из стандартной библиотеки самое большое значение (корень дерева) всегда оказывается в начале массива. Например, приведенная последовательность букв удовлетворяет требованиям, накладываемым на хип:
 
 X T O G S M N A E R A I
 
 В данном примере X – это корневой узел, слева от него находится T, а справа – O. Обратите внимание, что потомки не обязательно должны быть упорядочены (т.е. значение в левом узле не обязано быть меньше, чем в правом). G и S – потомки узла T, а M и N – потомки узла O. Аналогично A и E – потомки G, R и A – потомки S, I – левый потомок M, а N – листовой узел без потомков.
 Четыре обобщенных алгоритма для работы с хипом: make_heap(), pop_heap(), push_heap() и sort_heap() – поддерживают его создание и различные манипуляции. В последних трех алгоритмах предполагается, что последовательность, ограниченная парой итераторов, – действительно хип (в противном случае поведение программы не определено). Заметим, что список нельзя использовать как контейнер для хранения хипа, поскольку он не поддерживает произвольный доступ. Встроенный массив для размещения хипа использовать можно, но в этом случае трудно применять алгоритмы pop_heap() и push_heap(), так как они требуют изменения размера контейнера. Мы опишем все четыре алгоритма, а затем проиллюстрируем их работу на примере небольшой программы.
  Алгоритм make_heap()
 template< class RandomAccessIterator >
 void
 make_heap( RandomAccessIterator first,
  RandomAccessIterator last );
 
 template< class RandomAccessIterator, class Compare >
 void
 make_heap( RandomAccessIterator first,
  RandomAccessIterator last, Compare comp );
 make_heap() преобразует в хип последовательность, ограниченную диапазоном [first,last). В первом варианте для сравнения используется оператор “меньше”, определенный для типа элементов контейнера, а во втором – операция comp.
  Алгоритм pop_heap()
 template< class RandomAccessIterator >
 void
 pop_heap( RandomAccessIterator first,
  RandomAccessIterator last );
 
 template< class RandomAccessIterator, class Compare >
 void
 pop_heap( RandomAccessIterator first,
  RandomAccessIterator last, Compare comp );
 pop_heap() в действительности не исключает наибольший элемент, а переупорядочивает хип. Он переставляет элементы в позициях first и last-1, а затем перестраивает в хип последовательность в диапазоне [first,last-1). После этого “вытолкнутый” элемент можно получить посредством функции-члена back() контейнера либо по-настоящему исключить его с помощью pop_back(). В первом варианте при сравнении используется оператор “меньше”, определенный для типа элементов контейнера, а во втором – операция comp.
  Алгоритм push_heap()
 template< class RandomAccessIterator >
 void
 push_heap( RandomAccessIterator first,
  RandomAccessIterator last );
 
 template< class RandomAccessIterator, class Compare >
 void
 push_heap( RandomAccessIterator first,
  RandomAccessIterator last, Compare comp );
 push_heap() предполагает, что последовательность, ограниченная диапазоном [first,last-1), – хип и что новый добавляемый к хипу элемент находится в позиции last-1. Все элементы в диапазоне [first,last) реорганизуются в новый хип. Перед вызовом push_heap() необходимо вставить новый элемент в конец контейнера, возможно, применив функцию push_back() (это показано в примере ниже). В первом варианте при сравнении используется оператор “меньше”, определенный для типа элементов контейнера; во втором – операция comp.
  Алгоритм sort_heap()
 template< class RandomAccessIterator >
 void
 sort_heap( RandomAccessIterator first,
  RandomAccessIterator last );
 
 template< class RandomAccessIterator, class Compare >
 void
 sort_heap( RandomAccessIterator first,
  RandomAccessIterator last, Compare comp );
 sort_heap() сортирует последовательность в диапазоне [first,last), предполагая, что это правильно построенный хип; в противном случае поведение программы не определено. (Разумеется, после сортировки хип перестает быть хипом!) В первом варианте при сравнении используется оператор “меньше”, определенный для типа элементов контейнера, а во втором – операция comp.
 #include
 #include
 #include
 
 template
 void print_elements( Type elem ) { cout << elem << " "; }
 
 int main()
 {
  int ia[] = { 29,23,20,22,17,15,26,51,19,12,35,40 };
  vector< int, allocator > vec( ia, ia+12 );
 
 
  // печатается: 51 35 40 23 29 20 26 22 19 12 17 15
  make_heap( &ia[0], &ia[12] );
  void (*pfi)( int ) = print_elements;
  for_each( ia, ia+12, pfi ); cout << "\n\n";
 
  // печатается: 12 17 15 19 23 20 26 51 22 29 35 40
  // минимальный хип: в корне наименьший элемент
  make_heap( vec.begin(), vec.end(), greater() );
  for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";
 
  // печатается: 12 15 17 19 20 22 23 26 29 35 40 51
  sort_heap( ia, ia+12 );
  for_each( ia, ia+12, pfi ); cout << "\n\n";
 
  // добавим новый наименьший элемент
  vec.push_back( 8 );
 
  // печатается: 8 17 12 19 23 15 26 51 22 29 35 40 20
  // новый наименьший элемент должен оказаться в корне
  push_heap( vec.begin(), vec.end(), greater() );
  for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";
 
  // печатается: 12 17 15 19 23 20 26 51 22 29 35 40 8
  // наименьший элемент должен быть заменен на следующий по порядку
 
  pop_heap( vec.begin(), vec.end(), greater() );
  for_each( vec.begin(), vec.end(), pfi ); cout << "\n\n";
 }
 
 #
 #include, директива
 использование с using-директивой, 68, 427
 использование с директивой связывания, 354
 *
 умножения оператор
 комплексных чисел, 155
 ч
 члены класса
 функции-члены
 константные, 611–14
 подвижные (volatile), 611–14
 Д
 деструктор(ы)
 для элементов масс??а
 освобождение динамической памяти, 693–94
 abort(), функция
 вызов из terminate() как подразумеваемое поведение, 541
 abs(), функция
 поддержка для комплексных чисел, 156
 accumulate(), обобщенный алгоритм, 1104
 adjacent_difference(), обобщенный алгоритм, 1106

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

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